社区讨论

求助一个入门小问题

BBicycle_zxc
灌水区参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lwtzto5g
此快照首次捕获于
2024/05/31 09:16
2 年前
此快照最后确认于
2024/05/31 15:25
2 年前
查看原帖
rt，P2183 的三份代码求大佬看看有什么区别qwq
第一份（6RE 6WA 40pts）
CPP
#include<bits/stdc++.h>
using namespace std;
long long asdf=0,P,nn,mm,w[6],zxc,cnt,ct,ct2,nown;
struct node{
	long long a,b;
}Prime[1000005];
long long mods[1000005],fac[1000005],inv[1000005];
struct op{
	long long a,b;
}zhs[6];
inline long long ks(long long a,long long b){
	if(b==0){
		return 1;
	}
	if(b==1){
		return a;
	}
	long long tmp=ks(a,b/2);
	if(b%2==0){
		return tmp*tmp;
	}
	else{
		return tmp*tmp*a;
	}
}
inline void initzhs(){
	zxc=P;
	for(int i=2;i<=sqrt(zxc);i++){
		ct=0;
		if(zxc%i==0){
			Prime[++cnt].a=i;
			while(zxc%i==0){
				zxc/=i;
				ct++;
			}
			Prime[cnt].b=ct;
			ct=0;
			if(P/i!=i){
				Prime[++cnt].a=P/i;
				while(zxc%(P/i)==0){
					zxc/=(P/i);
					ct++;
				}
				Prime[cnt].b=ct;
			}
			ct=0;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(Prime[i].b!=0){
			mods[++ct2]=ks(Prime[i].a,Prime[i].b);
		}
	}
	for(int i=1;i<=mm;i++){
		zhs[i].a=nown;
		zhs[i].b=w[i];
		nown-=w[i];
	}
}
long long x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	long long tx=x;
	x=y;
	y=tx-y*(a/b); 
}
inline void init(long long mod){
	fac[0]=1;
	inv[0]=1;
	for(int i=1;i<=mod;i++){
		fac[i]=fac[i-1]*i%mod;
		exgcd(i,mod);
		inv[i]=(inv[i-1]*x%mod+mod)%mod;
		x=0;
		y=0;
	}
	return;
}
inline long long C(long long a,long long b,long long mod){
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
inline long long Lucas(long long a,long long b,long long mod){
	if(b==a||b==0){
		return 1;
	}
	if(b>a){
		return 0;
	}
	return C(a%mod,b%mod,mod)*Lucas(a/mod,b/mod,mod)%mod;
}
struct nd{
	long long mod[15],ans[15],c[15],sum=0;
	long long ji=1;
	long long n,m;
}func[6];
long long cw=0;
inline void build_up_func(long long bh){
	long long qwq;
	for(int i=1;i<=ct2;i++){
		func[bh].mod[i]=mods[i];
	}
	func[bh].n=zhs[bh].a;
	func[bh].m=zhs[bh].b;
	init(func[bh].mod[2]);
	for(int i=1;i<=ct2;i++){
		init(func[bh].mod[i]);
		func[bh].ans[i]=Lucas(func[bh].n,func[bh].m,func[bh].mod[i]);
	}
	for(int i=1;i<=ct2;i++){
		func[bh].ji*=func[bh].mod[i];
	}
	for(int i=1;i<=ct2;i++){
		qwq=func[bh].ji/func[bh].mod[i];
		exgcd(qwq,func[bh].mod[i]);
		func[bh].c[i]=qwq*x;
		x=0,y=0;
	}
	for(int i=1;i<=ct2;i++){
		func[bh].sum=(func[bh].sum+func[bh].ans[i]*func[bh].c[i]%func[bh].ji)%func[bh].ji;
		func[bh].sum%=func[bh].ji;
		func[bh].sum=(func[bh].sum%func[bh].ji+func[bh].ji)%func[bh].ji;
	}
	return;
}
long long finans=1;
int main(){
	cin>>P>>nn>>mm;
	nown=nn;
	for(int i=1;i<=mm;i++){
		cin>>w[i];
		asdf+=w[i];
	}
	if(asdf>nn){
		cout<<"Impossible"<<endl;
		exit(0);
	}
	initzhs();
	for(int i=1;i<=mm;i++){
		build_up_func(i);
	}
	for(int i=1;i<=mm;i++){
		finans*=func[i].sum;
		finans%=P;
	}
	cout<<finans<<endl;
}
/*
1000000000
1000000000
5
5
6
7
8
9
*/
/*
4 和 2 不互质
**C_3_2 = 2 mod 4** 
*/
/*
1.判无解 D
2.分解 P D
3.列出同余方程 \\逆元会炸 
4.使用 CRT 解出 C_n_m
5.乘，算答案。 
*/
第二份（6RE，5WA，9AC，45pts
CPP
#include<bits/stdc++.h>
using namespace std;
long long asdf=0,P,nn,mm,w[6],zxc,cnt,ct,ct2,nown;
struct node{
	long long a,b;
}Prime[1000005];
long long mods[1000005],fac[1000005],inv[1000005];
struct op{
	long long a,b;
}zhs[6];
inline long long ks(long long a,long long b){
	if(b==0){
		return 1;
	}
	if(b==1){
		return a;
	}
	long long tmp=ks(a,b/2);
	if(b%2==0){
		return tmp*tmp;
	}
	else{
		return tmp*tmp*a;
	}
}
inline void initzhs(){
	zxc=P;
	for(int i=2;i<=sqrt(zxc);i++){
		ct=0;
		if(zxc%i==0){
			Prime[++cnt].a=i;
			while(zxc%i==0){
				zxc/=i;
				ct++;
			}
			Prime[cnt].b=ct;
			ct=0;
			if(P/i!=i){
				Prime[++cnt].a=P/i;
				while(zxc%(P/i)==0){
					zxc/=(P/i);
					ct++;
				}
				Prime[cnt].b=ct;
			}
			ct=0;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(Prime[i].b!=0){
			mods[++ct2]=ks(Prime[i].a,Prime[i].b);
		}
	}
	for(int i=1;i<=mm;i++){
		zhs[i].a=nown;
		zhs[i].b=w[i];
		nown-=w[i];
	}
}
long long x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	long long tx=x;
	x=y;
	y=tx-y*(a/b); 
}
inline void init(long long mod){
	fac[0]=1;
	inv[0]=1;
	for(int i=1;i<=mod;i++){
		fac[i]=fac[i-1]*i%mod;
		exgcd(i,mod);
		inv[i]=(inv[i-1]*x%mod+mod)%mod;
		x=0;
		y=0;
	}
	return;
}
inline long long C(long long a,long long b,long long mod){
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
inline long long Lucas(long long a,long long b,long long mod){
	if(b==a||b==0){
		return 1;
	}
	if(b>a){
		return 0;
	}
	return C(a%mod,b%mod,mod)*Lucas(a/mod,b/mod,mod)%mod;
}
struct nd{
	long long mod[15],ans[15],c[15],sum=0;
	long long ji=1;
	long long n,m;
}func[6];
inline void build_up_func(long long bh){
	long long qwq;
	for(int i=1;i<=ct2;i++){
		func[bh].mod[i]=mods[i];
	}
	func[bh].n=zhs[bh].a;
	func[bh].m=zhs[bh].b;
	init(func[bh].mod[2]);
	for(int i=1;i<=ct2;i++){
		init(func[bh].mod[i]);
		func[bh].ans[i]=Lucas(func[bh].n,func[bh].m,func[bh].mod[i]);
	}
	for(int i=1;i<=ct2;i++){
		func[bh].ji*=func[bh].mod[i];
	}
	for(int i=1;i<=ct2;i++){
		qwq=func[bh].ji/func[bh].mod[i];
		exgcd(qwq,func[bh].mod[i]);
		func[bh].c[i]=qwq*x;
		x=0,y=0;
	}
	for(int i=1;i<=ct2;i++){
		func[bh].sum=(func[bh].sum+func[bh].ans[i]*func[bh].c[i]%func[bh].ji)%func[bh].ji;
		func[bh].sum%=func[bh].ji;
		func[bh].sum=(func[bh].sum%func[bh].ji+func[bh].ji)%func[bh].ji;
	}
	return;
}
long long finans=1;
int main(){
	cin>>P>>nn>>mm;
	nown=nn;
	for(int i=1;i<=mm;i++){
		cin>>w[i];
		asdf+=w[i];
	}
	if(asdf>nn){
		cout<<"Impossible"<<endl;
		exit(0);
	}
	initzhs();
	for(int i=1;i<=mm;i++){
		build_up_func(i);
	}
	for(int i=1;i<=mm;i++){
		finans*=func[i].sum;
		finans%=P;
	}
	cout<<finans<<endl;
}
/*
1000000000
1000000000
5
5
6
7
8
9
*/
/*
4 和 2 不互质
**C_3_2 = 2 mod 4** 
*/
/*
1.判无解 D
2.分解 P D
3.列出同余方程 \\逆元会炸 
4.使用 CRT 解出 C_n_m
5.乘，算答案。 
*/
第三份（9RE，1WA，50pts）
CPP
#include<bits/stdc++.h>
using namespace std;
long long asdf=0,P,nn,mm,w[6],zxc,cnt,ct,ct2,nown;
struct node{
	long long a,b;
}Prime[100005];
long long mods[100005],fac[100005],inv[100005];
struct op{
	long long a,b;
}zhs[6];
inline long long ks(long long a,long long b){
	if(b==0){
		return 1;
	}
	if(b==1){
		return a;
	} 
	long long tmp=ks(a,b/2);
	if(b%2==0){
		return tmp*tmp;
	}
	else{
		return tmp*tmp*a;
	}
}
inline void initzhs(){
	zxc=P;
	for(int i=2;i<=sqrt(zxc);i++){
		ct=0;
		if(zxc%i==0){
			Prime[++cnt].a=i;
			while(zxc%i==0){
				zxc/=i;
				ct++;
			}
			Prime[cnt].b=ct;
			ct=0;
			if(P/i!=i){
				Prime[++cnt].a=P/i;
				while(zxc%(P/i)==0){
					zxc/=(P/i);
					ct++;
				}
				Prime[cnt].b=ct;
			}
			ct=0;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(Prime[i].b!=0){
			mods[++ct2]=ks(Prime[i].a,Prime[i].b);
		}
	}
	for(int i=1;i<=mm;i++){
		zhs[i].a=nown;
		zhs[i].b=w[i];
		nown-=w[i];
	}
}
long long x,y;
void exgcd(int a,int b){
	if(b==0){
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	long long tx=x;
	x=y;
	y=tx-y*(a/b); 
}
inline void init(long long mod){
	fac[0]=1;
	inv[0]=1;
	for(int i=1;i<=mod;i++){
		fac[i]=fac[i-1]*i%mod;
		exgcd(i,mod);
		inv[i]=(inv[i-1]*x%mod+mod)%mod;
		x=0;
		y=0;
	}
	return;
}
inline long long C(long long a,long long b,long long mod){
	return fac[a]*inv[b]%mod*inv[a-b]%mod;
}
inline long long Lucas(long long a,long long b,long long mod){
	if(b==a||b==0){
		return 1;
	}
	if(b>a){
		return 0;
	}
	return C(a%mod,b%mod,mod)*Lucas(a/mod,b/mod,mod)%mod;
}
struct nd{
	long long mod[15],ans[15],c[15],sum=0;
	long long ji=1;
	long long n,m;
}func[6];
inline void build_up_func(long long bh){
	long long qwq;
	for(int i=1;i<=ct2;i++){
		func[bh].mod[i]=mods[i];
	}
	func[bh].n=zhs[bh].a;
	func[bh].m=zhs[bh].b;
	for(int i=1;i<=ct2;i++){
		init(func[bh].mod[i]);
		
		func[bh].ans[i]=Lucas(func[bh].n,func[bh].m,func[bh].mod[i]);
	}
	for(int i=1;i<=ct2;i++){
		func[bh].ji*=func[bh].mod[i];
	}
	for(int i=1;i<=ct2;i++){
		qwq=func[bh].ji/func[bh].mod[i];
		exgcd(qwq,func[bh].mod[i]);
		func[bh].c[i]=qwq*x;
		x=0,y=0;
	}
	for(int i=1;i<=ct2;i++){
		func[bh].sum=(func[bh].sum+func[bh].ans[i]*func[bh].c[i]%func[bh].ji)%func[bh].ji;
		func[bh].sum%=func[bh].ji;
		func[bh].sum=(func[bh].sum%func[bh].ji+func[bh].ji)%func[bh].ji;
	}
	return;
}
long long finans=1;
int main(){
	cin>>P>>nn>>mm;
	nown=nn;
	for(int i=1;i<=mm;i++){
		cin>>w[i];
		asdf+=w[i];
	}
	if(asdf>nn){
		cout<<"Impossible"<<endl;
		exit(0);
	}
	initzhs();
	for(int i=1;i<=mm;i++){
		build_up_func(i);
	}
	for(int i=1;i<=mm;i++){
		finans*=func[i].sum;;
		finans%=P;
	}
	cout<<finans<<endl;
}
/*
4 和 2 不互质
**C_3_2 = 2 mod 4** 
*/
/*
1.判无解 D
2.分解 P D
3.列出同余方程 \\逆元会炸 
4.使用 CRT 解出 C_n_m
5.乘，算答案。 
*/
比较疑惑的是第一份代码删掉第100行的 long long cw=0 就多了五分。为什么呢

回复

共 2 条回复，欢迎继续交流。

正在加载回复...