QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#341088 | #6223. 神经网络 | DaiRuiChen007 | 100 ✓ | 183ms | 396196kb | C++17 | 2.3kb | 2024-02-29 15:33:22 | 2024-02-29 15:33:23 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MOD=998244353;
int fac[MAXN],ifac[MAXN];
int ksm(int a,int b=MOD-2,int p=MOD) {
int ret=1;
for(;b;a=1ll*a*a%p,b>>=1) if(b&1) ret=1ll*ret*a%p;
return ret;
}
int C[MAXN][MAXN],co[MAXN][MAXN];
//co: i element -> j set
vector <int> G[MAXN];
int f[MAXN][MAXN],g[MAXN][MAXN],h[MAXN][MAXN]; //deg = 0,1,2
int tf[MAXN],tg[MAXN],th[MAXN],siz[MAXN];
void dfs(int u,int fz) {
f[u][0]=1,siz[u]=1;
for(int v:G[u]) if(v^fz) {
dfs(v,u);
memset(tf,0,sizeof(tf));
memset(tg,0,sizeof(tg));
memset(th,0,sizeof(th));
for(int i=0;i<=siz[u];++i) for(int j=0;j<=siz[v];++j) {
int x=(f[v][j]+2ll*g[v][j]+2ll*h[v][j])%MOD;
tf[i+j+1]=(tf[i+j+1]+1ll*f[u][i]*x)%MOD;
tg[i+j+1]=(tg[i+j+1]+1ll*g[u][i]*x)%MOD;
th[i+j+1]=(th[i+j+1]+1ll*h[u][i]*x)%MOD;
tg[i+j]=(tg[i+j]+1ll*f[u][i]*(f[v][j]+g[v][j]))%MOD;
th[i+j]=(th[i+j]+1ll*g[u][i]*(f[v][j]+g[v][j]))%MOD;
}
siz[u]+=siz[v];
memcpy(f[u],tf,sizeof(f[u]));
memcpy(g[u],tg,sizeof(g[u]));
memcpy(h[u],th,sizeof(h[u]));
}
}
int wys[MAXN],dp[MAXN],tdp[MAXN]; //dp to i elements
signed main() {
for(int i=fac[0]=1;i<MAXN;++i) ifac[i]=ksm(fac[i]=1ll*fac[i-1]*i%MOD)%MOD;
for(int i=0;i<MAXN;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
for(int i=1;i<MAXN;++i) for(int j=1;j<=i;++j) co[i][j]=1ll*fac[i]*ifac[j]%MOD*C[i-1][j-1]%MOD;
int n,m,tot=0; dp[0]=1;
scanf("%d",&m);
for(int t=1;t<=m;++t) {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
G[i].clear(),siz[i]=0;
memset(f[i],0,sizeof(f[i]));
memset(g[i],0,sizeof(g[i]));
memset(h[i],0,sizeof(h[i]));
}
for(int i=1,u,v;i<n;++i) {
scanf("%d%d",&u,&v);
G[u].push_back(v),G[v].push_back(u);
}
dfs(1,0);
memset(wys,0,sizeof(wys));
for(int i=1;i<=n;++i) {
int v=(f[1][i-1]+2ll*g[1][i-1]+2ll*h[1][i-1])%MOD;
for(int j=i;j>=1;--j) {
wys[j]=(wys[j]+((i-j)&1?-1ll:1ll)*v*co[i][j])%MOD;
}
}
for(int i=1;i<=n;++i) if(wys[i]<0) wys[i]+=MOD;
memset(tdp,0,sizeof(tdp));
for(int i=0;i<=tot;++i) for(int j=1;j<=n;++j) {
tdp[i+j]=(tdp[i+j]+1ll*dp[i]*wys[j])%MOD;
}
tot+=n;
memcpy(dp,tdp,sizeof(dp));
}
int ans=0;
for(int i=1;i<=tot;++i) ans=(ans+1ll*dp[i]*fac[i-1])%MOD;
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 43ms
memory: 170824kb
input:
3 4 2 1 4 3 3 1 5 4 5 3 4 3 2 1 2 1
output:
32824
result:
ok 1 number(s): "32824"
Test #2:
score: 5
Accepted
time: 42ms
memory: 171160kb
input:
4 3 1 2 3 1 3 2 1 3 1 5 3 4 5 4 2 3 2 1 4 2 1 3 2 4 3
output:
212823345
result:
ok 1 number(s): "212823345"
Test #3:
score: 5
Accepted
time: 21ms
memory: 170948kb
input:
300 1 1 2 1 2 2 2 1 2 2 1 2 1 2 1 2 2 1 1 2 1 2 1 2 2 1 2 1 2 2 1 2 2 1 2 2 2 1 1 1 1 1 1 2 2 1 1 1 1 2 2 1 2 2 1 1 2 2 1 2 1 2 1 2 1 2 1 1 2 2 1 1 1 2 1 2 2 1 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 1 2 1 2 1 1 2 1 2 2 1 2 2 2 1 2 1 2 2 1 2 2 2 1 2 1 2 2 1 2 2 1 2 1 1 2 2 1 2 2 1 1 2 2 1 1 1 2 1 2 1 1 2 1 2 ...
output:
354818429
result:
ok 1 number(s): "354818429"
Test #4:
score: 5
Accepted
time: 27ms
memory: 170852kb
input:
300 2 2 1 2 1 2 3 1 2 2 3 2 2 1 1 2 1 2 2 2 1 1 2 1 2 3 1 2 3 1 3 3 1 2 1 1 2 2 1 3 1 3 1 2 3 3 1 1 2 1 1 2 1 2 2 2 1 2 2 1 2 1 2 2 2 1 2 2 1 1 2 1 2 2 1 2 3 1 2 1 3 3 3 1 2 1 3 1 2 3 1 3 1 3 1 2 1 3 2 1 1 3 2 2 1 3 3 2 1 2 1 3 2 3 2 1 3 1 2 1 3 1 1 3 1 2 1 3 1 3 1 3 1 2 3 2 1 1 3 3 3 1 1 2 3 1 2 2 ...
output:
163346936
result:
ok 1 number(s): "163346936"
Test #5:
score: 5
Accepted
time: 43ms
memory: 170616kb
input:
300 3 1 2 3 1 2 1 2 2 1 2 2 2 1 3 3 1 1 2 1 2 1 2 1 1 2 2 1 2 2 1 3 2 3 1 2 2 2 1 2 2 1 1 2 1 2 3 1 3 2 1 1 3 3 1 2 1 2 2 1 3 3 2 1 2 1 1 2 2 1 1 1 3 2 1 1 3 3 3 2 1 2 3 2 1 1 3 3 1 2 3 1 2 2 1 3 1 2 3 2 3 1 2 1 3 2 2 1 3 1 3 2 1 3 2 1 3 2 2 2 1 1 2 1 2 2 2 1 3 3 1 2 1 1 3 1 2 3 1 3 3 2 1 2 2 2 1 2 ...
output:
623176801
result:
ok 1 number(s): "623176801"
Test #6:
score: 5
Accepted
time: 35ms
memory: 174500kb
input:
300 3 1 2 3 2 3 2 1 3 1 2 1 2 2 1 2 2 2 1 1 1 3 1 2 3 2 1 2 1 2 3 1 2 3 1 2 1 2 1 2 2 1 3 3 2 1 2 3 3 1 2 1 2 1 2 1 3 3 2 1 2 3 2 1 3 2 3 3 2 2 1 1 1 3 1 2 1 3 3 3 1 1 2 3 2 1 3 1 2 2 1 2 2 1 1 1 3 1 2 1 3 1 1 3 2 1 1 3 2 1 2 1 2 2 1 1 2 1 2 2 2 1 3 2 1 3 1 1 2 2 1 2 2 1 2 2 1 2 2 1 2 1 2 2 1 2 2 1 ...
output:
220324606
result:
ok 1 number(s): "220324606"
Test #7:
score: 5
Accepted
time: 52ms
memory: 173744kb
input:
50 50 6 2 19 30 13 4 16 17 26 10 11 37 2 19 38 1 22 28 8 50 16 35 41 10 21 17 4 2 5 49 43 17 1 27 20 8 23 34 42 34 7 6 23 8 2 9 14 5 14 16 44 28 11 29 8 1 19 47 6 46 32 2 11 40 15 3 14 39 2 5 8 18 17 31 20 45 11 4 24 3 1 10 25 21 18 22 33 36 2 3 2 12 33 10 1 2 30 48 50 1 28 21 1 19 1 8 1 1 17 41 1 1...
output:
634594980
result:
ok 1 number(s): "634594980"
Test #8:
score: 5
Accepted
time: 55ms
memory: 173580kb
input:
50 50 5 6 30 29 12 13 17 16 25 26 37 36 19 18 37 38 28 27 39 50 35 34 41 29 20 21 3 4 22 49 43 38 27 26 19 20 34 33 42 38 6 7 22 23 9 8 13 14 16 15 44 41 29 28 7 8 28 47 9 46 31 32 40 39 14 15 39 38 5 4 18 17 31 30 20 45 10 11 23 24 10 9 24 25 22 21 36 35 3 2 12 11 32 33 2 1 15 48 50 27 28 21 20 19 ...
output:
33435632
result:
ok 1 number(s): "33435632"
Test #9:
score: 5
Accepted
time: 43ms
memory: 173448kb
input:
50 50 5 6 30 29 12 13 17 16 25 26 37 36 19 18 37 38 28 27 29 50 35 34 41 28 20 21 3 4 36 49 43 12 27 26 19 20 34 33 42 10 6 7 22 23 9 8 13 14 16 15 44 42 29 28 7 8 2 47 38 46 31 32 40 39 14 15 39 38 5 4 18 17 31 30 32 45 10 11 23 24 10 9 24 25 22 21 36 35 3 2 12 11 32 33 2 1 42 48 50 28 1 8 21 3 19 ...
output:
642271217
result:
ok 1 number(s): "642271217"
Test #10:
score: 5
Accepted
time: 44ms
memory: 182372kb
input:
50 50 6 2 14 30 13 4 7 17 26 13 5 37 9 19 38 34 8 28 19 50 22 35 41 32 21 15 4 1 35 49 43 21 9 27 20 1 31 34 42 40 7 1 23 19 1 9 14 11 15 16 44 19 6 29 8 7 10 47 40 46 32 5 37 40 15 10 4 39 1 5 11 18 26 31 40 45 11 10 24 13 7 10 25 1 2 22 11 36 1 3 9 12 33 19 1 2 15 48 50 28 27 19 21 17 19 7 8 17 15...
output:
910594026
result:
ok 1 number(s): "910594026"
Test #11:
score: 5
Accepted
time: 140ms
memory: 259176kb
input:
59 1500 1206 1205 1192 1191 702 703 1412 1411 1060 1061 470 469 707 708 1133 1132 166 165 1197 1196 1215 1214 1030 1031 362 363 4 3 1167 1168 793 794 1418 1417 1195 1196 644 645 721 722 590 591 828 827 421 422 580 579 1186 1187 194 193 553 552 1430 1431 972 973 1398 1397 354 353 913 914 544 545 586 ...
output:
756407276
result:
ok 1 number(s): "756407276"
Test #12:
score: 5
Accepted
time: 132ms
memory: 269628kb
input:
59 1500 1206 1205 1192 1191 702 703 1412 1411 1060 1061 470 469 707 708 1133 1132 166 165 1197 1196 1215 1214 1030 1031 362 363 4 3 1167 1168 793 794 1418 1417 1195 1196 644 645 721 722 590 591 828 827 421 422 580 579 1186 1187 194 193 553 552 1430 1431 972 973 1398 1397 354 353 913 914 544 545 586 ...
output:
799821558
result:
ok 1 number(s): "799821558"
Test #13:
score: 5
Accepted
time: 130ms
memory: 272088kb
input:
59 1500 1206 1205 1192 1191 702 703 1412 1411 1060 1061 470 469 707 708 1133 1132 166 165 1197 1196 1215 1214 1030 1031 362 363 4 3 1167 1168 793 794 1418 1417 1195 1196 644 645 721 722 590 591 828 827 421 422 580 579 1186 1187 194 193 553 552 1430 1431 972 973 1398 1397 354 353 913 914 544 545 586 ...
output:
332021746
result:
ok 1 number(s): "332021746"
Test #14:
score: 5
Accepted
time: 148ms
memory: 273368kb
input:
59 1500 1206 1205 1192 1191 702 703 1412 1411 1060 1061 470 469 707 708 1133 1132 166 165 1197 1196 1215 1214 1030 1031 362 363 4 3 1167 1168 793 794 1418 1417 1195 1196 644 645 721 722 590 591 828 827 421 422 580 579 1186 1187 194 193 553 552 1430 1431 972 973 1398 1397 354 353 913 914 544 545 586 ...
output:
458452660
result:
ok 1 number(s): "458452660"
Test #15:
score: 5
Accepted
time: 143ms
memory: 276480kb
input:
109 1500 1205 1206 1191 1192 703 701 1411 1412 1061 1059 469 470 708 707 1131 1133 165 166 1195 1197 1213 1215 1031 1029 363 361 3 4 1168 1167 794 793 1417 1418 1196 1195 645 643 722 721 591 589 827 828 422 421 579 580 1187 1185 193 194 551 553 1431 1429 973 971 1397 1398 353 354 914 913 545 543 587...
output:
550433177
result:
ok 1 number(s): "550433177"
Test #16:
score: 5
Accepted
time: 129ms
memory: 286084kb
input:
109 1500 1205 1206 1191 1192 703 701 1411 1412 1061 1059 469 470 708 707 1131 1133 165 166 1195 1197 1213 1215 1031 1029 363 361 3 4 1168 1167 794 793 1417 1418 1196 1195 645 643 722 721 591 589 827 828 422 421 579 580 1187 1185 193 194 551 553 1431 1429 973 971 1397 1398 353 354 914 913 545 543 587...
output:
590770405
result:
ok 1 number(s): "590770405"
Test #17:
score: 5
Accepted
time: 142ms
memory: 284664kb
input:
109 1500 1205 1206 1191 1192 703 701 1411 1412 1061 1059 469 470 708 707 1131 1133 165 166 1195 1197 1213 1215 1031 1029 363 361 3 4 1168 1167 794 793 1417 1418 1196 1195 645 643 722 721 591 589 827 828 422 421 579 580 1187 1185 193 194 551 553 1431 1429 973 971 1397 1398 353 354 914 913 545 543 587...
output:
557926200
result:
ok 1 number(s): "557926200"
Test #18:
score: 5
Accepted
time: 125ms
memory: 285328kb
input:
109 1500 1205 1206 1191 1192 703 701 1411 1412 1061 1059 469 470 708 707 1131 1133 165 166 1195 1197 1213 1215 1031 1029 363 361 3 4 1168 1167 794 793 1417 1418 1196 1195 645 643 722 721 591 589 827 828 422 421 579 580 1187 1185 193 194 551 553 1431 1429 973 971 1397 1398 353 354 914 913 545 543 587...
output:
496374494
result:
ok 1 number(s): "496374494"
Test #19:
score: 5
Accepted
time: 183ms
memory: 342880kb
input:
2 2500 1205 1206 1191 1192 703 702 2396 2395 2401 2402 469 470 707 708 1133 1132 166 165 2390 2391 1214 1215 1031 1030 363 362 1651 1650 1736 1737 1980 1981 1417 1418 1196 1195 645 644 722 721 1577 1576 1557 1558 422 421 2320 2319 1186 1187 1984 1983 552 553 1689 1688 973 972 1398 1397 354 353 914 9...
output:
155139106
result:
ok 1 number(s): "155139106"
Test #20:
score: 5
Accepted
time: 171ms
memory: 396196kb
input:
6 3500 3187 3188 1191 1192 703 702 3099 3100 2401 2402 470 469 707 708 3230 3231 165 166 2390 2391 1215 1214 1031 1030 362 363 3239 3240 1736 1737 3339 3338 1417 1418 1196 1195 644 645 2975 2974 1577 1576 2757 2756 422 421 2319 2320 1187 1186 1983 1984 3141 3142 1689 1688 973 972 3019 3020 3169 3170...
output:
21222413
result:
ok 1 number(s): "21222413"
Extra Test:
score: 0
Extra Test Passed