[ARC012D] Don't worry. Be Together

首先每个人独立，对于每个人我们求的是这种形式的式子：

\begin{aligned} &[x^{a}y^{b}](x+\dfrac{1}{x}+y+\dfrac{1}{y})^T\\ =&[x^{a}y^{b}](x+y)^T(1+\dfrac{1}{xy})^T\\ \end{aligned}

转化成，从

(0,0)

开始要么往上要么往右走

T

步，然后还有

T

步要么不动要么往左下角走，到

(a,b)

的走法方案数。

显然前

T

步要走到

y=x-a+b

这条直线上，我们又有

x+y=T

，所以最后走到的

(x,y)

是唯一的，解得

x=\dfrac{a-b+T}{2}\\ y=\dfrac{b-a+T}{2}\\ \end{cases}$$ 最后走的 $T$ 步贡献是 ${T\choose x-a}$，所以单个人的方案数是 ${T\choose x}{T\choose x-a}$。最后把所有人的方案数乘起来即可。 对组合数的处理，可以先处理出每个数在答案中的指数，然后计算每个质数在答案中的指数。 ```cpp int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); cin>>n>>T>>mod; auto mulfac=[&](int x,int op)->void{ c[1]+=op; c[x+1]-=op; }; auto mulC=[&](int n,int m)->void{ if(n<0||m<0||n<m){ cerr<<"invalid\n"; cout<<"0\n"; exit(0); } mulfac(n,1),mulfac(m,-1),mulfac(n-m,-1); }; for(int i=1,a,b;i<=n;++i){ cin>>a>>b; a=abs(a),b=abs(b); if(a<b)swap(a,b); if((a-b+T)%2){ cout<<"0\n"; return 0; } int x=(a-b+T)/2; mulC(T,x),mulC(T,x-a); } rep(i,2,1000000){ c[i]+=c[i-1]; int x=i; for(int j=2;j*j<=x;++j){ if(x%j==0){ while(x%j==0)x/=j,a[j]+=c[i]; } } if(x!=1)a[x]+=c[i]; } int ans=1; rep(i,1,1000000)ans=1ll*ans*qp(i,a[i])%mod; cout<<ans<<'\n'; return 0; } ```

文章操作