P8417 [THUPC2022 决赛] 高性能计算导论集群登录密码复杂性策略

251Sec · 2024-09-02 19:29:55 · 题解

简单题，咋没人写题解。

不难得到一个暴力 DP 形如 f(n,c,l_1,l_2,l_3,0/1,0/1)，即已经填了 n 位，最后一位为 c，结尾相等、上升、下降的长度为 l_{1..3}，是否已经选出了字母，是否已经选出了数字的方案数。这个 DP 太炸裂了，不过我们再观察一下：l_{1..3} 至多有一个不是 1，c 为大写字母和小写字母的状态是等价的，最后两个 0/1 实际上只需要记一个代表是否存在一个位置左侧和右侧分别为字母和数字。所以状态数瞬间就少了很多，只有几千种了，可以暴力 DP 前 10^3 项。l,r 很大，看起来就很线性递推，所以记录 s(n) 代表长度 \le n 的密码种类数，然后直接把它丢进 BM 一看发现递推式长度只有几百。那就做完了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 1e9 + 7;
ll QPow(ll a, ll b) {
    ll res = 1;
    for (; b; b >>= 1, a = a * a % P) if (b & 1) res = res * a % P;
    return res;
}
struct Poly {
    vector<ll> w;
    Poly() {}
    Poly(int sz) : w(sz) {}
    Poly(vector<ll> w) : w(w) {}
    ll &operator[](int i) { return w[i]; }
    ll operator[](int i) const { return w[i]; }
    int size() const { return w.size(); }
    void resize(int x) { w.resize(x); }
    Poly operator*(const Poly &b) const {
        Poly res(size() + b.size() - 1);
        for (int i = 0; i < size(); i++) {
            for (int j = 0; j < b.size(); j++) {
                res[i + j] += w[i] * b[j] % P;
            }
        }
        for (int i = 0; i < res.size(); i++) res[i] %= P;
        return res;
    }
    Poly operator%(const Poly &b) const {
        if (size() < b.size()) return *this;
        Poly a = *this;
        ll iv = QPow(b.w.back(), P - 2);
        int m = b.size() - 1;
        for (int i = size() - 1; i >= m; i--) {
            if (!a[i]) continue;
            ll w = a[i] * iv % P;
            for (int j = 0; j <= m; j++) (a[i - j] -= w * b[m - j] % P) %= P;
        }
        for (int i = 0; i < a.size(); i++) a[i] = (a[i] % P + P) % P;
        while (a.size() && !a.w.back()) a.w.pop_back();
        return a;
    }
};
namespace BM {
    vector<ll> cur, lst;
    ll del, fail;
    void UpdLst(vector<ll> t, ll tdel, ll tfail) {
        if ((int)t.size() - tfail < (int)lst.size() - fail) fail = tfail, del = tdel, lst = t;
    }
    vector<ll> Solve(ll *a, int n) {
        for (int i = 1; i <= n; i++) {
            ll d = a[i];
            for (int j = 0; j < cur.size(); j++) d -= a[i - j - 1] * cur[j] % P;
            d = (d % P + P) % P;
            if (!d) continue;
            vector<ll> tcur = cur;
            if (!fail) cur.resize(i);
            else {
                ll w = d * del % P;
                if (cur.size() < i - fail + lst.size()) cur.resize(i - fail + lst.size());
                (cur[i - fail - 1] += w) %= P;
                for (int j = 0; j < lst.size(); j++) (cur[i - fail + j] += (P - lst[j]) * w % P) %= P;
            }
            UpdLst(tcur, QPow(d, P - 2), i);
        }
        for (int i = 0; i < cur.size(); i++) cur[i] = (P - cur[i]) % P;
        reverse(cur.begin(), cur.end());
        cur.push_back(1);
        return cur;
    }
}
int l, r, a, b;
ll f[1005][36][26][2][3], s[1005];
void Upd(ll &x, ll y) { (x += y) %= P; }
ll Calc(Poly f, int n) {
    Poly a; a.resize(2), a[1] = 1;
    Poly res; res.resize(1), res[0] = 1;
    for (; n; n >>= 1, a = a * a % f) if (n & 1) res = res * a % f;
    ll ans = 0;
    for (int i = 0; i < res.size(); i++) ans += res[i] * s[i] % P;
    return ans % P;
}
int main() {
    scanf("%d%d%d%d", &l, &r, &a, &b);
    for (int i = 0; i < 36; i++) f[1][i][1][0][0] = 1 + (i > 9);
    for (int i = 1; i <= 1000; i++) {
        for (int j = 0; j < 36; j++) {
            for (int k = 1; k < 26; k++) {
                for (int x = 0; x < 2; x++) {
                    for (int y = 0; y < 3; y++) {
                        if (f[i][j][k][x][y] && ((!y && k < a) || (y && k < b))) {
                            ll w = f[i][j][k][x][y];
                            for (int z = 0; z < 36; z++) {
                                if (z == j) Upd(f[i + 1][z][!y ? k + 1 : 2][x][0], w);
                                else if (z == j + 1 && j != 9) Upd(f[i + 1][z][y == 1 ? k + 1 : 2][x][1], w);
                                else if (z == j - 1 && j != 10) Upd(f[i + 1][z][y == 2 ? k + 1 : 2][x][2], w);
                                else Upd(f[i + 1][z][1][x || ((j < 10) != (z < 10))][0], w);
                                if (z > 9) Upd(f[i + 1][z][1][x || ((j < 10) != (z < 10))][0], w);
                            }
                            if (x) Upd(s[i], w);
                        }
                    }
                }
            }
        }
    }
    for (int i = 1; i <= 1000; i++) Upd(s[i], s[i - 1]);
    auto g = BM::Solve(s - 1, 1001);
    printf("%lld\n", (Calc(g, r) - Calc(g, l - 1) + P) % P);
    return 0;
}