土拨鼠
小X在设想自己2027年毕业后的生活。
在他的设想中，他回到乡下种土豆。但是田地需要恰当的管理措施，其中之一是防止土拨鼠破坏土豆。
小X设想的 \(n+1\) 块土豆田排在一条直线上，从左到右编号为 \(0\) 到 \(n\)。第 $i $块土豆田里有i株各不相同的土豆，其中 \(0\) 号土豆田是土拨鼠的巢。
每一个时刻，土拨鼠会离开当前所在的土豆田去往下一块土豆田。若土拨鼠当前所在的土豆田编号为i
，那么它能到达的下一块土豆田的编号 \(j\) 必须满足 \(j−i \in S\)，其中S中只包含不大于 \(15\) 的正整数。若 \(i≥0\)，土拨鼠在离开的同时还会破坏第 \(i\) 块土豆田中的至多一棵土豆。
小X想知道，对于给定的正整数 \(n\)，若土拨鼠最后到达了 \(n\) 号土豆田，它有多少种破坏土豆田的方案。两种方案不同当且仅当土拨鼠经过的路径不同，或破坏的土豆不同。注意，此时 \(N\) 号土豆田上的土豆并没有被破坏。
由于答案可能很大，小X只要知道这个方案数对2027取模的结果。
\(n ≤ 10^{18},|S|≤15\)，对于所有 \(t∈S,1≤t≤\min(n,15)\)。
\(Sol\)
设 \(f_i\) 为到 \(i\) 点时的方案数，考虑一个 \(j \in S\)，在 \(i - j\) 上有 \(i - j\) 个土豆，可以选择破坏 \(0,1,...,i - j\) 个，一共 \(i - j + 1\) 个方案，故得到转移方程
\[f_i = \sum_{j \in S} (i - j + 1) \times f_j \]式子非常简单，但是 \(n\) 特别大，考虑矩阵加速。
直接做的话每次的转移系数不同，不好做，但是模数比较小，这启发我们 \(f_i\) 与 \(f_{i+2027}\) 的转移矩阵是一样的，于是我们可以把前2027个矩阵先暴力推出来，然后分为 \(n / 2027\) 和 \(n % 2027\) 去做。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 2027;
ll n;
int m;
int a[20];
struct Matrix {
int n, m;
int c[20][20];
void init(int _n, int _m) {
n = _n, m = _m;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++) c[i][j] = 0;
}
Matrix operator *(const Matrix t) const {
static Matrix res;
res.init(n, t.m);
for(int i = 1; i <= res.n; i ++)
for(int j = 1; j <= res.m; j ++)
for(int k = 1; k <= m; k ++) {
res.c[i][j] = (res.c[i][j] + c[i][k] * t.c[k][j]) % mod;
}
return res;
}
} base, ans, cur[2030];
Matrix power(Matrix a, ll b) {
Matrix res;
res.init(15, 15);
for(int i = 1; i <= 15; i ++) {
res.c[i][i] = 1;
}
for(; b; a = a * a, b /= 2) if(b & 1) res = res * a;
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= m; i ++) {
cin >> a[i];
}
ans.init(1, 15), base.init(15, 15);
ans.c[1][1] = 1;
for(int i = 1; i <= 15; i ++) {
base.c[i][i] = 1;
}
for(int i = 1; i <= 2027; i ++) {
Matrix &t = cur[i];
t.init(15, 15);
for(int j = 1; j <= 14; j ++) {
t.c[j][j + 1] = 1;
}
for(int j = 1; j <= m; j ++) {
t.c[a[j]][1] = (i - a[j] + 1 + mod) % mod;
}
base = base * t;
}
ans = ans * power(base, n / 2027);
for(int i = 1; i <= n % 2027; i ++) {
ans = ans * cur[i];
}
cout << ans.c[1][1] << '\n';
return 0;
}