2019-Sp33-team5
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
[[Image(1007.png,700px)]]
== 总结 ==
zx2018 菜菜 B没写完 wa了，以及证明python不要轻易写，浪费了0.5h,以及A这种题，想个最稳妥的做法会方便你很多。
lyc:
pb:
[[br]]
= 补题 ==[[br]]
== 题解 ==
'''A'''
'''C'''
'''D'''
'''E'''
'''F'''
'''G'''
'''H'''
/*
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500005;
const ll mod=998244353ll;
struct node{int to,next;}q[N];
ll P[2]={31,29},M[2]={1000000007,998244353};
struct Pa{ll x[2];int i;
};
bool operator<(const Pa p1,const Pa p2)
{
if(p1.x[0]!=p2.x[0])return p1.x[0]<p2.x[0];
return p1.x[1]<p2.x[1];
}
bool operator ==(const Pa p1,const Pa p2)
{
return (p1.x[0]==p2.x[0]&&p1.x[1]==p2.x[1]);
}
int h[N],cnt=0,n;
void qxx(int x,int y)
{
cnt++;q[cnt].to=y;q[cnt].next=h[x];h[x]=cnt;
}
void clear()
{
for(int i=0;i<=n+5;i++)h[i]=0;cnt=0;
}
ll Pow(ll x,ll y,ll MOD)
{
ll all=1;
while(y)
{
if(y&1)all=1ll*all*x%MOD;
x=1ll*x*x%MOD;
y>>=1;
}
return all;
}
ll fact[N],inv[N];
ll C(int x,int y)
{
if(x == 0 || y == 0) return 1;
return fact[x]*inv[y]%mod*inv[x-y]%mod;
}
void liner(int n){
fact[0] = 1;
for(int i=1;i<=n;++i) fact[i] = fact[i-1]*i%mod;
inv[n] = Pow(fact[n],mod-2,mod);
for(int i=n-1;i>=0;--i) inv[i] = inv[i+1]*(i+1)%mod;
return ;
}
map<Pa,int>mp;
Pa f[N];
Pa dfn[N],Up[N],sta[N];
ll tot[N];
int pos[N],son[N];
ll sum[2][N],g[2][N];
bool cmp(const Pa p1,const Pa p2)
{
return p1<p2;
}
void dfs(int x,int pre)
{
for(int i=h[x];i;i=q[i].next)
{
int y=q[i].to;
if(y!=pre)dfs(y,x);
}
int num=0;
for(int i=h[x];i;i=q[i].next)
{
int y=q[i].to;
if(y!=pre)
{
son[x]++;
num++;dfn[num]=f[y];
}
}
sort(dfn+1,dfn+num+1,cmp);
ll v0=0,v1=0;
if(son[x]==0)v0=v1=1;
for(int i=1;i<=num;i++)
{
v0=(v0+1ll*g[0][i]*dfn[i].x[0]%M[0])%M[0];
v1=(v1+1ll*g[1][i]*dfn[i].x[1]%M[1])%M[1];
}
f[x].x[0]=v0;
f[x].x[1]=v1;
}
void solve(int x,int pre,Pa fa)
{
int num=0;
for(int i=h[x];i;i=q[i].next)
{
int y=q[i].to;
if(y!=pre)
{
num++;dfn[num]=f[y];dfn[num].i=y;
}
}
if(pre!=0){num++;dfn[num]=fa;dfn[num].i=0;}
sort(dfn+1,dfn+num+1,cmp);
for(int i=1;i<=num;i++)pos[dfn[i].i]=i;
ll v0=0,v1=0;
sum[0][0]=v0;sum[1][0]=v1;
for(int i=1;i<=num;i++)
{
ll tp0=1ll*g[0][i]*dfn[i].x[0]%M[0];
ll tp1=1ll*g[1][i]*dfn[i].x[1]%M[1];
v0=(v0+tp0)%M[0];
v1=(v1+tp1)%M[1];
sum[0][i]=(sum[0][i-1]+tp0)%M[0];
sum[1][i]=(sum[1][i-1]+tp1)%M[1];
}
ll val=1;
int lef=num,now=1;
for(int i=2;i<=num;i++)
{
if(dfn[i]==dfn[i-1])now++;
else
{
if(now==0)continue;
val=1ll*val*C(lef,now)%mod;
lef-=now;
now=1;
}
}
if(now)val=1ll*val*C(lef,now)%mod,lef-=now;
tot[x]=val;
sta[x].x[0]=v0;
sta[x].x[1]=v1;
for(int i=h[x];i;i=q[i].next)
{
int y=q[i].to;
if(y==pre)continue;
ll f0,f1;
int t=pos[y];
f0=(sum[0][t-1]+(sum[0][num]-sum[0][t]+M[0])%M[0]*Pow(P[0],M[0]-2,M[0])%M[0])%M[0];
f1=(sum[1][t-1]+(sum[1][num]-sum[1][t]+M[1])%M[1]*Pow(P[1],M[1]-2,M[1])%M[1])%M[1];
Up[y].x[0]=f0;
Up[y].x[1]=f1;
if(x==1&&son[x]==1)
{
Up[y].x[0]=Up[y].x[1]=1;
}
}
for(int i=h[x];i;i=q[i].next)
{
int y=q[i].to;
if(y==pre)continue;
solve(y,x,Up[y]);
}
}
set<Pa>H;
int main()
{
liner(500000);
g[0][0]=g[1][0]=1;
for(int i=1;i<=200000;i++)
for(int j=0;j<2;j++)
{
g[j][i]=g[j][i-1]*P[j]%M[j];
}
int T;
scanf("%d",&T);
while(T--)
{
H.clear();
scanf("%d",&n);
clear();
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
qxx(x,y);
qxx(y,x);
}
dfs(1,0);
Pa tmp;tmp.x[0]=tmp.x[1]=tmp.i=0;
solve(1,0,tmp);
ll ans=0;
/*cout<<" ! out: \n";
for(int i=1;i<=n;i++)
{
sta[i].O();
cout<<"num: "<<tot[i]<<endl;
}*/
for(int i=1;i<=n;i++)
if(H.find(sta[i])==H.end())
{
H.insert(sta[i]);
ans=(ans+tot[i])%mod;
}
printf("%lld\n",ans);
}
return 0;
}
/*
1
4
1 3
2 3
4 3
*/
*/Contest Information
总结
zx2018 菜菜 B没写完 wa了，以及证明python不要轻易写，浪费了0.5h,以及A这种题，想个最稳妥的做法会方便你很多。
lyc:
pb:
[[br]]
= 补题 ==[[br]]
题解
A
C
D
E
F
G
H
/*
#include
using namespace std;
typedef long long ll;
const int N=500005;
const ll mod=998244353ll;
struct node{int to,next;}q[N];
ll P[2]={31,29},M[2]={1000000007,998244353};
struct Pa{ll x[2];int i;
};
bool operator<(const Pa p1,const Pa p2)
{
if(p1.x[0]!=p2.x[0])return p1.x[0] return p1.x[1] } bool operator ==(const Pa p1,const Pa p2) { return (p1.x[0]==p2.x[0]&&p1.x[1]==p2.x[1]); } int h[N],cnt=0,n; void qxx(int x,int y) { cnt++;q[cnt].to=y;q[cnt].next=h[x];h[x]=cnt; } void clear() { for(int i=0;i<=n+5;i++)h[i]=0;cnt=0; } ll Pow(ll x,ll y,ll MOD) { ll all=1; while(y) { if(y&1)all=1ll*all*x%MOD; x=1ll*x*x%MOD; y>>=1; } return all; } ll fact[N],inv[N]; ll C(int x,int y) { if(x == 0 || y == 0) return 1; return fact[x]*inv[y]%mod*inv[x-y]%mod; } void liner(int n){ fact[0] = 1; for(int i=1;i<=n;++i) fact[i] = fact[i-1]*i%mod; inv[n] = Pow(fact[n],mod-2,mod); for(int i=n-1;i>=0;--i) inv[i] = inv[i+1]*(i+1)%mod; return ; } map Pa f[N]; Pa dfn[N],Up[N],sta[N]; ll tot[N]; int pos[N],son[N]; ll sum[2][N],g[2][N]; bool cmp(const Pa p1,const Pa p2) { return p1 } void dfs(int x,int pre) { for(int i=h[x];i;i=q[i].next) { int y=q[i].to; if(y!=pre)dfs(y,x); } int num=0; for(int i=h[x];i;i=q[i].next) { int y=q[i].to; if(y!=pre) { son[x]++; num++;dfn[num]=f[y]; } } sort(dfn+1,dfn+num+1,cmp); ll v0=0,v1=0; if(son[x]==0)v0=v1=1; for(int i=1;i<=num;i++) { v0=(v0+1ll*g[0][i]*dfn[i].x[0]%M[0])%M[0]; v1=(v1+1ll*g[1][i]*dfn[i].x[1]%M[1])%M[1]; } f[x].x[0]=v0; f[x].x[1]=v1; } void solve(int x,int pre,Pa fa) { int num=0; for(int i=h[x];i;i=q[i].next) { int y=q[i].to; if(y!=pre) { num++;dfn[num]=f[y];dfn[num].i=y; } } if(pre!=0){num++;dfn[num]=fa;dfn[num].i=0;} sort(dfn+1,dfn+num+1,cmp); for(int i=1;i<=num;i++)pos[dfn[i].i]=i; ll v0=0,v1=0; sum[0][0]=v0;sum[1][0]=v1; for(int i=1;i<=num;i++) { ll tp0=1ll*g[0][i]*dfn[i].x[0]%M[0]; ll tp1=1ll*g[1][i]*dfn[i].x[1]%M[1]; v0=(v0+tp0)%M[0]; v1=(v1+tp1)%M[1]; sum[0][i]=(sum[0][i-1]+tp0)%M[0]; sum[1][i]=(sum[1][i-1]+tp1)%M[1]; } ll val=1; int lef=num,now=1; for(int i=2;i<=num;i++) { if(dfn[i]==dfn[i-1])now++; else { if(now==0)continue; val=1ll*val*C(lef,now)%mod; lef-=now; now=1; } } if(now)val=1ll*val*C(lef,now)%mod,lef-=now; tot[x]=val; sta[x].x[0]=v0; sta[x].x[1]=v1; for(int i=h[x];i;i=q[i].next) { int y=q[i].to; if(y==pre)continue; ll f0,f1; int t=pos[y]; f0=(sum[0][t-1]+(sum[0][num]-sum[0][t]+M[0])%M[0]*Pow(P[0],M[0]-2,M[0])%M[0])%M[0]; f1=(sum[1][t-1]+(sum[1][num]-sum[1][t]+M[1])%M[1]*Pow(P[1],M[1]-2,M[1])%M[1])%M[1]; Up[y].x[0]=f0; Up[y].x[1]=f1; if(x==1&&son[x]==1) { Up[y].x[0]=Up[y].x[1]=1; } } for(int i=h[x];i;i=q[i].next) { int y=q[i].to; if(y==pre)continue; solve(y,x,Up[y]); } } set int main() { liner(500000); g[0][0]=g[1][0]=1; for(int i=1;i<=200000;i++) for(int j=0;j<2;j++) { g[j][i]=g[j][i-1]*P[j]%M[j]; } int T; scanf("%d",&T); while(T--) { H.clear(); scanf("%d",&n); clear(); for(int i=1;i { int x,y; scanf("%d%d",&x,&y); qxx(x,y); qxx(y,x); } dfs(1,0); Pa tmp;tmp.x[0]=tmp.x[1]=tmp.i=0; solve(1,0,tmp); ll ans=0; /*cout<<" ! out: \n"; for(int i=1;i<=n;i++) { sta[i].O(); cout<<"num: "< }*/ for(int i=1;i<=n;i++) if(H.find(sta[i])==H.end()) { H.insert(sta[i]); ans=(ans+tot[i])%mod; } printf("%lld\n",ans); } return 0; } /* 1 4 1 3 2 3 4 3 */ */
附加文件
- 1007.png by zx2018