QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#340368 | #6223. 神经网络 | ushg8877 | 100 ✓ | 324ms | 609488kb | C++14 | 1.9kb | 2024-02-28 21:55:21 | 2024-02-28 21:55:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=5005;
const int MOD=998244353;
bool Mbe;
int m,n,siz[MAXN];
vector<int> edg[MAXN];
ll f[MAXN][MAXN],g[MAXN][MAXN],h[MAXN][MAXN],tf[MAXN],tg[MAXN],th[MAXN];
ll p[MAXN],fac[MAXN],s;
// 向父亲延申(不算自己),不延展,延展但孤立点
ll q[MAXN][MAXN];// 把 i 个有区别元素分为 j 个有区别链的方案
bool Med;
void add(ll &x,ll y){x=(x+y)%MOD;}
void dfs(int u,int fa){
siz[u]=1;
h[u][0]=1;
for(int v:edg[u]) if(v!=fa){
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++){
add(tf[i+j],f[u][i]*g[v][j]%MOD+h[u][i]*f[v][j]%MOD);
add(th[i+j],h[u][i]*g[v][j]%MOD);
add(tg[i+j],g[u][i]*g[v][j]%MOD);
add(tg[i+j+1],2*f[u][i]*f[v][j]%MOD);
}
swap(f[u],tf);swap(g[u],tg);swap(h[u],th);
siz[u]+=siz[v];
}
for(int i=0;i<=siz[u];i++){
add(g[u][i+1],2*f[u][i]+h[u][i]);
add(f[u][i],h[u][i]);
}
}
int main(){
ios::sync_with_stdio(false);
fac[0]=p[0]=1;
for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%MOD;
cin>>m;
q[0][0]=1;
for(int i=1;i<MAXN;i++) for(int j=1;j<=i;j++){
q[i][j]=((i+j-1)*q[i-1][j]+q[i-1][j-1])%MOD;
}
p[0]=1;
for(int i=1;i<=m;i++){
cin>>n;
for(int i=1;i<=n;i++) edg[i].clear();
for(int i=1;i<=n;i++){
memset(f[i],0,sizeof(f[i]));
memset(g[i],0,sizeof(g[i]));
memset(h[i],0,sizeof(h[i]));
}
for(int j=1;j<n;j++){
int u,v;cin>>u>>v;
edg[u].push_back(v);
edg[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=siz[1];i++) for(int j=1;j<i;j++)
add(g[1][j],((i-j)&1?MOD-1:1)*q[i][j]%MOD*g[1][i]%MOD);
for(int i=s+n;i>=0;i--){
p[i]=0;
for(int j=1;j<=n&&j<=i;j++) add(p[i],g[1][j]*p[i-j]%MOD);
}
s+=n;
}
ll ans=0;
for(int i=1;i<=s;i++) ans+=fac[i-1]*p[i]%MOD;
cout<<ans%MOD<<'\n';
return 0;
}
詳細信息
Test #1:
score: 5
Accepted
time: 7ms
memory: 192940kb
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: 32ms
memory: 196724kb
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: 20ms
memory: 198156kb
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: 19ms
memory: 194532kb
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: 25ms
memory: 196976kb
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: 21ms
memory: 198716kb
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: 58ms
memory: 201848kb
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: 50ms
memory: 202360kb
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: 52ms
memory: 204008kb
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: 59ms
memory: 201656kb
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: 223ms
memory: 372248kb
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: 235ms
memory: 373308kb
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: 227ms
memory: 374328kb
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: 226ms
memory: 373676kb
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: 207ms
memory: 373832kb
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: 215ms
memory: 374096kb
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: 229ms
memory: 374164kb
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: 234ms
memory: 375824kb
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: 324ms
memory: 493216kb
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: 314ms
memory: 609488kb
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