【玄关】求卡常
  • 板块学术版
  • 楼主miyachn
  • 当前回复51
  • 已保存回复52
  • 发布时间2025/7/30 11:27
  • 上次更新2025/7/30 16:26:05
查看原帖
【玄关】求卡常
1295276
miyachn楼主2025/7/30 11:27

目前1204ms,方法绝对正确

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
const ll N=200003;
ll f[N];
ll exgcd(ll a,ll b,ll&x,ll&y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	ll xp,yp;
	ll g=exgcd(b,a%b,xp,yp);
	x=yp,y=xp-a/b*yp;
	return g;
}
ll inverse(ll a,ll mod){
	ll x,y;
	ll g=exgcd(a,mod,x,y);
	if(g==1) return (x%mod+mod)%mod;
}
int main(){
//	freopen("combination.in","r",stdin);
//	freopen("combination.out","w",stdout);
	ll a,b;
	while(cin>>a>>b){
		ll m=b-2,n=a+b-4;
		f[0]=1;
		for(ll x=1;x<=max(n,m);x++) f[x]=f[x-1]*x%MOD;
		ll res=f[n];
		res=res*inverse(f[m],MOD)%MOD;
		res=res*inverse(f[n-m],MOD)%MOD;
		cout<<res<<endl;
	}
	return 0;
}
2025/7/30 11:27
加载中...