P8735 题解

joke3579 · 2023-02-23 15:30:54 · 题解

1. 1\le k,p \le 50,\ 1\le l\le 10^{3}

考虑直接 dp。

设 f({i,j}) 为当前整数大小为 i，最后一项为 j 的序列的计数。 容易写出转移：

直接转移即可做到 O(kpl)，答案即为 \sum_{i=1}^k f({l,i})。
Submission.

进行状态的压缩。我们发现 j 这一维实际上只记录了 j< p 的情况和 j\ge p 的情况，这可以在转移时完成。然后就可以把这两种状态压缩：
设 f({i,0/1}) 为当前整数大小为 i，最后一项是否小于 p 的序列的计数。有转移：

答案即为 f({l,0}) + f({l,1})。直接转移即可做到 O(kl)。
Submission.

2. 1\le k,p \le 50,\ 1\le l\le 10^{18}

可以发现，如上 O(kl) 的转移是线性的，可以写成矩阵乘法的形式。具体地，我们使用 2k\times 2k 的矩阵进行转移，初始向量记录 1\sim k 段内所有 f({i,0}) 与 f({i,1})。

例如，当 k=5, p=3 时矩阵即为：

转移即可。总时间复杂度 O(8k^3\log l)。
Submission.

3. 1\le k,p \le 1000,\ 1\le l\le 10^{18}

你看这个转移矩阵是不是和线性递推的很像？

考虑设 g({i}) = f({i,0}) + f({i,1})。 我们可以写

前面那部分可以直接扔进线性递推转移。
对于后半部分，考虑在最后一步 i \ge p 时，仅有倒数第二步 j < p 的状态能够全部转移。同时，考虑这里的贡献在 j < p 时已经被算了，我们只需要 \ge p 的 j。算一下有多少个 j 满足条件，这就是 f(i) 对应的系数。
这里由于需要让所有贡献都被算完，线性递推的长度是 k + p - 1 的。

转移时直接模拟多项式乘法即可，总复杂度为 O(k^2 \log l)。Submission.
应用任意模数多项式乘法即可做到 O(k\log k\log n)。

可能 80% 的部分分是给数组开小的正解准备的。Submission.

#include <bits/stdc++.h>
using namespace std; using pii = pair<int,int>;
using ll = long long; using ull = unsigned long long; using db = double; using ld = long double; using lll = __int128_t;
template<typename T> void get(T & x) {
    x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i#_ = (t) + 1; i < i#_; ++ i)
#define pre(i,s,t) for (register int i = (s), i#_ = (t) - 1; i > i#_; -- i)
const int N = 4e3 + 10;

const int mod = 20201114;
template <typename T1, typename T2> T1 add(T1 a, T2 b) { return (a += b) >= mod ? a - mod : a; }template <typename T1, typename ...Args> T1 add(T1 a, Args ... b) { return add(a, add(b...)); }
struct FastMod { int m; ll b; void init(int _m) { m = _m; b = ((lll)1<<64) / m; } FastMod(int _m) { init(_m); } int operator() (ll a) {ll q = ((lll)a * b) >> 64; a -= q * m; if (a >= m) a -= m; return a; } } Mod(mod);
int mul(int a, int b) { return Mod(1ll * a * b); } template <typename ...Args> int mul(int a, Args ...b) { return mul(a, mul(b...)); }

int k, mx, p, sum[N][2], ans;
int f[N], h[N];
ll l;

struct seq {
    int a[N];
    int & operator [] (const int & p) { return a[p]; }
    const int operator [] (const int & p) const { return a[p]; }
    seq operator * (const seq & b) const {
        seq ret; rep(i,0,mx-1) ret[i] = 0;
        rep(i,0,mx-1) rep(j,0,mx-1) ret[i + j] = add(ret[i + j], mul(a[i], b[j]));
        for (int i = (mx-1) << 1; i >= mx; ret[i] = 0, -- i) rep(j,1,mx) 
            ret[i - j] = add(ret[i - j], mul(ret[i], f[j]));
        return ret;
    }
} res;

seq qp(seq a, ll b) {
    seq ret; memset(ret.a, 0, sizeof ret.a); ret[0] = 1;
    while (b) {
        if (b & 1) ret = ret * a;
        a = a * a;
        b >>= 1;
    } return ret;
}

int main() {
    get(k, p, l); mx = k + p - 1; -- l;
    sum[0][0] = 1;
    rep(i,1,mx) {
        rep(j,1,min(p - 1, i)) {
            sum[i][0] = add(sum[i][0], sum[i - j][0], sum[i - j][1]);
        }
        rep(j,p,min(k, i)) {
            sum[i][1] = (sum[i][1] + sum[i - j][0]) % mod;
        }
    } 

    rep(i,1,p-1) f[i] = 1;
    rep(i,p,k+p-1) rep(j,p,k) if (0 < i - j and i - j < p) ++ f[i];
    rep(i,0,k+p-1) h[i] = add(sum[i + 1][0], sum[i + 1][1]);

    if (l <= mx) {
        cout << h[l] << endl;
        return 0;
    }

    res[1] = 1; ans = 0;
    res = qp(res, l);
    rep(i,0,mx - 1) ans = add(ans, mul(res[i], h[i]));
    cout << ans << endl;
}