[COGS2287][HZOI 2015]疯狂的机器人（NTT+组合数学）

题目描述

传送门

题解

本来是想找一道题想一想dp到底是怎么用FFT优化的，然而写完了发现怎么和dp没啥关系呢 也可能是我太弱根本没看出来dp 不过确实是一道好题！在hxy神犇的一些提示下做出来…

令 g(i) 表示只能上下走，不能左右走，不能不走，走i步最后回到原点的方案数 首先可以发现当i为奇数的时候 g(i) 一定为0 接着考虑i为偶数的情况，很显然向上走的步数和向下走的步数一定相等，都为 i2 。求 g(i) 也就是求解这样一个问题：向上走 i2 步，向下走 i2 步，并且必须保证在任何时刻向上走的步数大于等于向下走的步数 这不就是卡特兰数问题嘛，一个组合数公式 g(i)=Ci2i−Ci2+1i 显然只能左右走，不能上下走，不能不走，走i步回到原点的方案数也是 g(i)

令 f(i) 表示只能上下左右走，不能不走，走i步最后回到原点的方案数， f(i) 可以写成 f(i)=∑j=0ig(i−j)g(j)Cji 也就是说先选出一部分只能上下走，剩下的只能左右走 将组合数展开，令 g′(i)=g(i)i! 能搞成一个卷积的形式 f(i)=∑j=0ig(i−j)g(j)i!j!(i−j)!=i!∑j=0ig(i−j)(i−j)!g(j)j!=i!∑j=0ig′(i−j)g′(j) 然后用NTT就可以求出 f(i) 了

最后考虑将不走的添加进去，即 ans=∑i=0nf(i)∗Cin

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define LL long long #define N 300005 const LL Mod=998244353LL; int n,m,L,R[N]; LL mul[N],g[N],a[N],b[N],f[N],ans; void calc_mul(int n) { mul[0]=1LL; for (int i=1;i<=n;++i) mul[i]=mul[i-1]*(LL)i%Mod; } LL fast_pow(LL a,LL p) { LL ans=1LL; for (;p;p>>=1,a=a*a%Mod) if (p&1) ans=ans*a%Mod; return ans; } LL C(int n,int m) { if (m>n) return 0LL; return mul[n]*fast_pow(mul[m]*mul[n-m]%Mod,Mod-2)%Mod; } void NTT(LL a[N],int n,int opt) { for (int i=0;i<n;++i) if (i<R[i]) swap(a[i],a[R[i]]); for (int k=1;k<n;k<<=1) { LL wn=fast_pow(3,(Mod-1)/(k<<1)); for (int i=0;i<n;i+=(k<<1)) { LL w=1; for (int j=0;j<k;++j,w=w*wn%Mod) { LL x=a[i+j],y=w*a[i+j+k]%Mod; a[i+j]=(x+y)%Mod,a[i+j+k]=(x-y+Mod)%Mod; } } } if (opt==-1) reverse(a+1,a+n); } int main() { scanf("%d",&n); calc_mul(n); for (int i=1;i<=n;++i) { if (i&1) continue; g[i]=C(i,i/2)-C(i,i/2+1); g[i]=(g[i]+Mod)%Mod; }g[0]=1LL; for (int i=1;i<=n;++i) g[i]=g[i]*fast_pow(mul[i],Mod-2)%Mod; for (int i=0;i<=n;++i) a[i]=b[i]=g[i]; m=n+n; for (n=1;n<=m;n<<=1) ++L; for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); NTT(a,n,1);NTT(b,n,1); for (int i=0;i<=n;++i) a[i]=a[i]*b[i]%Mod; NTT(a,n,-1); LL inv=fast_pow(n,Mod-2); for (int i=0;i<=n;++i) a[i]=a[i]*inv%Mod; for (int i=0;i<=m/2;++i) f[i]=mul[i]*a[i]%Mod; for (int i=0;i<=m/2;++i) ans=(ans+f[i]*C(m/2,i)%Mod)%Mod; printf("%I64d\n",ans); }