P5320 题解
望月Asta
·
·
题解
前言
退役选手不好好学 whk 跑来颓废
题解里都是斯特林数推式子 + 扩域，对我这样脑容量不足的暴力选手不够友好。
这里讲一个十分暴力的 BM + 线性递推做法。
前置知识不会可以左转模板题：
P4723 【模板】常系数齐次线性递推
P5487 【模板】Berlekamp–Massey 算法
解法
初步推导得到的式子都是 \sum_{i = 1}^{n} \binom{f_i}{k} 这样的形式，其中 \{f\} 为一个低阶的常系数齐次线性递推数列（以下“常系数齐次线性递推”简称为“线性递推”）。
考虑证明这是一个线性递推数列，然后就可以大力套 BM 了。
首先对与线性递推有一个非常重要的性质：线性递推的封闭性。
对于线性递推数列 \{a\},\{b\}，有如下几条：
考虑原式，前缀和相当于卷上 \{1,1,1,\cdots\}，可以摘掉。
剩下部分为：
\binom{f_i}{k} &= \frac{\prod_{j = 0}^{k - 1}f_i - j}{k!}\\
\end{aligned}
综上，$\sum_{i = 1}^{n} \binom{f_i}{k}$ 为一个线性递推数列，我们可以 $\mathcal{O} (k ^2)$ 暴力求出前面一定的项数然后丢进 BM 里。
BM 打表可知，最长的递推式长度不超过 $2507$，暴力求其二倍即数列前面约 $5000$ 项即可，时间复杂度 $\mathcal{O(k^2 + k \log k \log n)}$，用 $k^2 \log$ 线性递推在洛谷和 loj 都会被卡。
## 代码
[完整代码](https://www.luogu.com.cn/paste/czm6527n)
博客里就放个核心部分吧，线性递推和 BM 都是板子。
```cpp
#define rep(a,b,c) for(int a = (b);a <= (c);++a)
#define repl(a,b,c) for(int a = (b);a < (c);++a)
#define add(x,y) ( (((x) += (y)) >= MOD) && ((x) -= MOD) )
#define red(x,y) ( (((x) -= (y)) < 0) && ((x) += MOD) )
// 暴力组合数
inline int binom(int n,int m) {
int x = 1,y = 1;
rep(i,1,m) {
x = (i64)x * (n - i + 1) % MOD;
y = (i64)y * i % MOD;
}
return (i64)x * qpow(y) % MOD;
}
int m;
void solve() {
i64 l = readI(),r = readI();
int k = readI();
int frac = qpow((r - l + 1) % MOD);
if(m == 3) {
r >>= 1,l = ((l - 1) >> 1) + 1;
if(l > r) {
PutC('0'),enter;
return ;
}
}
const int lim = 5000;// 暴力计算前 5000 项
g[0] = 1;
rep(i,1,lim) {
g[i] = g[i - 1],f[i] = f[i - 1];
if(m == 3) {
g[i] = g[i] * 4ll % MOD;
if(i ^ 1)
add(g[i],MOD - g[i - 2]);
else
add(g[i],MOD - 1);
}
else if(i ^ 1)
add(g[i],g[i - 2]);
add(f[i],binom(g[i],k));
}
int kk = BerlekampMassey(f,a,lim);// BM 求递推式
int ans = LinearRecurrence(f + 1,a,r - 1,kk);
if(l ^ 1)
add(ans,MOD - LinearRecurrence(f + 1,a,l - 2,kk));
ans = (i64)ans * frac % MOD;
writeI(ans),enter;
}
```