15分玄关求调
查看原帖
15分玄关求调
928846
sbh2012楼主2025/2/2 19:53

rt,式子推得和题解一样,却一直15分。用的逆元求组合数。

#include<bits/stdc++.h>
using namespace std;
long long f[2000015];
long long inv[2000015];
const int mod=1000000007;
long long qsm(long long a,long long p){
    long long ans=1;
    while(p){
        if(p&1)ans=a*ans%mod;
        a=a*a%mod;
        p>>=1;
    }
    return ans;
}
long long c(long long n,long long m) {
	return f[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
	f[0]=1;
	for(long long i=1;i<=2000005;i++){
		f[i]=f[i-1]*i%mod;
	}
	inv[2000005]=qsm(f[2000005],mod-2);
	for(long long i=2000005-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
	long long t;
	cin>>t;
	while(t--){
		long long n,m,sum;
		cin>>n>>m;
		if(n==0&&m==0){
			cout<<1<<'\n';
		}else{
			sum=c(n+m,n)%mod;
			if(n>=1&&m>=1){
				sum+=(n+m-1)*2%mod*c(n+m-2,n-1)%mod;
			}
			cout<<sum<<'\n';
		}
	}
	return 0;
}
2025/2/2 19:53
加载中...