QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74485 | #4811. Be Careful | Appleblue17 | RE | 4ms | 43260kb | C++14 | 3.6kb | 2023-02-01 22:55:00 | 2023-02-01 22:55:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=205,M=6e5+5,mod=998244353;
int n;
int mul[N],inv[N],S2[N][N],pre[N][N][N];
vector <int> G[N];
int ksm(int a,int x){
int tot=1;
while(x){
if(x & 1ll) tot=1ll*tot*a%mod;
a=1ll*a*a%mod;
x>>=1ll;
}
return tot;
}
void gmod(int &x){
x%=mod;
}
void init(int lim){
mul[0]=inv[0]=1;
for(int i=1;i<=lim;i++) mul[i]=1ll*mul[i-1]*i%mod;
inv[lim]=ksm(mul[lim],mod-2);
for(int i=lim-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
S2[0][0]=1;
for(int i=1;i<=lim;i++){
for(int j=1;j<=i;j++){
S2[i][j]=(S2[i-1][j-1]+1ll*S2[i-1][j]*j%mod)%mod;
}
}
// for(int c=0;c<=lim;c++){
// for(int p=0;p<=c;p++){
// for(int i=0;i<=c;i++)
// gmod(pre[c][p]+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(n-t,c-i)%mod);
// }
// }
}
int cal(int c,int p,int x){
if(pre[c][p][x]!=-1) return pre[c][p][x];
int tot=0;
for(int i=0;i<=c;i++)
gmod(tot+=1ll*inv[c-i]%mod*inv[i]%mod*S2[i][p]%mod*ksm(x,c-i)%mod);
return pre[c][p][x]=1ll*tot*mul[c]%mod*mul[p]%mod;
}
int dp[N][N],sdp[N][N];
int f[2][M],fid;
int g[2][M][N],gid;
void dfs(int u,int fa){
vector <int> A,B;
bool fl=0;
int m=0,c=0;
for(int v: G[u]){
if(v==fa) continue;
fl=1;
dfs(v,u);
m++;
if(G[v].size()==1) c++;
}
if(!fl){
for(int i=0;i<=n;i++) dp[u][i]=1;
return ;
}
long long mn=1e18;
int k;
for(int t=0;t<=n;t++){
int s=0;
for(int v: G[u]){
if(v==fa || G[v].size()==1) continue;
s+=((int)G[v].size()-1>=t);
}
if(t<=19 && s<=19) continue;
long long val=t*(m-c-s)*(1ll<<t)+m*c*s*(1ll<<(t+s));
if(val<mn) mn=val,k=t;
}
for(int v: G[u]){
if(v==fa || G[v].size()==1) continue;
if((int)G[v].size()-1<k) A.push_back(v);
else B.push_back(v);
}
fid=0;
for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
f[fid][0]=1;
for(int i=0;i<(int)A.size();i++){
int v=A[i];
fid^=1;
for(int mac=0;mac<(1<<k);mac++) f[fid][mac]=0;
for(int mac=0;mac<(1<<k);mac++){
for(int t=0;t<k;t++){
gmod(f[fid][mac | (1<<t)]+=1ll*f[fid^1][mac]*dp[v][t]%mod);
}
}
}
int l=B.size();
// cout<<u<<": "<<m<<" "<<k<<" "<<l<<'\n';
for(int mac0=0;mac0<(1<<k);mac0++){
gid=0;
for(int mac=0;mac<(1<<l);mac++)
for(int p=0;p<=m;p++)
g[gid][mac][p]=0;
g[gid][0][0]=1;
int mac0_=mac0;
for(int t=0;t<=m;t++,mac0_>>=1){
gid^=1;
for(int mac=0;mac<(1<<l);mac++)
for(int p=0;p<=c;p++)
g[gid][mac][p]=g[gid^1][mac][p];
for(int i=0;i<l;i++){
int v=B[i];
for(int mac=(1<<l)-1;mac>=0;mac--){
if(mac>>i & 1) continue;
for(int p=0;p<=c;p++){
gmod(g[gid][mac | (1<<i)][p]+=1ll*g[gid][mac][p]*dp[v][t]%mod);
}
}
}
for(int mac=0;mac<(1<<l);mac++){
for(int p=c;p>=0;p--){
gmod(g[gid][mac][p+1]+=g[gid][mac][p]);
}
}
if(!(mac0_ & 1)){
for(int mac=0;mac<(1<<l);mac++){
int val=1;
for(int i=0;i<l;i++)
if(!(mac>>i & 1)) val=1ll*val*sdp[B[i]][t+1]%mod;
for(int p=0;p<=c;p++){
int w=1ll*cal(c,p,n-t)*f[fid][mac0]%mod;
gmod(dp[u][t]+=1ll*g[gid^1][mac][p]*val%mod*w%mod);
gmod(g[gid][mac][p]+=mod-g[gid^1][mac][p]);
}
}
}
}
}
for(int i=n;i>=0;i--) gmod(sdp[u][i]=sdp[u][i+1]+dp[u][i]);
}
int main(){
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
init(N-5);
memset(pre,-1,sizeof(pre));
cin>>n;
for(int i=1;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(1,0);
for(int i=0;i<=n;i++) cout<<dp[1][i]<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 42156kb
input:
5 1 2 1 3 2 4 2 5
output:
55 127 34 0 0 0
result:
ok 6 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 42440kb
input:
8 1 2 1 3 1 4 1 5 1 6 6 7 6 8
output:
69632 265534 133905 47790 12636 1944 0 0 0
result:
ok 9 numbers
Test #3:
score: 0
Accepted
time: 4ms
memory: 41608kb
input:
3 1 2 2 3
output:
1 3 0 0
result:
ok 4 number(s): "1 3 0 0"
Test #4:
score: 0
Accepted
time: 1ms
memory: 42736kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 43260kb
input:
10 1 8 1 9 6 1 2 1 1 4 1 10 1 5 7 1 3 1
output:
1755647 612579511 359376750 200038110 104287680 49974120 21379680 7771680 2177280 362880 0
result:
ok 11 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 42216kb
input:
10 2 8 2 9 6 2 2 1 2 4 2 10 2 5 7 2 3 2
output:
114358881 100000000 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #7:
score: -100
Runtime Error
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2