乘法逆元 70pts 求助
查看原帖
乘法逆元 70pts 求助
220824
yyz1005楼主2023/4/4 08:59

讨论区的帖子都看了一遍没查出错。

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll p = 20100403;
const ll N = 1000010;
ll Get128(){
	ll x = 0,h = 1;
	char ch = getchar();
	while(!(('0'<=ch&&ch<='9')||ch=='-')) ch = getchar();
	if(ch=='-') h = -1;
	else x = ch-'0';
	ch = getchar();
	while('0'<=ch&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*h; 
} 
void print(ll x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
void write(ll x){
	if(x<0){
		putchar('-');
		x = -x;
	}
	print(x);
}
ll frac[N],inv[N];
ll fpow(ll x,ll k){
	ll res = 1;
	while(k){
		if(k&1) res = res*x%p;
		x = x*x%p;
		k>>=1;
	}
	return res;
}
void init(){
	frac[1] = 1;
	for(ll i = 2; i <= 1000000; i++){
		frac[i] = frac[i-1]*i%p;
	}
	inv[1000000] = fpow(frac[1000000],p-2);
	for(ll i = 1000000; i >= 1; i--){
		inv[i-1] = inv[i]*i%p;
	}
}
ll C(ll m,ll n){
	return frac[n]*inv[n-m]%p*inv[m]%p;
}
int main(){
	ll n,m;
	init();
	n = Get128();m = Get128();
	ll res = C(m,n+m)-C(m-1,n+m);
	res = (((res%p)+p)%p);
	write(res);
	return 0;
}
2023/4/4 08:59
加载中...