乘法逆元有误,求指点
查看原帖
乘法逆元有误,求指点
799098
chengzihan620楼主2023/12/20 16:26
#include<bits/stdc++.h>
using namespace std;
#define int long long
namespace mathmech{
	int binpow(int k,int n){
		int res=1;
		while(n){
			if(n&1)res*=k;
			k*=k;
			n>>=1;
		}
		return res;
	}
	int modpow(int k,int n,int mod){
		int res=1;
		while(n){
			if(n&1)res=res*k%mod;
			k=k*k%mod;
			n>>=1;
		}
		return res%mod;
	}
	inline int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}return x*f;}
	void Write(int x){if(x<0){x=-x;putchar('-');}if(x){Write(x/10);putchar(x%10+'0');}}
	void write(int x){Write(x);putchar('\n');}
}using namespace mathmech;    
int fac[1000001]={1,1};
const int mod=20100403;
int C(int n,int m){
	if(m==0||m==n)return 1; 
	int inv1=modpow(fac[n-m],mod-2,mod),inv2=modpow(fac[m],mod-2,mod);
	return ((fac[n]*inv1%mod)*inv2)%mod;
}
int lcs(int n,int m){
	if(m==0||m==n)return 1;
	return lcs(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
signed main(){
	int n=read(),m=read();
	for(int i=2;i<=n;i++)
		fac[i]=(fac[i-1]*i)%mod;
	cout<<(lcs(n+m,n)-lcs(n+m,m-1)+mod)%mod;
	return 0;
}
2023/12/20 16:26
加载中...