[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}。最后把所有人的方案数乘起来即可。

对组合数的处理，可以先处理出每个数在答案中的指数，然后计算每个质数在答案中的指数。

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;
}