QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#112922 | #5357. 芒果冰加了空气 | Larry1010 | 5 | 2ms | 7788kb | C++14 | 2.1kb | 2023-06-15 11:53:10 | 2023-06-15 11:53:14 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,s,t) for(int i=s,__=t;i<=__;i++)
#define pre(i,s,t) for(int i=s,__=t;i>=__;i--)
#define ll long long
#define fi first
#define se second
#define ls (k<<1)
#define rs (k<<1|1)
#define mkp make_pair
#define pii pair<int,int>
#define p_b push_back
#define all(x) x.begin(),x.end()
#define sz(x) x.size()
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
const int N=3010,mod=998244353;
using namespace std;
inline int read() {
int s = 0, w = 1;
char ch = getchar();
while(ch < '0' || ch > '9') { if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
return s * w;
}
int T,n,a[N];
vector<int>v[N];
int dp[N][N];
int c[N][N];
int siz[N];
int f[N];
void dfs(int x,int fa){
siz[x]=1;
dp[x][1]=1;
for(auto y:v[x]){
if(y==fa)continue;
dfs(y,x);memset(f,0,sizeof(f));
rep(i,1,siz[x]){
int pre=0;
pre(j,siz[y],1){
pre=(pre+dp[y][j])%mod;
f[i+j]=(f[i+j]+1ll*dp[x][i]*pre%mod*c[i+j-1][i-1])%mod;
}
f[i]=(f[i]+1ll*dp[x][i]*pre)%mod;
}
swap(f,dp[x]);
// rep(i,1,siz[x]+siz[y]){
// cout<<dp[x][i]<<" ";
// }puts("");
siz[x]+=siz[y];
}
}
void init(int n){
rep(i,0,n){
c[i][0]=1;
rep(j,1,i)c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
}
}
int ans=0;
int main() {
cin>>n;
init(2*n);
rep(i,2,n){
int x=read(),y=read();
v[x].p_b(y);v[y].p_b(x);
}
dfs(1,0);
rep(i,1,n)ans=(ans+dp[1][i])%mod;
cout<<ans<<endl;
return 0;
}
/*
0. Enough array size? Enough array size? Enough array size? Interger overflow?
1. Think TWICE, Code ONCE!
Are there any counterexamples to your algo?
2. Be careful about the BOUNDARIES!
N=1? P=1? Something about 0?
3. Do not make STUPID MISTAKES!
Time complexity? Memory usage? Precision error?
4. Do you have some Warnings? Just have a look at them!
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 5724kb
input:
10 1 2 2 3 3 4 5 4 6 4 7 4 8 4 9 4 10 4
output:
310862
result:
ok single line: '310862'
Test #2:
score: 0
Accepted
time: 0ms
memory: 5644kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 8 10
output:
64804
result:
ok single line: '64804'
Test #3:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
10 1 2 1 3 3 4 3 5 3 6 4 7 3 8 4 9 4 10
output:
258182
result:
ok single line: '258182'
Test #4:
score: 0
Accepted
time: 1ms
memory: 5776kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
16796
result:
ok single line: '16796'
Test #5:
score: 0
Accepted
time: 1ms
memory: 5772kb
input:
10 1 2 2 3 3 4 4 5 1 6 2 7 3 8 4 9 5 10
output:
78384
result:
ok single line: '78384'
Test #6:
score: 0
Accepted
time: 0ms
memory: 5608kb
input:
10 1 2 1 3 2 4 3 5 2 6 4 7 3 8 7 9 9 10
output:
38896
result:
ok single line: '38896'
Test #7:
score: 0
Accepted
time: 0ms
memory: 5608kb
input:
10 1 2 2 3 4 3 5 3 6 3 7 3 8 3 9 3 10 3
output:
609656
result:
ok single line: '609656'
Test #8:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
10 1 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 9 10
output:
64804
result:
ok single line: '64804'
Test #9:
score: 0
Accepted
time: 2ms
memory: 7760kb
input:
10 1 2 1 3 3 4 3 5 1 6 4 7 1 8 4 9 9 10
output:
118638
result:
ok single line: '118638'
Test #10:
score: 0
Accepted
time: 2ms
memory: 7704kb
input:
10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 8 10
output:
22438
result:
ok single line: '22438'
Test #11:
score: 0
Accepted
time: 0ms
memory: 5620kb
input:
10 1 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 10
output:
16796
result:
ok single line: '16796'
Test #12:
score: 0
Accepted
time: 0ms
memory: 5656kb
input:
10 1 2 1 3 1 4 3 5 4 6 2 7 3 8 5 9 5 10
output:
82316
result:
ok single line: '82316'
Test #13:
score: 0
Accepted
time: 1ms
memory: 5708kb
input:
8 1 2 3 2 4 2 5 2 6 2 7 2 8 2
output:
13700
result:
ok single line: '13700'
Test #14:
score: 0
Accepted
time: 0ms
memory: 5700kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 3 8
output:
3996
result:
ok single line: '3996'
Test #15:
score: 0
Accepted
time: 1ms
memory: 5508kb
input:
8 1 2 2 3 1 4 1 5 1 6 3 7 6 8
output:
3490
result:
ok single line: '3490'
Test #16:
score: 0
Accepted
time: 1ms
memory: 5760kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 7 8
output:
1430
result:
ok single line: '1430'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7684kb
input:
8 1 2 1 3 2 4 3 5 4 6 5 7 6 8
output:
1430
result:
ok single line: '1430'
Test #18:
score: 0
Accepted
time: 1ms
memory: 5640kb
input:
8 1 2 2 3 3 4 2 5 3 6 5 7 4 8
output:
3232
result:
ok single line: '3232'
Test #19:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
8 1 2 2 3 4 3 5 3 6 3 7 3 8 3
output:
8970
result:
ok single line: '8970'
Test #20:
score: 0
Accepted
time: 0ms
memory: 5624kb
input:
8 1 2 1 3 2 4 2 5 3 6 3 7 2 8
output:
3996
result:
ok single line: '3996'
Test #21:
score: 0
Accepted
time: 2ms
memory: 7788kb
input:
8 1 2 1 3 1 4 4 5 3 6 4 7 2 8
output:
3332
result:
ok single line: '3332'
Test #22:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
8 1 2 2 3 3 4 4 5 5 6 6 7 2 8
output:
1870
result:
ok single line: '1870'
Test #23:
score: 0
Accepted
time: 1ms
memory: 5500kb
input:
8 1 2 2 3 1 4 2 5 3 6 4 7 5 8
output:
2416
result:
ok single line: '2416'
Test #24:
score: 0
Accepted
time: 1ms
memory: 5564kb
input:
8 1 2 1 3 2 4 3 5 2 6 6 7 3 8
output:
2802
result:
ok single line: '2802'
Test #25:
score: 0
Accepted
time: 2ms
memory: 7592kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 2ms
memory: 7640kb
input:
10 1 2 1 3 1 4 4 5 1 6 6 7 3 8 5 9 2 10
output:
78904
result:
ok single line: '78904'
Subtask #2:
score: 0
Runtime Error
Test #27:
score: 0
Runtime Error
input:
5000 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52 52 53 ...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #37:
score: 0
Wrong Answer
time: 2ms
memory: 5684kb
input:
20 1 2 2 3 3 4 1 5 3 6 5 7 5 8 8 9 7 10 10 11 9 12 12 13 10 14 11 15 13 16 16 17 17 18 18 19 16 20
output:
555866770
result:
wrong answer 1st lines differ - expected: '85351498', found: '555866770'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%