题解 P5173 【传球】

· · 题解

我们设 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

然而作者并不会MTT 由于 MTT 太难写了，所以我们直接用暴力做多项式乘法，这样的时间复杂度是 O(n^2 \log m) 的，只能得到 60 分。

常数优化 1：多项式中某一项为 0 就直接 continue; 得分 68。

常数优化 2：使用 memset 清 0，得分 96。

常数优化 3：把多项式的长度作为函数参数而不是全局变量传入多项式乘法中，得分 100。

这样写代码长度极短，并且异常好写。

代码：

#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]);
}