QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#74461 | #4811. Be Careful | Appleblue17 | WA | 258ms | 5652kb | C++14 | 3.6kb | 2023-02-01 21:31:42 | 2023-02-01 21:31:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=220,M=1e3+5,mod=998244353;
int n;
int mul[N],inv[N],S2[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;
}
}
}
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;
for(int v: G[u]){
if(v==fa) continue;
fl=1;
dfs(v,u);
}
// cout<<'\n';
// cout<<u<<": "<<'\n';
if(!fl){
for(int i=0;i<=n;i++) dp[u][i]=1;
// cout<<" dp: ";
// for(int i=0;i<=n;i++) cout<<dp[u][i]<<" ";
// cout<<'\n';
return ;
}
int mn=1e9,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+s<mn) mn=t+s,k=t;
}
// k=2;
int c=0;
for(int v: G[u]){
if(v==fa) continue;
if(G[v].size()==1) c++;
else if((int)G[v].size()-1<k) A.push_back(v);
else B.push_back(v);
}
// cout<<" k, c: "<<k<<" "<<c<<'\n';
// cout<<" A: ";
// for(int x: A) cout<<x<<" ";
// cout<<'\n';
// cout<<" B: ";
// for(int x: B) cout<<x<<" ";
// cout<<'\n';
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);
}
}
}
if(u==1){
cout<<"";
}
int m=A.size()+B.size()+c,l=B.size();
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;
// cout<<" g "<<mac0<<": "<<f[fid][mac0]<<'\n';
for(int t=0;t<=m;t++){
// cout<<" "<<t<<": ";
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>>t & 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=0;
for(int i=0;i<=c;i++) w=(w+1ll*mul[c]*inv[c-i]%mod*inv[i]%mod*mul[p]%mod*S2[i][p]%mod*ksm(n-t,c-i)%mod*f[fid][mac0]%mod)%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]);
// if(g[gid][mac][p]) cout<<mac<<","<<p<<"|"<<g[gid][mac][p]<<" ";
}
}
}
// cout<<'\n';
}
}
// cout<<" dp: ";
// for(int i=0;i<=n;i++) cout<<dp[u][i]<<" ";
// cout<<'\n';
for(int i=n;i>=0;i--) gmod(sdp[u][i]=sdp[u][i+1]+dp[u][i]);
}
int main(){
init(N-5);
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: 2ms
memory: 3664kb
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: 2ms
memory: 3668kb
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: 2ms
memory: 3552kb
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: 2ms
memory: 3668kb
input:
2 1 2
output:
2 1 0
result:
ok 3 number(s): "2 1 0"
Test #5:
score: 0
Accepted
time: 2ms
memory: 3680kb
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: 2ms
memory: 3660kb
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: 0
Accepted
time: 0ms
memory: 3612kb
input:
10 7 8 8 9 6 5 2 1 3 4 9 10 4 5 7 6 3 2
output:
10 1 0 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
10 3 6 2 4 4 9 8 4 2 5 10 5 3 7 2 1 1 3
output:
27510 31142 102399 0 0 0 0 0 0 0 0
result:
ok 11 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
14 10 3 6 2 2 8 3 13 1 3 1 2 3 14 4 2 9 3 12 3 2 5 7 2 11 3
output:
930962871 780146137 253920328 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 15 numbers
Test #10:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
20 7 6 2 6 5 1 17 12 9 13 12 18 3 2 9 1 2 1 12 6 10 9 14 2 4 1 6 8 11 2 16 9 13 19 8 15 20 5
output:
572808214 694156482 763085092 958730326 465749894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 21 numbers
Test #11:
score: 0
Accepted
time: 2ms
memory: 3732kb
input:
21 6 12 11 13 1 7 8 14 1 18 5 4 1 2 16 11 21 1 9 10 15 17 1 9 1 8 1 20 1 3 1 4 19 16 11 1 15 10 3 6
output:
778184256 242901486 277265229 855621813 564317020 918444623 408876720 314039448 593931360 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 22 numbers
Test #12:
score: 0
Accepted
time: 2ms
memory: 3744kb
input:
22 20 21 9 12 6 10 19 10 16 10 10 11 8 7 13 12 21 22 19 20 14 13 7 6 8 9 15 14 2 5 18 6 5 6 3 2 16 17 2 1 3 4
output:
142157709 5878180 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 23 numbers
Test #13:
score: 0
Accepted
time: 2ms
memory: 3696kb
input:
23 6 10 4 2 6 9 15 20 10 15 3 6 17 23 1 3 16 22 19 14 17 12 7 11 18 13 11 16 5 3 8 5 10 14 8 12 9 13 4 7 1 2 15 21
output:
7619809 175546557 7936610 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 24 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 3632kb
input:
24 7 10 2 5 2 1 17 20 1 4 16 13 7 4 19 16 23 20 11 8 10 13 1 3 22 19 5 8 3 6 17 14 21 18 24 21 18 15 9 6 9 12 14 11 15 12
output:
24 576 15025 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #15:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
24 22 16 17 11 15 9 13 7 8 2 1 3 5 1 6 12 9 3 14 8 21 15 17 23 19 13 7 1 24 18 2 1 5 11 1 4 4 10 18 12 20 14 10 16 1 6
output:
24 7962624 236177977 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
result:
ok 25 numbers
Test #16:
score: 0
Accepted
time: 258ms
memory: 3752kb
input:
200 1 199 95 1 1 75 177 1 66 1 157 1 85 1 1 193 1 26 8 1 38 1 151 1 1 56 63 1 1 138 1 59 190 1 1 36 1 120 156 1 115 1 1 118 171 1 6 1 113 1 20 1 83 1 1 176 33 1 153 1 1 169 22 1 1 159 1 27 87 1 1 129 1 44 174 1 1 93 77 1 1 122 1 125 1 23 1 81 112 1 173 1 1 51 32 1 96 1 184 1 116 1 67 1 1 94 1 104 19...
output:
211917199 369375874 201944418 582671162 183066248 639389350 952947539 137147613 216366713 398936459 73236543 354059031 727857197 121548413 610762100 573534011 706945631 286154195 226699593 267771858 823273748 233587424 176942776 226493975 707601105 339075191 694353149 944734662 932707579 934386415 4...
result:
ok 201 numbers
Test #17:
score: 0
Accepted
time: 253ms
memory: 3832kb
input:
200 2 199 95 2 2 75 177 2 66 2 157 2 85 2 2 193 2 26 8 2 38 2 151 2 2 56 63 2 2 138 2 59 190 2 2 36 2 120 156 2 115 2 2 118 171 2 6 2 113 2 20 2 83 2 2 176 33 2 153 2 2 169 22 2 2 159 2 27 87 2 2 129 2 44 174 2 2 93 77 2 2 122 2 125 2 23 2 81 112 2 173 2 2 51 32 2 96 2 184 2 116 2 67 2 2 94 2 104 19...
output:
356210711 85910356 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 201 numbers
Test #18:
score: 0
Accepted
time: 2ms
memory: 4100kb
input:
200 198 199 95 94 74 75 177 176 66 65 157 156 85 84 192 193 25 26 8 7 38 37 151 150 55 56 63 62 137 138 58 59 190 189 35 36 119 120 156 155 115 114 117 118 171 170 6 5 113 112 20 19 83 82 175 176 33 32 153 152 168 169 22 21 158 159 26 27 87 86 128 129 43 44 174 173 92 93 77 76 121 122 124 125 22 23 ...
output:
200 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 201 numbers
Test #19:
score: 0
Accepted
time: 1ms
memory: 4072kb
input:
199 176 177 115 116 47 48 29 30 120 119 7 8 93 94 158 159 118 117 28 29 185 186 133 132 24 25 76 77 55 54 68 69 96 95 65 66 172 171 114 113 127 128 91 92 106 107 70 71 135 136 83 82 187 188 146 147 23 22 36 37 195 196 166 165 81 80 109 108 8 9 21 20 41 42 125 124 46 47 87 86 133 134 38 37 174 173 12...
output:
1 199 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200 numbers
Test #20:
score: 0
Accepted
time: 2ms
memory: 3924kb
input:
200 28 56 82 165 53 107 94 188 67 134 51 102 69 139 18 37 10 20 33 66 179 89 156 78 53 106 93 186 113 56 9 19 8 16 65 130 33 16 41 82 37 74 197 98 26 53 18 36 195 97 30 60 132 66 81 162 61 30 40 81 26 52 168 84 79 39 128 64 27 54 68 136 91 45 40 20 122 61 108 54 3 6 118 59 91 182 177 88 15 31 133 66...
output:
115157040 769068498 218666068 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 201 numbers
Test #21:
score: 0
Accepted
time: 2ms
memory: 3912kb
input:
200 51 153 118 39 23 68 26 9 163 54 7 2 21 62 174 58 125 42 50 150 15 46 32 95 186 62 53 158 7 22 29 88 165 55 47 140 9 3 18 6 20 59 131 44 90 30 149 50 35 12 11 32 15 5 4 13 110 37 160 53 3 10 51 152 154 51 37 12 94 31 119 40 49 146 196 65 16 48 46 138 4 12 116 39 74 25 27 81 105 35 61 182 18 55 19...
output:
96831322 243739289 839032182 347339046 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 201 numbers
Test #22:
score: 0
Accepted
time: 2ms
memory: 3956kb
input:
200 4 1 40 159 6 22 16 65 7 29 7 2 10 39 103 26 24 97 180 45 24 6 47 186 50 200 140 35 15 61 10 38 127 32 93 23 18 73 185 46 23 91 29 115 126 32 35 9 120 30 22 86 20 79 7 27 35 139 148 37 26 105 18 70 198 50 190 48 136 34 147 37 25 98 39 155 40 158 199 50 67 17 75 19 8 2 109 27 160 40 176 44 23 90 1...
output:
868579713 768926703 473674519 835466001 35818891 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
ok 201 numbers
Test #23:
score: 0
Accepted
time: 1ms
memory: 4020kb
input:
200 124 21 53 9 5 28 33 199 145 24 20 119 24 140 31 5 86 15 30 176 12 69 172 29 116 20 14 3 11 66 3 15 75 13 13 76 144 24 79 13 72 12 80 14 1 7 70 12 23 135 178 30 33 197 30 179 9 55 27 159 18 3 25 151 11 62 18 107 82 14 30 180 23 138 31 182 16 94 97 16 93 16 173 29 32 190 10 2 8 2 18 104 6 35 111 1...
output:
298503373 243520600 324348437 233414660 209600209 600025942 504289019 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 201 numbers
Test #24:
score: -100
Wrong Answer
time: 5ms
memory: 5652kb
input:
200 6 61 5 47 14 141 16 161 144 15 48 5 115 12 147 15 175 18 19 186 86 9 75 8 109 11 158 16 169 17 62 7 135 14 97 10 1 6 3 23 9 87 42 5 73 8 20 200 152 16 14 132 90 9 21 2 4 34 4 37 181 18 71 7 1 9 84 9 180 18 56 6 127 13 6 52 12 121 137 14 7 64 11 105 156 16 15 146 6 59 1 4 83 9 8 74 6 60 69 7 10 1...
output:
290634446 222370911 503586247 593548263 144507253 475827448 233112830 567218231 270237508 31506702 833404556 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
result:
wrong answer 1st numbers differ - expected: '107615921', found: '290634446'