自动搬运

查看原文

来自洛谷，原作者为

	joke3579 **

搬运于2025-08-24 22:41:55，当前版本为作者最后更新于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$ 的序列的计数。 容易写出转移：

$$f({i,j}) = \left\{ \begin{aligned} \sum_{t=1}^{k}f({i-j,t}) \qquad j < p \\ \sum_{t=1}^{p-1}f({i-j,t}) \qquad j\ge p \end{aligned} \right.$$

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

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

$$f({i,0}) = \sum_{j=1}^{p-1} f({i-j,0}) + f({i-j,1})\qquad f({i,1}) = \sum_{j=p}^{k} f({i-j,0}) $$

答案即为 $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$ 时矩阵即为：

$$\begin{bmatrix} f({i+1,1})\\ f({i+1,0})\\ f({i,1})\\ f({i,0})\\ f({i-1,1})\\ f({i-1,0})\\ f({i-2,1})\\ f({i-2,0})\\ f({i-3,1})\\ f({i-3,0})\\ \end{bmatrix}= \begin{bmatrix} 0 & 0 & 0 & 0 & 0 &1 & 0 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 0 &0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 &0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 &0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 &0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 &0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 &0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 &1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 &0 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 &0 & 0 & 1 & 0 & 0\\ \end{bmatrix} \begin{bmatrix} f({i,1})\\ f({i,0})\\ f({i-1,1})\\ f({i-1,0})\\ f({i-2,1})\\ f({i-2,0})\\ f({i-3,1})\\ f({i-3,0})\\ f({i-4,1})\\ f({i-4,0})\\ \end{bmatrix} $$

转移即可。总时间复杂度 $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})$。 我们可以写

$$g(i) = \sum_{j=1}^{p-1}\left( f({i-j,0}) + f({i-j,1})\right) + \sum_{j=p}^{k} f({i-j,0}) = \sum_{j=1}^{p-1} g({i-j}) + \sum_{j=p}^{k} f({i-j,0}) $$

前面那部分可以直接扔进线性递推转移。
对于后半部分，考虑在最后一步 $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;
}