QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#299212 | #5357. 芒果冰加了空气 | HMSF | 15 | 85ms | 200168kb | C++14 | 2.2kb | 2024-01-06 17:48:53 | 2024-01-06 17:48:54 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
//#include<vector>
//#include<set>
//#include<queue>
//#include<stack>
#define PII pair<int,int>
#define MP make_pair
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LDB;
inline LL read()
{
LL s=0; bool w=0; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=1; ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+(ch^48); ch=getchar();}
return w ? ~s+1 : s;
}
const int maxn = 5005;
const LL mod = 1000000007;
inline LL madd(LL a,LL b){a+=b; return a>=mod ? a-mod : a;}
inline LL msub(LL a,LL b){a-=b; return a<0 ? a+mod : a;}
inline LL M(LL a,LL b){return (a*b)%mod;}
LL qpow(LL bse,LL exp) {
LL res = 1; while(exp) {
if(exp&1){res = M(res,bse);}
bse = M(bse,bse); exp>>=1;
} return res;
}
LL jxig[maxn+10],jxiginv[maxn+10];
void init_math()
{
jxig[0] = 1;
for(int i=1; i<=maxn; i++) jxig[i] = M(jxig[i-1],i);
jxiginv[maxn] = qpow(jxig[maxn],mod-2);
for(int i=maxn-1; i>=0; i--) jxiginv[i] = M(jxiginv[i+1],i+1);
return;
}
inline LL C(LL N,LL R){return N>=R ? M(jxig[N],M(jxiginv[R],jxiginv[N-R])) : 0;}
int n;
struct Edge { int v,nxt; }e[maxn<<1];
int h[maxn],ecnt;
void adde(int u,int v) { ecnt++; e[ecnt].v = v; e[ecnt].nxt = h[u]; h[u] = ecnt; return; }
LL f[maxn][maxn];
LL g[maxn];
int siz[maxn];
void DP(int u,int lst)
{
siz[u] = 0;
for(int i=0; i<=n; i++) g[i] = 0;
f[u][0] = 1;
for(int i=h[u]; i; i=e[i].nxt)
{
int v = e[i].v; if(v==lst) continue;
DP(v,u);
for(int j=siz[u]; j>=0; j--)
for(int k=0; k<=siz[v]; k++)
g[j+k] += M(M(f[v][k],f[u][j]),C(j+k,j));
siz[u] += siz[v];
for(int j=0; j<=siz[u]; j++) { f[u][j] = g[j]; g[j] = 0; }
}
siz[u]++;
for(int i=siz[u]; i>=1; i--) { f[u][i] = f[u][i-1]; } f[u][0] = 0;
for(int i=siz[u]-1; i>=0; i--) { f[u][i] = madd(f[u][i],f[u][i+1]); }
return;
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
init_math();
n = read();
for(int i=1; i<n; i++)
{
int u = read(); int v =read();
adde(u,v); adde(v,u);
}
DP(1,0);
printf("%lld\n",f[1][0]);
//fclose(stdin);fclose(stdout);
return 0;
}
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 1ms
memory: 3980kb
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: 1ms
memory: 5904kb
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: 0ms
memory: 3984kb
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: 0ms
memory: 3880kb
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: 0ms
memory: 3980kb
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: 1ms
memory: 5892kb
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: 3864kb
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: 5912kb
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: 0ms
memory: 3900kb
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: 1ms
memory: 5872kb
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: 3880kb
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: 3848kb
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: 3872kb
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: 3824kb
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: 0ms
memory: 3856kb
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: 0ms
memory: 3932kb
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: 0ms
memory: 3988kb
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: 0ms
memory: 3824kb
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: 0ms
memory: 3864kb
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: 3860kb
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: 1ms
memory: 5852kb
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: 5804kb
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: 0ms
memory: 3972kb
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: 0ms
memory: 3840kb
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: 0ms
memory: 4020kb
input:
3 1 2 2 3
output:
5
result:
ok single line: '5'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3876kb
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: 10
Accepted
Test #27:
score: 10
Accepted
time: 78ms
memory: 200168kb
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:
138172849
result:
ok single line: '138172849'
Test #28:
score: 0
Accepted
time: 16ms
memory: 90476kb
input:
2195 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:
34585647
result:
ok single line: '34585647'
Test #29:
score: 0
Accepted
time: 49ms
memory: 158524kb
input:
3927 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:
179814607
result:
ok single line: '179814607'
Test #30:
score: 0
Accepted
time: 6ms
memory: 38796kb
input:
857 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 5...
output:
997745350
result:
ok single line: '997745350'
Test #31:
score: 0
Accepted
time: 4ms
memory: 49180kb
input:
1157 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:
459486613
result:
ok single line: '459486613'
Test #32:
score: 0
Accepted
time: 85ms
memory: 200108kb
input:
4958 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:
276300910
result:
ok single line: '276300910'
Test #33:
score: 0
Accepted
time: 28ms
memory: 113040kb
input:
2758 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:
161112418
result:
ok single line: '161112418'
Test #34:
score: 0
Accepted
time: 26ms
memory: 117668kb
input:
2905 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:
501208825
result:
ok single line: '501208825'
Test #35:
score: 0
Accepted
time: 16ms
memory: 84436kb
input:
2047 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:
995483163
result:
ok single line: '995483163'
Test #36:
score: 0
Accepted
time: 32ms
memory: 125624kb
input:
3098 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:
324344238
result:
ok single line: '324344238'
Subtask #3:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #37:
score: 0
Wrong Answer
time: 0ms
memory: 3880kb
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:
14085351596
result:
wrong answer 1st lines differ - expected: '85351498', found: '14085351596'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #5:
0%