好好玩的题。
设普通生成函数 \(F_i\),其中 \([z^k]F_i\) 表示从所有起点走到 \((i,k)\) 的方案数。特别地,\([z^k]F_1=\sum\limits_{a\in A}[a=k]\)。
注意到 \(F_i=(z^{-1}+1+z)F_{i-1}\) 几乎成立,但是在 \([z^1]F_i\) 和 \([z^M]F_i\) 处不成立。
尝试对 \(F_i\) 进行改造:
\[[z^k]F_i^\star=
\begin{cases}
0,&k=0\lor k=M+1\\
[z^k]F_i,&1\le k\le M\\
-[z^{2M+2-k}]F_i,&M+2\le k\le 2M+1
\end{cases}
\]
考察 \(F_i^\star\) 与 \((z^{-1}+1+z)\) 的循环卷积(即 \(\bmod (z^{2M+2}-1)\) 的结果),发现由于 \(F_i^\star\) 是由 \(F_i\) 沿着 \(k=M+1\) 翻折并取相反数得到的,\([z^0]F_i^\star\) 和 \([z^{M+1}]F_i^\star\) 永远会是 \(0\),这就防止了我们移动到网格外,从而使得循环卷积结果的系数恰好是 \(F_{i+1}^\star\) 的各项系数,即:
\[F_{i+1}^\star\equiv F_i^\star(z^{-1}+1+z)\pmod{(z^{2M+2}-1)}
\]
使用快速幂即可,时间复杂度 \(O(M\log M\log N)\)。
去掉封装的核心代码:(完整代码)
Poly<mod, g> qmul(const Poly<mod, g>& a, const Poly<mod, g>& b) {
Poly<mod, g> ans = a * b;
int sz = (int)ans.size();
rep(i, 2*m+2, sz-1) ans[i%(2*m+2)] += ans[i];
ans.resize(2*m+2);
return ans;
}
Poly<mod, g> qpow(Poly<mod, g> a, int k) {
Poly<mod, g> ans{1};
for(; k; k >>= 1, a = qmul(a, a)) if(k & 1) ans = qmul(ans, a);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
initPoly(N);
cin >> n >> m >> k >> l;
Poly<mod, g> a(2*m+2), b(2*m+2);
rep(i, 1, k) {
cin >> x;
++a[x];
--a[2*m+2-x];
}
b[0] = b[1] = b[2*m+1] = 1;
a = qmul(a, qpow(b, n-1));
Modint<mod, g> ans = 0;
rep(i, 1, l) {
cin >> x;
ans += a[x];
}
cout << ans << '\n';
return 0;
}
- 题解 Counting Problem Simple Pathcounting problem simple path 题解counting problem simple 题解counting another problem 题解counting t399753 problem 题解problem simple 3483 counting another path abc integers problem simple 17383 subsequence problem simple 024f 数论counting another problem typical problem 318g path