自动搬运

查看原文

来自洛谷，原作者为

	ezoixx130 浴乎沂，风乎舞雩，咏而归

搬运于2025-08-24 22:07:54，当前版本为作者最后更新于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

然而作者并不会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]);
}