社区讨论
求助,关于 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 条回复,欢迎继续交流。
正在加载回复...