求调,代码厌氧
查看原帖
求调,代码厌氧
760291
zhangbo1000楼主2025/1/17 13:30

rt,代码厌氧。

初步推断是 4747nm<0n-m<0 了,但是加上取模后 WA。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<deque>
#include<map>
#include<random>
#include<unordered_map>
using namespace std;

namespace code{
	using ll=long long;
	using ull=unsigned long long;
	using uint=unsigned int;
#define F(i,x,y) for(int i=(x),__tt2__=(y);i<=__tt2__;i++)
#define R(i,x,y) for(int i=(x),__tt2__=(y);i>=__tt2__;i--)
#define _F(i,x,y) for(int i=(x),__tt2__=(y);i<__tt2__;i++)
#define _R(i,x,y) for(int i=(x),__tt2__=(y);i>__tt2__;i--)
#define debug(x) cout<<#x<<'='<<(x)<<endl
	constexpr int N=200005;
	int inv[N],s[N];
	ll qpow(ll a,int b,const ll& p){
		ll ans=1;
		while(b){
			if(b&1)ans=ans*a%p;
			a=a*a%p;
			b>>=1;
		}
		return ans;
	}
	void init(const int& p){
		s[1]=s[0]=1;
		F(i,2,p-1){
			s[i]=((ll)s[i-1])*i%p;
		}
		ll tmp=qpow(s[p-1],p-2,p);
		R(i,p-1,1){
			inv[i]=s[i-1]*tmp%p;
			tmp=tmp*i%p;
		}
	}
	ll safeC(const int& n,const int& m,const int& p){
		return ((ll)s[n])*inv[((ll)s[n-m])*s[m]%p]%p;
	}
	int C(const int& n,const int& m,const int& p){
		if(m==0)return 1;
		if(n<p&&m<p)return safeC(n,m,p);
		return safeC(n%p,m%p,p)*C(n/p,m/p,p)%p;
	}
	int main(){
		cin.tie(0)->sync_with_stdio(0);
		int T;
		cin>>T;
		while(T--){
			int n,m,p;
			cin>>n>>m>>p;
			init(p);
			cout<<C(n+m,n,p)<<'\n';
		}
		return 0;
	}
}
signed main(){return code::main();}
2025/1/17 13:30
加载中...