Untitled

Text Views: 22 • Oct 27, 2026 • Never expires
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int MAXN=1001005; // n+m 最大为 10^6 + 10^3,开 1001005 刚好
int T,n,m,a,b,c,d,total;
int fac[MAXN],inv[MAXN];

int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)
			res=res*a%mod;
		a=a*a%mod,
		b>>=1;
	}
	return res;
}

void pre(){
	fac[0]=1;
	for(int i=1;i<MAXN;i++)
		fac[i]=fac[i-1]*i%mod;
	inv[MAXN-1]=qpow(fac[MAXN-1],mod-2);
	for(int i=MAXN-2;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%mod;
}

int C(int n,int m){
	if(m<0||m>n)
		return 0;
	return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
	freopen("5-1.in","r",stdin);
	freopen("Jinhsi.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//用这个加速cin和cout,不得使用scanf、getchar、printf或putchar
	pre();
	cin>>T;
	while(T--){
		cin>>n>>m>>a>>b>>c>>d;
		total=C(n+m,n); // 总路径数
		
		// S1: 路径从左上绕过。前 a+d 步中,向右步数 x <= a
		int s1=0;
		for(int x=0;x<=a;x++){
			s1=(s1+C(a+d,x)*C(n+m-a-d,n-x)%mod)%mod;
		}
		
		// S2: 路径从右下绕过。前 b+c 步中,向右步数 x >= c
		int s2=0;
		for(int x=c;x<=n;x++){
			s2=(s2+C(b+c,x)*C(n+m-b-c,n-x)%mod)%mod;
		}
		
		// 左上和右下互斥,直接相加即为合法方案数
		int ans=(s1+s2)%mod;
		cout<<ans*qpow(total,mod-2)%mod<<'\n';
	}
	return 0;
}
🛡️

Ad Blocker Detected

PasteBin.site is free to use thanks to our sponsors. Please consider disabling your ad blocker or whitelisting our site to support our servers.

Learn More