题解 P5173 【传球】
ezoixx130
2019-01-05 16:49:45
我们设 $f[i][j]$ 表示 $i$ 次传球以后，球在 $j$ 手里的方案数。
容易得到转移式：$f[i][j]=f[i-1][(j-1+n)\bmod n]+f[i-1][(j+1)\bmod n]$
我们发现这是一个循环卷积的形式。
我们设有多项式 $A(x)=x+x^{n-1}$。
容易得到 $f_i(x)=f_{i-1}(x)\times A$。
这里的乘法是循环卷积，也就是说，把次数大于等于 $n$ 的项的系数挪到次数减去 $n$ 的项的系数上。
所以 $f_m(x)=f_0(x) \times A^m$。
我们只需要采用快速幂求出 $A^m$ 即可。
使用 NTT+CRT 或者 MTT 做多项式快速幂可以做到 $O(n\log n\log m)$ 的时间复杂度。
代码见：[https://www.luogu.org/paste/jeqlfiwz](https://www.luogu.org/paste/jeqlfiwz)
~~然而作者并不会MTT~~ 由于 MTT 太难写了，所以我们直接用暴力做多项式乘法，这样的时间复杂度是 $O(n^2 \log m)$ 的，只能得到 $60$ 分。
常数优化 1：多项式中某一项为 $0$ 就直接 `continue;` 得分 $68$。
常数优化 2：使用 `memset` 清 $0$，得分 $96$。
常数优化 3：把多项式的长度作为函数参数而不是全局变量传入多项式乘法中，得分 $100$。
这样写代码长度极短，并且异常好写。
代码：
```cpp
#pragma GCC optimize("Ofast,fast-math,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10000
#define mod 1000000007
#define mul(a,b) ((long long)(a)*(b)%mod)
int n,m,a[MAXN],ans[MAXN];
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
void polymul(int *a,int *b,int *c,int n)
{
int tmp[MAXN];
memset(tmp,0,sizeof(int)*n*2);
for(int i=0;i<n;++i)
if(a[i])
for(int j=0;j<n;++j)
tmp[i+j]=add(tmp[i+j],mul(a[i],b[j]));
for(int i=0;i<n;++i)c[i]=tmp[i];
for(int i=n;i<2*n;++i)c[i-n]=add(c[i-n],tmp[i]);
}
int main()
{
scanf("%d%d",&n,&m);
++a[1];++a[n-1];
ans[0]=1;
while(m)
{
if(m&1)polymul(ans,a,ans,n);
polymul(a,a,a,n);
m>>=1;
}
printf("%d\n",ans[0]);
}
```