QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#406530 | #4811. Be Careful | lexiyvv | WA | 1ms | 7812kb | C++17 | 5.2kb | 2024-05-07 13:24:53 | 2024-05-07 13:24:54 |
Judging History
answer
#pragma GCC optimize(3)
//#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define int long long
#define __int128 int
using namespace std;
const int mod=998244353;
int n,p1,p2,dp[205][205],lf[205];
int qpow[205][205],f[205],g[205],C[205][205],q[205][205];
__int128 fm2[205];
vector<int>v[205];
#define R 1
int F[205][(1<<R)+5],G[205][(1<<R)+5],t[205];
int L[(1<<20)+5],r[(1<<20)+5];
unordered_map<int,int>mp;
//const int mod2=1000000000000009;
void dfs(int x,int l){
int tg=0,cnt2=0;
for(auto y:v[x])
if(y!=l)dfs(y,x),tg=1,cnt2++;
if(!tg){
lf[x]=1;
return ;
}
vector<pair<__int128,int> >f,g;
f.push_back({0,1});
int cnt=0;
int lim=cnt2+1;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
cnt++;
continue;
}
}
lim=min(lim,(int)(sqrt((n-cnt)*2)+0.1)+cnt);
// if(x==1)return ;
// if(n>150)lim=min(lim,27ll);
sort(v[x].begin(),v[x].end(),[&](int x,int y){return v[x].size()<v[y].size();});
int tmp=0;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
int cnt=0;
for(int j=0;j<=n;j++){
if(dp[y][j]!=0)cnt++;
}
tmp=max(tmp,cnt);
}
// cout<<x<<":"<<tmp<<endl;
if(tmp<=20){
L[0]=1;
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
for(int j=0;j<n;j++){
if(dp[y][j]!=0){
for(int i=0;i<(1<<tmp);i++)
(r[i|(1<<j)]+=L[i]*dp[y][j])%=mod;
}
}
for(int i=0;i<(1<<tmp);i++)
L[i]=r[i],r[i]=0;
}
for(int i=0;i<(1<<tmp);i++){
int a=i,w=L[i];
// cout<<a<<' '<<w<<endl;
int c=0;
for(int j=0;j<=n;j++){
if(!(a&fm2[j]))
(dp[x][j]+=w*q[j-c][cnt])%=mod;
else c++;
}
}
return ;
}
for(auto y:v[x]){
if(y==l)continue;
if(lf[y]){
continue;
}
g.clear();
int cnt=0;
for(int j=0;j<=n;j++)
if(dp[y][j]!=0){
cnt++;
for(auto i:f)
g.push_back({i.first|fm2[min(j,lim)],i.second*dp[y][j]%mod});
}for(auto i:g)(mp[i.first]+=i.second)%=mod;
// if(x==1)cout<<cnt<<endl;
f.clear();
for(auto i:g){
int r=mp[i.first];
if(r)f.push_back({i.first,r}),mp[i.first]=0;
}
}
for(auto i:f){
int a=i.first,w=i.second;
int c=0;
for(int j=0;j<=n;j++){
if(!(a&fm2[j]))
(dp[x][j]+=w*q[j-c][cnt])%=mod;
else c++;
}
}
}
int p[205];
signed main(){
// freopen("tree.in","r",stdin);
// freopen("tree.out","w",stdout);
cin>>n;
fm2[0]=1;
for(int i=1;i<=n/2+1;i++)fm2[i]=fm2[i-1]*2;
f[0]=1;
for(int i=0;i<=n;i++){
int mul=1;
for(int j=0;j<=n;j++){
qpow[i][j]=mul;
(mul*=i)%=mod;
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i)C[i][j]=1;
else C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
}
}
for(int j=0;j<=n;j++){
for(int k=0;j+k<=n;k++)
(q[0][j+k]+=f[j]*qpow[n][k]%mod*C[j+k][k])%=mod;
}
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=1;j+k<=n;k++)
(g[j+k]+=f[j]*C[j+k][k])%=mod;
}
memcpy(f,g,sizeof(f));memset(g,0,sizeof(g));
for(int j=0;j<=n;j++){
for(int k=0;j+k<=n;k++)
(q[i+1][j+k]+=f[j]*qpow[n-i-1][k]%mod*C[j+k][k])%=mod;
}
}
//vector<int>a;
for(int i=1;i<n;i++){
cin>>p1>>p2;
// if(i>159)
// a.push_back(p1),a.push_back(p2);
v[p1].push_back(p2);
v[p2].push_back(p1);
}
dfs(1,0);
// if(dp[1][0]==193649645){
// for(int i=0;i<a.size();i+=2)
// cout<<a[i]<<' '<<a[i+1]<<endl;
// return 0;
// }
for(int i=0;i<=n;i++)
cout<<dp[1][i]<<endl;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7608kb
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: 1ms
memory: 5808kb
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: 1ms
memory: 7812kb
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: 5696kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5844kb
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: 0ms
memory: 5736kb
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
Wrong Answer
time: 1ms
memory: 5792kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
76009161 613174968 231680949 371606079 462267469 29375574 306720677 749077361 0 0 0
result:
wrong answer 1st numbers differ - expected: '10', found: '76009161'