CF1931G题解

快斗游鹿 · 2024-02-16 16:06:25 · 题解

观察拼图形状。可以发现如果不考虑第三块和第四块拼图，第一块拼图和第二块拼图一定是交替出现的。也就意味着如果 \lvert c_1-c_2 \rvert>1，一定无解。

然后分类讨论：

如果 c_1=c_2：

以第一块拼图打头，如下图：

可以发现第三块拼图有 c_1 个空位可填，第四块拼图有 c_2+1 个空位可填。

可以发现这个问题就相当于有 y 个盒子，要放入 x 个球，可以为空的方案数，由插板法易知答案为 \tbinom{x+y-1}{y-1}，记 g(x,y)=\tbinom{x+y-1}{y-1}。那么该情况的答案就是 g(c_3,c_1)\times g(c_4,c_2+1)。

同理，如果以第二块拼图打头，那么第三块拼图有 c_1+1 个空位可填，第四块拼图有 c_2 个空位可填，答案就是 g(c_3,c_1+1)\times g(c_4,c_2)。

如果 \lvert c_1-c_2 \rvert=1：

如图：

可以发现第三块和第四块拼图都有 \max(c_1,c_2) 个空位可填，设 a=\max(c_1,c_2)。

那么方案数就是 g(c_3,a)\times g(c_4,a)。然后就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=8e6+5;
const int mod=998244353;
int T,a,b,c,d;
int fac[N],inv[N];
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int C(int nn,int mm){
    if(!mm)return 1;
    if(nn<mm)return 0;
    return fac[nn]%mod*inv[mm]%mod*inv[nn-mm]%mod;
}
signed main(){
    //freopen("std.in","r",stdin);
    T=read();
    inv[0]=1;inv[1]=1;fac[0]=1;fac[1]=1;
    for(int i=2;i<=8e6;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=8e6;i++)inv[i]=inv[i-1]*inv[i]%mod;
    for(int i=2;i<=8e6;i++)fac[i]=fac[i-1]*i%mod;
    while(T--){
        a=read();b=read();c=read();d=read();
        if(a==b){
            //a个c,b+1个d
            //a+1个c,b个d 
            if(!a)puts(c&&d?"0":"1");
            else printf("%lld\n",(C(a+c-1,a-1)*C(b+d,b)%mod+C(b+d-1,b-1)*C(a+c,a))%mod); 
        }
        else if(abs(a-b)==1){
            if(a<b)swap(a,b);
            printf("%lld\n",C(a+c-1,a-1)*C(a+d-1,a-1)%mod);
        }
        else puts("0");
    }
    return 0;
}