[atAGC051D]C4

考虑将两次移动作为一个整体，两次移动的效果分为：$s-u$、$u-s$和原地不动

对于从$s$回到$s$路径，必然有前两种效果使用次数相同，假设都为$i$（枚举），那么原地不动的次数$j=\frac{a+b+c+d}{2}-i$

$2i$次中使用$t$来移动的次数$x$，那么使用$v$的次数即为$y=2i-x$，之后这里有$2i\choose x$种方案（注意这$2i$次操作顺序已经确定，必然是$s-u$再$u-s$循环排列）

考虑原地不动的贡献：在$s$上原地不动的$\frac{a+d}{2}-i$次（这里分子要减去$x+y$，即$2i$）划分为了$i+1$段（可以为空，通过插板法计算），且内部有$\frac{a+d}{2}-i\choose \frac{a-x}{2}$种排列，在$t$上原地不动的类似

综合上述，即$[b+c=0]{a+d\choose a}+\sum_{i=1}^{\frac{a+b+c+d}{2}}\sum_{x=0}^{2i}{2i\choose x}{\frac{a+d}{2}\choose i}{\frac{a+d}{2}-i\choose \frac{a-x}{2}}{\frac{b+c}{2}-1\choose i-1}{\frac{b+c}{2}-i\choose \frac{b-x}{2}}$

对后半部分化简，即$(\frac{a+d}{2})!(\frac{b+c}{2}-1)!\sum_{i=0}^{\frac{a+b+c+d}{2}}\frac{(2i)!}{i!(i-1)!}\sum_{x=0}^{2i}\frac{1}{x!(\frac{a-x}{2})!(\frac{b-x}{2})!(2i-x)!(\frac{d-(2i-x)}{2})!(\frac{c-(2i-x)}{2}))}$

关于$x$的枚举是一个多项式乘法的形式，即记$h(x)=\frac{1}{x!(\frac{a-x}{2})!(\frac{b-x}{2})!}$且$g(x)=\frac{1}{x!(\frac{d-x}{2})!(\frac{c-x}{2})!}$，考虑$f(x)=g(x)h(x)$的$k$次项系数即为$i=\frac{k}{2}$时后面的值，用ntt计算即可，时间复杂度为$o(n\log_{2}n)$（其中$n=a+b+c+d$）

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5000005

 4 #define mod 998244353

 5 int n,a,b,c,d,ans,fac[N],inv[N],rev[N],g[N],f[N];

 6 int C(int n,int m){

 7     return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;

 8 }

 9 int ksm(int n,int m){

10     if (!m)return 1;

11     int s=ksm(n,m>>1);

12     s=1LL*s*s%mod;

13     if (m&1)s=1LL*s*n%mod;

14     return s;

15 }

16 void ntt(int *a,int p){

17     for(int i=0;i<(1<<22);i++)

18         if (i<rev[i])swap(a[i],a[rev[i]]);

19     for(int i=2;i<=(1<<22);i*=2){

20         int s=ksm(3,(mod-1)/i);

21         if (p)s=ksm(s,mod-2);

22         for(int j=0;j<(1<<22);j+=i)

23             for(int k=0,ss=1;k<(i>>1);k++,ss=1LL*ss*s%mod){

24                 int x=a[j+k],y=1LL*a[j+k+(i>>1)]*ss%mod;

25                 a[j+k]=(x+y)%mod;

26                 a[j+k+(i>>1)]=(x+mod-y)%mod;

27             }

28     }

29     if (p){

30         int s=ksm((1<<22),mod-2);

31         for(int i=0;i<(1<<22);i++)a[i]=1LL*a[i]*s%mod;

32     }

33 }

34 int main(){

35     fac[0]=inv[0]=inv[1]=1;

36     for(int i=1;i<N-4;i++)fac[i]=1LL*fac[i-1]*i%mod;

37     for(int i=2;i<N-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

38     for(int i=1;i<N-4;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;

39     scanf("%d%d%d%d",&a,&b,&c,&d);

40     if (((a+d)&1)||((b+c)&1)||((a+b)&1)){

41         printf("0");

42         return 0;

43     }

44     if ((!b)&&(!c)){

45         printf("%d",C(a+d,a));

46         return 0;

47     }

48     n=a+b+c+d;

49     for(int i=0;i<(1<<22);i++)rev[i]=(rev[i>>1]>>1)+((i&1)<<21);

50     for(int i=0;i<=min(a,b);i++)

51         if ((a-i)%2==0)f[i]=1LL*inv[i]*inv[(a-i)/2]%mod*inv[(b-i)/2]%mod;

52     for(int i=0;i<=min(c,d);i++)

53         if ((c-i)%2==0)g[i]=1LL*inv[i]*inv[(c-i)/2]%mod*inv[(d-i)/2]%mod;

54     ntt(g,0);

55     ntt(f,0);

56     for(int i=0;i<(1<<22);i++)f[i]=1LL*f[i]*g[i]%mod;

57     ntt(f,1);

58     for(int i=1;i<=(b+c)/2;i++)ans=(ans+1LL*fac[2*i]*inv[i]%mod*inv[i-1]%mod*f[2*i])%mod;

59     ans=1LL*ans*fac[(a+d)/2]%mod*fac[(b+c)/2-1]%mod;

60     printf("%d",ans);

61 }

巴特西

[atAGC051D]C4

最新文章

热门文章