[HZOI 2015]疯狂的机器人

【题目描述】

现在在二维平面内原点上有一只机器人

他每次操作可以选择向右走，向左走，向下走，向上走和不走(每次如果走只能走一格）

但是由于本蒟蒻施展的大魔法，机器人不能走到横坐标是负数或者纵坐标是负数的点上

否则他就会big bang

给定操作次数n，求有多少种不同的操作序列使得机器人在操作后会回到原点

输出答案模998244353后的结果

注意如果两个操作序列存在某一时刻操作不同，则我们认为这两个操作序列不同

【输入格式】

输入n，表示操作次数

n<=100000

【输出格式】

按要求输出答案

【样例输入】

【样例输出】

【提示】

样例解释：

机器人有7种操作序列

1、不走不走不走

2、不走向右向左

3、向右不走向左

4、向右向左不走

5、不走向上向下

6、向上不走向下

7、向上向下不走

将操作分3类：向上下，向左右，不动
$f[i]$表示只考虑前两类走i步到原点的方案数
$$f[n]=\sum_{i=0}^{n}a[i]*a[n-i]*\binom{n}{i}$$
$a[i]$表示向上向下(或向左向右)走i步回到原点的方案数
显然i为偶数时才有方案否则$a[i]$为0
然后不动就直接枚举f
$$ans=\sum_{i=0}^{n}f[i]*\binom{n}{i}$$
$a[i]$显然就是卡特兰数第$i/2$项
因为任意时刻向上的前缀和总是大于向下的
至于卷积就直接把组合数拆开，把分母分到a上，即：
$$a[i]=C[i/2]*i!^{-1}$$
NTT求出f后再乘上$n!$

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef int lol;

 const int N=;

 int Mod=;

 int G=;

 int a[*N],fac[*N],R[*N],ifac[*N],inv[*N],c[*N],f[*N],ans;

 int qpow(int x,int y)

 {

   int res=;

   while (y)

     {

       if (y&) res=1ll*res*x%Mod;

       x=1ll*x*x%Mod;

       y>>=;

     }

   return res;

 }

 void NTT(int *A,int len,int o)

 {int wn,w,i,j,k,x,y;

   for (i=;i<len;i++)

     if (i<R[i]) swap(A[i],A[R[i]]);

   for (i=;i<len;i<<=)

     {

       wn=qpow(G,(Mod-)/(i<<));

       if (o==-) wn=qpow(wn,Mod-);

       for (j=;j<len;j+=(i<<))

     {

       w=;

       for (k=;k<i;k++,w=1ll*w*wn%Mod)

         {

           x=A[j+k];y=1ll*w*A[j+k+i]%Mod;

           A[j+k]=x+y;

           if (A[j+k]>=Mod) A[j+k]-=Mod;

           A[j+k+i]=x-y;

           if (A[j+k+i]<) A[j+k+i]+=Mod;

         }

     }

     }

   if (o==-)

     {

       int tmp=qpow(len,Mod-);

       for (i=;i<len;i++)

     A[i]=1ll*A[i]*tmp%Mod;

     }

 }

 int main()

 {

   int i,len,lg,n;

   scanf("%d",&n);

   memset(a,,sizeof(a));

   fac[]=fac[]=ifac[]=ifac[]=inv[]=;

   for (i=;i<=n*;i++)

     {

       inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;

       fac[i]=1ll*fac[i-]*i%Mod;

       ifac[i]=1ll*ifac[i-]*inv[i]%Mod;

     }

   for (i=;i<=n;i++)

     c[i]=1ll*fac[i<<]*ifac[i]%Mod*ifac[i]%Mod*inv[i+]%Mod;

   a[]=;

   for (i=;i<=n;i++)

     if ((i&)==)

       a[i]=1ll*c[i>>]*ifac[i]%Mod;

   len=;

   while (len<=*n) len*=,lg++;

   for (i=;i<len;i++)

     R[i]=(R[i>>]>>)|((i&)<<(lg-));

   NTT(a,len,);

   for (i=;i<len;i++)

     a[i]=1ll*a[i]*a[i]%Mod;

   NTT(a,len,-);

   for (i=;i<=n;i++)

     f[i]=1ll*a[i]*fac[i]%Mod;

   for (i=;i<=n;i++)

     ans=1ll*(ans+1ll*f[i]*fac[n]%Mod*ifac[i]%Mod*ifac[n-i]%Mod)%Mod;

   printf("%d\n",ans);

   return ;

 }

巴特西