把线性求逆元改成费马小定理就过了,求助orz
查看原帖
把线性求逆元改成费马小定理就过了,求助orz
186068
我怂了楼主2023/8/8 09:39

这是AC代码

#include<bits/stdc++.h>
#define deb
#define int long long
using namespace std;
const int p=1e9+7;
int inv[8005],fac[8005],n,a[200005],b[200005],dp[4005][4005];
int ksm(int x,int y){
	int r=1;
	while(y){
		if(y&1){
			r=(r*x)%p;
		}
		y>>=1;
		x=(x*x)%p;
	}
	return r;
}
int invv(int x){
	return ksm(x,p-2)%p;
}
int C(int x,int y){
	return fac[x]*inv[y]%p*inv[x-y]%p;
} 
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fac[0]=fac[1]=1;
	inv[0]=inv[1]=1;
	for(int i=2;i<8005;i++){
		fac[i]=1ll*fac[i-1]*i%p;
		inv[i]=invv(fac[i]);
	}
	int maxa=-10000,maxb=-10000;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		dp[2002-a[i]][2002-b[i]]++;
	}
	for(int i=1;i<=4004;i++){
		for(int j=1;j<=4004;j++){
			dp[i][j]=(dp[i][j]+(dp[i-1][j]+dp[i][j-1])%p)%p;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=(1ll*ans+1ll*dp[2002+a[i]][2002+b[i]])%p;
		ans=(ans-C(2*a[i]+2*b[i],2*a[i]))%p;
		ans=(ans+p)%p;
	}
	ans=(ans+p)%p;
	cout<<(1ll*ans*500000004)%p;
	return 0;
}

这边是 WA 的

#include<bits/stdc++.h>
#define deb
#define int long long
using namespace std;
const int p=1e9+7;
int inv[8005],fac[8005],n,a[2005],b[2005],dp[4005][4005];
int C(int x,int y){
	return fac[x]*inv[y]%p*inv[x-y]%p;
} 
signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	fac[0]=fac[1]=1;
	for(int i=2;i<8005;i++){
		fac[i]=1ll*fac[i-1]*i%p;
	}
	inv[0]=inv[1]=1;
	for(int i=2;i<8005;i++){
		inv[i]=1ll*(p-p/i)*inv[p%i]%p;
	}
	for(int i=2;i<8005;i++){
		inv[i]=1ll*inv[i-1]*inv[i]%p;
	}
	int maxa=-10000,maxb=-10000;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
		maxa=max(maxa,a[i]),maxb=max(maxb,b[i]);
		dp[2002-a[i]][2002-b[i]]++;
	}
	for(int i=1;i<=4004;i++){
		for(int j=1;j<=4004;j++){
			dp[i][j]=(dp[i][j]+(dp[i-1][j]+dp[i][j-1])%p)%p;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=(1ll*ans+1ll*dp[2002+a[i]][2002+b[i]])%p;
		ans=(ans-C(2*a[i]+2*b[i],2*a[i]))%p;
		ans=(ans+p)%p;
	}
	ans=(ans+p)%p;
	cout<<(1ll*ans*500000004)%p;
	return 0;
}

2023/8/8 09:39
加载中...