社区讨论

求助,关于 1LL

学术版参与者 3已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@lq7tzzuo
此快照首次捕获于
2023/12/16 17:03
2 年前
此快照最后确认于
2023/12/16 19:17
2 年前
查看原帖
这份代码:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,MOD;
vector<int> G[200031];
int dp1[100031],dp2[100031];
int pre[100031],lst[100031];

void dfs1(int x,int fa){
	vector<int> son; dp1[x]=1;
	for(auto i:G[x]){
		if(i==fa) continue;
		dfs1(i,x);
		dp1[x]=dp1[x]*(dp1[i]+1)%MOD;
		son.push_back(i);
	}
	int npre=1,nlst=1;
	for(int i=0;i<son.size();i++)
		pre[son[i]]=npre,npre=npre*(dp1[son[i]]+1)%MOD;
	for(int i=son.size()-1;i>=0;i--)
		lst[son[i]]=nlst,nlst=nlst*(dp1[son[i]]+1)%MOD;
}
void dfs2(int x,int fa){
	if(fa==-1) dp2[x]=1;
	else dp2[x]=dp2[fa]*(pre[x]*lst[x]%MOD+1)%MOD;
	for(auto i:G[x])
		if(i!=fa) dfs2(i,x);
}

signed main(){
	cin>>n>>MOD;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs1(1,-1),dfs2(1,-1);
	for(int i=1;i<=n;i++) cout<<dp1[i]*dp2[i]%MOD<<'\n';
	return 0;
}
开了 long long,却过不了样例一。
但是这份代码:
CPP
#include<bits/stdc++.h>
using namespace std;

int n,MOD;
vector<int> G[100031];
int dp1[100031],dp2[100031];
int pre[100031],lst[100031];

void dfs1(int x,int fa){
	vector<int> son; dp1[x]=1;
	for(auto i:G[x]){
		if(i==fa) continue;
		dfs1(i,x);
		dp1[x]=1LL*dp1[x]*(dp1[i]+1)%MOD;
		son.push_back(i);
	}
	int npre=1,nlst=1;
	for(int i=0;i<son.size();i++)
		pre[son[i]]=npre,npre=1LL*npre*(dp1[son[i]]+1)%MOD;
	for(int i=son.size()-1;i>=0;i--)
		lst[son[i]]=nlst,nlst=1LL*nlst*(dp1[son[i]]+1)%MOD;
}
void dfs2(int x,int fa){
	if(fa==-1) dp2[x]=1;
	else dp2[x]=(1LL*dp2[fa]*(1LL*pre[x]*lst[x]%MOD)%MOD+1)%MOD;
	for(auto i:G[x])
		if(i!=fa) dfs2(i,x);
}

signed main(){
	cin>>n>>MOD;
	for(int i=1,u,v;i<n;i++)
		cin>>u>>v,G[u].push_back(v),G[v].push_back(u);
	dfs1(1,-1),dfs2(1,-1);
	for(int i=1;i<=n;i++) cout<<1LL*dp1[i]*dp2[i]%MOD<<'\n';
	return 0;
}
没开 long long 但加了 1LL,AC。
求助各位大佬这是为什么 qwq。

回复

3 条回复,欢迎继续交流。

正在加载回复...