QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#85205 | #5367. 递增树列 | tricyzhkx | 100 ✓ | 162ms | 5768kb | C++14 | 3.6kb | 2023-03-07 10:42:22 | 2023-03-07 10:42:24 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
typedef vector<int> Poly;
int n,sz[100],f[100][100];
ll fac[100],inv[100];
Poly P[100],P1[100];
vector<int> G[100];
template<typename T>
void upd(int &a,T b){a=(a+b)%mod;}
ll C(int n,int m){return fac[n]*inv[n-m]%mod*inv[m]%mod;}
Poly operator+(const Poly &a,const Poly &b)
{
Poly ans(n+1);
for(int i=0;i<=n;i++) ans[i]=(a[i]+b[i])%mod;
return ans;
}
Poly operator*(Poly a,int b)
{
for(int &i:a) i=(ll)i*b%mod;
return a;
}
Poly operator*(const Poly &a,const Poly &b)
{
Poly ans(n+1);
for(int i=0;i<=n;i++) ans[i]=(ll)a[i]*b[i]%mod;
return ans;
}
Poly Eval(const Poly &a)
{
int sz=a.size();
Poly ans(n+1);
for(int i=0;i<=n;i++)
{
int v=0;
for(int j=sz-1;j>=0;j--) v=((ll)v*i+a[j])%mod;
ans[i]=v;
}
return ans;
}
Poly Lagrange(const Poly &a)
{
Poly ans(n+1),mul(n+2);
mul[0]=1;
for(int i=0;i<=n;i++)
{
for(int j=i+1;j>=1;j--) mul[j]=((ll)(mod-i)*mul[j]+mul[j-1])%mod;
mul[0]=(ll)(mod-i)*mul[0]%mod;
}
for(int i=0;i<=n;i++)
{
Poly F(n+1);
for(int j=n,v=mul[j+1];j>=0;j--) F[j]=v,v=(mul[j]+(ll)v*i)%mod;
ll w=((n-i)&1?mod-inv[n-i]:inv[n-i])*inv[i]%mod*a[i]%mod;
for(int j=0;j<=n;j++) ans[j]=(ans[j]+w*F[j])%mod;
}
return ans;
}
int calc(Poly a)
{
a=Lagrange(a);
int ans=0;
for(int i=0;i<=n;i++) upd(ans,a[i]*fac[i]);
return ans;
}
void dfs(int u,int fa)
{
sz[u]=1;
for(int v:G[u])
if(v!=fa) dfs(v,u);
vector<int> vec;vec.push_back(u);
for(int v:G[u])
if(v!=fa) vec.push_back(v);
int tot=vec.size();
if(tot==1) return f[u][0]=0,f[u][1]=1,void();
static Poly pre[100][100],suf[100][100],G[100];
static int pres[100],sufs[100];
pres[0]=sz[vec[0]];sufs[tot]=0;
for(int i=0;i<=sz[vec[0]];i++) pre[0][i]=P[i]*C(sz[vec[0]],i);
suf[tot][0]=Poly(n+1,1);
for(int i=1;i<tot;i++)
{
pres[i]=pres[i-1]+sz[vec[i]];
for(int j=0;j<=pres[i];j++) pre[i][j]=Poly(n+1);
for(int j=0;j<=pres[i-1];j++)
for(int k=0;k<=sz[vec[i]];k++)
pre[i][j+k]=pre[i][j+k]+pre[i-1][j]*P[k]*C(sz[vec[i]],k);
}
for(int i=tot-1;i>=0;i--)
{
sufs[i]=sufs[i+1]+sz[vec[i]];
for(int j=0;j<=sufs[i];j++) suf[i][j]=Poly(n+1);
for(int j=0;j<=sufs[i+1];j++)
for(int k=0;k<=sz[vec[i]];k++)
suf[i][j+k]=suf[i][j+k]+suf[i+1][j]*P[k]*C(sz[vec[i]],k);
}
sz[u]=sufs[0];
for(int i=1;i<=sz[u];i++) G[i]=Poly(n+1);
for(int i=1;i<tot;i++)
{
int v=vec[i];
static Poly F[100];
for(int j=0;j<=sz[u]-sz[v];j++) F[j]=Poly(n+1);
for(int j=0;j<=pres[i-1];j++)
for(int k=0;k<=sufs[i+1];k++)
F[j+k]=F[j+k]+pre[i-1][j]*suf[i+1][k];
for(int j=0;j<=sz[u]-sz[v];j++)
for(int k=1;k<=sz[v];k++)
for(int l=1;l<=k;l++)
G[j+k]=G[j+k]+F[j]*P1[k-l]*(C(sz[v]-l,k-l)*f[v][l]%mod);
}
for(int i=1;i<=sz[u];i++) G[i]=G[i]+suf[1][i-1];
for(int i=1;i<=sz[u];i++) f[u][i]=calc(G[i]);
}
int main()
{
int u,v;
cin>>n;
fac[0]=fac[1]=inv[0]=inv[1]=1;
for(int i=2;i<=n;i++) fac[i]=fac[i-1]*i%mod;
for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=2;i<=n;i++) inv[i]=inv[i-1]*inv[i]%mod;
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
G[u].push_back(v);G[v].push_back(u);
}
P1[0]=P[0]=Poly(n+1,1);
for(int i=1;i<=n;i++)
{
P[i].resize(i+1);P1[i].resize(i+1);
for(int j=1;j<=i;j++) P[i][j]=C(i-1,j-1)*fac[i]%mod*inv[j]%mod;
for(int j=i-1;j>=0;j-=2) P[i][j]=mod-P[i][j];
for(int j=0;j<i;j++) P1[i][j]=(P[i][j]+(ll)(mod-j-1)*P[i][j+1])%mod;
P1[i][i]=P[i][i];
P[i]=Eval(P[i]);P1[i]=Eval(P1[i]);
}
dfs(1,0);
cout<<f[1][n]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 1ms
memory: 4152kb
input:
7 1 2 2 3 2 4 1 5 5 6 3 7
output:
712
result:
ok single line: '712'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3960kb
input:
5 1 2 1 3 3 4 4 5
output:
44
result:
ok single line: '44'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
7 1 2 2 3 1 4 3 5 3 6 2 7
output:
576
result:
ok single line: '576'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
8 1 2 1 3 3 4 2 5 2 6 1 7 2 8
output:
6912
result:
ok single line: '6912'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4088kb
input:
8 1 2 2 3 2 4 1 5 2 6 3 7 5 8
output:
3360
result:
ok single line: '3360'
Subtask #2:
score: 11
Accepted
Dependency #1:
100%
Accepted
Test #6:
score: 11
Accepted
time: 2ms
memory: 4008kb
input:
14 1 2 1 3 1 4 1 5 1 6 4 7 2 8 1 9 4 10 7 11 9 12 2 13 11 14
output:
389151297
result:
ok single line: '389151297'
Test #7:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
13 1 2 2 3 2 4 2 5 4 6 4 7 3 8 4 9 6 10 4 11 11 12 6 13
output:
17381952
result:
ok single line: '17381952'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4136kb
input:
12 1 2 2 3 2 4 1 5 5 6 4 7 7 8 5 9 4 10 1 11 7 12
output:
4993920
result:
ok single line: '4993920'
Test #9:
score: 0
Accepted
time: 3ms
memory: 4020kb
input:
15 1 2 1 3 2 4 4 5 2 6 6 7 2 8 8 9 2 10 4 11 8 12 4 13 5 14 9 15
output:
818474475
result:
ok single line: '818474475'
Test #10:
score: 0
Accepted
time: 2ms
memory: 4008kb
input:
15 1 2 1 3 2 4 3 5 2 6 5 7 4 8 4 9 1 10 10 11 8 12 10 13 13 14 7 15
output:
16041048
result:
ok single line: '16041048'
Subtask #3:
score: 15
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #11:
score: 15
Accepted
time: 1ms
memory: 4044kb
input:
25 1 2 1 3 3 4 4 5 2 6 2 7 5 8 5 9 1 10 10 11 9 12 5 13 4 14 12 15 1 16 14 17 2 18 2 19 16 20 18 21 18 22 20 23 17 24 19 25
output:
179142361
result:
ok single line: '179142361'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4156kb
input:
24 1 2 1 3 2 4 1 5 2 6 2 7 6 8 1 9 1 10 1 11 8 12 6 13 13 14 12 15 2 16 5 17 12 18 8 19 11 20 17 21 21 22 19 23 18 24
output:
680835791
result:
ok single line: '680835791'
Test #13:
score: 0
Accepted
time: 3ms
memory: 4024kb
input:
23 1 2 1 3 3 4 2 5 2 6 5 7 4 8 7 9 4 10 8 11 2 12 8 13 1 14 14 15 9 16 7 17 9 18 5 19 16 20 15 21 10 22 17 23
output:
613299173
result:
ok single line: '613299173'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3988kb
input:
24 1 2 1 3 1 4 1 5 2 6 3 7 1 8 6 9 6 10 10 11 6 12 10 13 6 14 4 15 5 16 1 17 8 18 1 19 17 20 2 21 19 22 20 23 15 24
output:
990332459
result:
ok single line: '990332459'
Test #15:
score: 0
Accepted
time: 3ms
memory: 4044kb
input:
27 1 2 1 3 2 4 1 5 3 6 1 7 4 8 5 9 5 10 9 11 10 12 11 13 6 14 3 15 6 16 5 17 4 18 14 19 3 20 13 21 1 22 8 23 6 24 4 25 12 26 25 27
output:
254905851
result:
ok single line: '254905851'
Test #16:
score: 0
Accepted
time: 6ms
memory: 4160kb
input:
28 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
output:
245512165
result:
ok single line: '245512165'
Test #17:
score: 0
Accepted
time: 3ms
memory: 4044kb
input:
25 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25
output:
440732388
result:
ok single line: '440732388'
Test #18:
score: 0
Accepted
time: 4ms
memory: 3996kb
input:
25 1 2 2 3 2 4 3 5 3 6 4 7 6 8 8 9 8 10 9 11 9 12 11 13 11 14 12 15 14 16 15 17 16 18 16 19 19 20 19 21 20 22 21 23 21 24 24 25
output:
222462817
result:
ok single line: '222462817'
Test #19:
score: 0
Accepted
time: 4ms
memory: 4096kb
input:
30 1 2 1 3 1 4 2 5 5 6 3 7 7 8 5 9 6 10 7 11 10 12 9 13 11 14 11 15 14 16 13 17 16 18 15 19 19 20 20 21 18 22 22 23 21 24 24 25 22 26 24 27 25 28 27 29 27 30
output:
915280502
result:
ok single line: '915280502'
Test #20:
score: 0
Accepted
time: 4ms
memory: 4164kb
input:
29 1 2 2 3 1 4 4 5 2 6 5 7 3 8 7 9 5 10 7 11 10 12 9 13 13 14 11 15 11 16 12 17 17 18 17 19 17 20 16 21 17 22 20 23 22 24 23 25 22 26 25 27 24 28 28 29
output:
847984210
result:
ok single line: '847984210'
Test #21:
score: 0
Accepted
time: 5ms
memory: 4184kb
input:
30 1 2 1 3 3 4 4 5 4 6 5 7 6 8 6 9 8 10 6 11 11 12 10 13 9 14 9 15 15 16 15 17 17 18 16 19 16 20 19 21 16 22 20 23 20 24 21 25 20 26 22 27 25 28 26 29 28 30
output:
203499669
result:
ok single line: '203499669'
Test #22:
score: 0
Accepted
time: 0ms
memory: 4092kb
input:
29 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 7 18 1 19 6 20 16 21 18 22 19 23 15 24 6 25 3 26 16 27 9 28 21 29
output:
673029660
result:
ok single line: '673029660'
Test #23:
score: 0
Accepted
time: 3ms
memory: 4028kb
input:
25 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 2 20 10 21 2 22 14 23 9 24 5 25
output:
463358446
result:
ok single line: '463358446'
Test #24:
score: 0
Accepted
time: 3ms
memory: 4124kb
input:
30 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 16 20 14 21 8 22 13 23 3 24 16 25 13 26 18 27 10 28 5 29 21 30
output:
2581770
result:
ok single line: '2581770'
Subtask #4:
score: 25
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Test #25:
score: 25
Accepted
time: 3ms
memory: 4168kb
input:
42 1 2 1 3 2 4 1 5 1 6 1 7 6 8 2 9 5 10 2 11 2 12 7 13 9 14 3 15 4 16 3 17 8 18 11 19 10 20 12 21 16 22 6 23 13 24 19 25 8 26 22 27 19 28 7 29 1 30 2 31 30 32 27 33 28 34 18 35 6 36 24 37 21 38 11 39 22 40 22 41 3 42
output:
475818143
result:
ok single line: '475818143'
Test #26:
score: 0
Accepted
time: 10ms
memory: 4120kb
input:
47 1 2 2 3 2 4 2 5 4 6 3 7 6 8 4 9 7 10 6 11 3 12 8 13 4 14 3 15 9 16 12 17 1 18 4 19 7 20 1 21 4 22 3 23 12 24 5 25 7 26 18 27 23 28 21 29 4 30 6 31 11 32 27 33 25 34 28 35 13 36 9 37 21 38 31 39 13 40 20 41 34 42 12 43 36 44 13 45 25 46 42 47
output:
574349748
result:
ok single line: '574349748'
Test #27:
score: 0
Accepted
time: 12ms
memory: 4120kb
input:
47 1 2 2 3 3 4 4 5 5 6 2 7 7 8 6 9 7 10 7 11 4 12 11 13 7 14 6 15 10 16 16 17 7 18 17 19 3 20 15 21 21 22 11 23 10 24 13 25 10 26 6 27 21 28 4 29 2 30 6 31 16 32 29 33 4 34 20 35 34 36 19 37 3 38 21 39 29 40 8 41 31 42 37 43 38 44 23 45 43 46 28 47
output:
284808122
result:
ok single line: '284808122'
Test #28:
score: 0
Accepted
time: 10ms
memory: 4200kb
input:
48 1 2 2 3 1 4 1 5 3 6 1 7 7 8 6 9 8 10 8 11 3 12 11 13 6 14 13 15 4 16 4 17 9 18 17 19 11 20 11 21 3 22 2 23 8 24 23 25 7 26 4 27 21 28 11 29 4 30 21 31 20 32 14 33 20 34 21 35 26 36 10 37 8 38 2 39 27 40 9 41 14 42 28 43 31 44 2 45 10 46 25 47 43 48
output:
728582173
result:
ok single line: '728582173'
Test #29:
score: 0
Accepted
time: 8ms
memory: 4096kb
input:
46 1 2 1 3 1 4 3 5 3 6 1 7 5 8 6 9 3 10 1 11 6 12 8 13 3 14 7 15 2 16 11 17 17 18 18 19 4 20 5 21 7 22 18 23 10 24 20 25 16 26 22 27 17 28 17 29 17 30 25 31 1 32 7 33 2 34 12 35 27 36 31 37 13 38 34 39 30 40 5 41 34 42 31 43 2 44 8 45 43 46
output:
830913254
result:
ok single line: '830913254'
Test #30:
score: 0
Accepted
time: 21ms
memory: 4148kb
input:
42 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
output:
118430285
result:
ok single line: '118430285'
Test #31:
score: 0
Accepted
time: 7ms
memory: 4400kb
input:
44 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44
output:
10503098
result:
ok single line: '10503098'
Test #32:
score: 0
Accepted
time: 22ms
memory: 4112kb
input:
48 1 2 2 3 1 4 2 5 5 6 5 7 6 8 7 9 7 10 8 11 11 12 10 13 12 14 14 15 15 16 15 17 17 18 17 19 18 20 18 21 19 22 20 23 23 24 22 25 24 26 26 27 27 28 27 29 28 30 29 31 31 32 32 33 33 34 33 35 34 36 34 37 36 38 36 39 38 40 40 41 40 42 40 43 42 44 44 45 45 46 44 47 46 48
output:
236779386
result:
ok single line: '236779386'
Test #33:
score: 0
Accepted
time: 13ms
memory: 4116kb
input:
43 1 2 1 3 3 4 4 5 4 6 4 7 4 8 8 9 7 10 7 11 10 12 9 13 12 14 12 15 14 16 15 17 17 18 17 19 18 20 19 21 19 22 20 23 21 24 22 25 23 26 24 27 27 28 25 29 26 30 30 31 29 32 32 33 31 34 33 35 33 36 33 37 37 38 35 39 37 40 37 41 38 42 42 43
output:
472278844
result:
ok single line: '472278844'
Test #34:
score: 0
Accepted
time: 19ms
memory: 4244kb
input:
49 1 2 2 3 2 4 4 5 1 6 3 7 7 8 6 9 7 10 10 11 7 12 10 13 9 14 11 15 14 16 15 17 15 18 14 19 18 20 19 21 17 22 22 23 20 24 24 25 24 26 23 27 25 28 25 29 27 30 29 31 27 32 29 33 31 34 34 35 31 36 34 37 35 38 35 39 37 40 36 41 40 42 39 43 42 44 42 45 42 46 45 47 46 48 45 49
output:
918870657
result:
ok single line: '918870657'
Test #35:
score: 0
Accepted
time: 11ms
memory: 4072kb
input:
46 1 2 1 3 2 4 3 5 3 6 6 7 4 8 8 9 9 10 8 11 8 12 12 13 9 14 12 15 14 16 12 17 13 18 18 19 19 20 15 21 21 22 20 23 18 24 20 25 23 26 23 27 26 28 24 29 24 30 29 31 28 32 31 33 31 34 31 35 33 36 36 37 32 38 34 39 35 40 39 41 38 42 37 43 41 44 43 45 45 46
output:
85610243
result:
ok single line: '85610243'
Test #36:
score: 0
Accepted
time: 5ms
memory: 4308kb
input:
48 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 2 23 1 24 23 25 18 26 10 27 1 28 15 29 7 30 6 31 26 32 17 33 30 34 10 35 35 36 10 37 29 38 31 39 35 40 18 41 34 42 3 43 30 44 34 45 45 46 43 47 27 48
output:
773530270
result:
ok single line: '773530270'
Test #37:
score: 0
Accepted
time: 4ms
memory: 4260kb
input:
45 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 12 24 11 25 2 26 13 27 7 28 4 29 5 30 29 31 4 32 9 33 32 34 21 35 12 36 20 37 3 38 20 39 35 40 36 41 23 42 31 43 5 44 31 45
output:
600462689
result:
ok single line: '600462689'
Test #38:
score: 0
Accepted
time: 5ms
memory: 4268kb
input:
45 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 24 25 24 26 26 27 16 28 4 29 23 30 16 31 23 32 6 33 27 34 25 35 12 36 4 37 31 38 4 39 8 40 18 41 27 42 35 43 22 44 23 45
output:
563685126
result:
ok single line: '563685126'
Subtask #5:
score: 40
Accepted
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #39:
score: 40
Accepted
time: 34ms
memory: 4292kb
input:
73 1 2 1 3 2 4 3 5 5 6 3 7 3 8 2 9 3 10 3 11 8 12 3 13 9 14 12 15 11 16 3 17 11 18 18 19 3 20 5 21 1 22 2 23 23 24 7 25 15 26 17 27 22 28 28 29 13 30 24 31 22 32 15 33 25 34 4 35 5 36 28 37 8 38 6 39 12 40 6 41 4 42 30 43 26 44 11 45 8 46 35 47 36 48 45 49 8 50 7 51 43 52 27 53 49 54 53 55 52 56 8 5...
output:
518761011
result:
ok single line: '518761011'
Test #40:
score: 0
Accepted
time: 41ms
memory: 4376kb
input:
80 1 2 1 3 2 4 3 5 1 6 6 7 7 8 5 9 2 10 7 11 4 12 3 13 9 14 12 15 13 16 5 17 10 18 4 19 1 20 14 21 16 22 13 23 17 24 8 25 11 26 23 27 5 28 27 29 23 30 8 31 11 32 21 33 3 34 25 35 6 36 24 37 12 38 6 39 37 40 10 41 2 42 27 43 23 44 28 45 20 46 46 47 15 48 45 49 40 50 36 51 13 52 49 53 52 54 36 55 19 5...
output:
908706975
result:
ok single line: '908706975'
Test #41:
score: 0
Accepted
time: 36ms
memory: 4328kb
input:
77 1 2 2 3 1 4 2 5 1 6 1 7 3 8 2 9 6 10 7 11 8 12 4 13 12 14 14 15 4 16 10 17 7 18 7 19 9 20 14 21 10 22 9 23 23 24 5 25 22 26 16 27 21 28 10 29 1 30 26 31 5 32 12 33 31 34 3 35 22 36 30 37 17 38 20 39 20 40 14 41 33 42 5 43 1 44 36 45 30 46 27 47 43 48 13 49 29 50 5 51 10 52 47 53 20 54 24 55 3 56 ...
output:
471949293
result:
ok single line: '471949293'
Test #42:
score: 0
Accepted
time: 50ms
memory: 4312kb
input:
80 1 2 2 3 2 4 4 5 4 6 5 7 2 8 1 9 7 10 6 11 10 12 2 13 8 14 14 15 3 16 9 17 1 18 10 19 10 20 5 21 9 22 9 23 23 24 13 25 8 26 18 27 27 28 4 29 10 30 3 31 1 32 16 33 32 34 21 35 19 36 17 37 13 38 38 39 38 40 8 41 33 42 4 43 12 44 15 45 19 46 19 47 4 48 47 49 6 50 24 51 29 52 12 53 48 54 31 55 15 56 5...
output:
112450382
result:
ok single line: '112450382'
Test #43:
score: 0
Accepted
time: 38ms
memory: 4348kb
input:
76 1 2 2 3 3 4 1 5 2 6 6 7 2 8 2 9 1 10 6 11 4 12 5 13 7 14 10 15 14 16 16 17 16 18 14 19 10 20 5 21 13 22 2 23 5 24 19 25 14 26 13 27 7 28 15 29 1 30 20 31 1 32 13 33 9 34 30 35 34 36 28 37 2 38 35 39 12 40 29 41 21 42 40 43 6 44 18 45 2 46 35 47 38 48 15 49 25 50 23 51 38 52 23 53 17 54 4 55 40 56...
output:
815118641
result:
ok single line: '815118641'
Test #44:
score: 0
Accepted
time: 162ms
memory: 4244kb
input:
74 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 53...
output:
367159086
result:
ok single line: '367159086'
Test #45:
score: 0
Accepted
time: 22ms
memory: 5768kb
input:
71 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61 1 62 ...
output:
715534167
result:
ok single line: '715534167'
Test #46:
score: 0
Accepted
time: 113ms
memory: 4440kb
input:
79 1 2 2 3 2 4 4 5 3 6 4 7 7 8 6 9 9 10 10 11 10 12 10 13 11 14 12 15 14 16 14 17 15 18 17 19 19 20 18 21 21 22 22 23 21 24 24 25 25 26 25 27 27 28 28 29 29 30 28 31 30 32 30 33 31 34 33 35 33 36 34 37 37 38 38 39 37 40 40 41 40 42 40 43 41 44 43 45 43 46 45 47 45 48 48 49 48 50 48 51 51 52 50 53 51...
output:
192185403
result:
ok single line: '192185403'
Test #47:
score: 0
Accepted
time: 97ms
memory: 4300kb
input:
78 1 2 1 3 2 4 1 5 2 6 4 7 7 8 5 9 8 10 9 11 8 12 9 13 12 14 14 15 14 16 14 17 16 18 16 19 18 20 18 21 20 22 20 23 21 24 24 25 22 26 23 27 25 28 28 29 28 30 30 31 30 32 31 33 32 34 34 35 32 36 35 37 36 38 35 39 38 40 40 41 40 42 39 43 42 44 41 45 42 46 44 47 46 48 48 49 48 50 50 51 51 52 49 53 51 54...
output:
275960320
result:
ok single line: '275960320'
Test #48:
score: 0
Accepted
time: 94ms
memory: 4316kb
input:
78 1 2 1 3 3 4 4 5 1 6 6 7 6 8 4 9 8 10 10 11 10 12 9 13 9 14 13 15 14 16 16 17 14 18 18 19 19 20 20 21 20 22 22 23 23 24 23 25 23 26 24 27 26 28 25 29 27 30 30 31 28 32 28 33 32 34 34 35 33 36 32 37 37 38 37 39 35 40 40 41 39 42 40 43 42 44 43 45 43 46 45 47 43 48 45 49 46 50 46 51 51 52 51 53 50 5...
output:
79692172
result:
ok single line: '79692172'
Test #49:
score: 0
Accepted
time: 76ms
memory: 4232kb
input:
76 1 2 2 3 3 4 4 5 1 6 2 7 5 8 6 9 5 10 8 11 8 12 12 13 9 14 13 15 12 16 11 17 15 18 15 19 16 20 17 21 18 22 18 23 23 24 21 25 21 26 24 27 27 28 24 29 26 30 26 31 26 32 29 33 28 34 30 35 31 36 32 37 37 38 33 39 34 40 37 41 38 42 38 43 40 44 41 45 42 46 46 47 45 48 46 49 44 50 49 51 49 52 50 53 51 54...
output:
155298272
result:
ok single line: '155298272'
Test #50:
score: 0
Accepted
time: 21ms
memory: 5088kb
input:
78 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 16 33 18 34 1 35 16 36 13 37 35 38 11 39 33 40 29 41 22 42 29 43 11 44 22 45 9 46 21 47 35 48 1 49 27 50 23 51 14 52 21 53 44 54 39 55 25 56 39 57 41 ...
output:
347869842
result:
ok single line: '347869842'
Test #51:
score: 0
Accepted
time: 23ms
memory: 4840kb
input:
73 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 18 34 32 35 32 36 26 37 31 38 32 39 23 40 11 41 12 42 18 43 36 44 18 45 26 46 22 47 45 48 25 49 18 50 13 51 27 52 9 53 42 54 51 55 54 56 10 57 11...
output:
320963094
result:
ok single line: '320963094'
Test #52:
score: 0
Accepted
time: 20ms
memory: 4916kb
input:
70 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 21 35 10 36 20 37 27 38 9 39 28 40 17 41 2 42 20 43 21 44 16 45 19 46 18 47 13 48 4 49 12 50 22 51 16 52 44 53 13 54 27 55 7 56 47 57 44 58 ...
output:
203034247
result:
ok single line: '203034247'
Test #53:
score: 0
Accepted
time: 32ms
memory: 4312kb
input:
75 1 2 1 3 1 4 3 5 1 6 4 7 6 8 2 9 2 10 3 11 4 12 2 13 1 14 2 15 11 16 10 17 2 18 8 19 13 20 17 21 4 22 6 23 16 24 5 25 3 26 5 27 2 28 5 29 20 30 22 31 6 32 17 33 2 34 7 35 4 36 16 37 7 38 22 39 7 40 27 41 5 42 42 43 38 44 20 45 23 46 36 47 46 48 14 49 23 50 26 51 18 52 4 53 51 54 41 55 54 56 25 57 ...
output:
917400836
result:
ok single line: '917400836'
Test #54:
score: 0
Accepted
time: 35ms
memory: 4260kb
input:
76 1 2 1 3 2 4 1 5 4 6 3 7 6 8 8 9 1 10 3 11 3 12 4 13 11 14 3 15 5 16 6 17 17 18 3 19 13 20 6 21 4 22 16 23 22 24 5 25 11 26 8 27 17 28 8 29 15 30 30 31 25 32 20 33 11 34 8 35 33 36 27 37 29 38 5 39 8 40 4 41 31 42 32 43 27 44 1 45 39 46 39 47 43 48 35 49 44 50 9 51 10 52 26 53 5 54 25 55 17 56 12 ...
output:
716634289
result:
ok single line: '716634289'
Test #55:
score: 0
Accepted
time: 40ms
memory: 4364kb
input:
74 1 2 1 3 2 4 1 5 2 6 6 7 5 8 1 9 4 10 10 11 7 12 7 13 6 14 13 15 10 16 15 17 14 18 12 19 2 20 4 21 19 22 9 23 5 24 21 25 17 26 17 27 19 28 11 29 5 30 16 31 5 32 30 33 11 34 29 35 14 36 29 37 4 38 11 39 1 40 4 41 6 42 1 43 36 44 29 45 7 46 36 47 38 48 40 49 14 50 36 51 33 52 48 53 23 54 38 55 18 56...
output:
920487193
result:
ok single line: '920487193'
Test #56:
score: 0
Accepted
time: 33ms
memory: 4380kb
input:
70 1 2 2 3 1 4 2 5 4 6 5 7 7 8 5 9 6 10 3 11 2 12 4 13 10 14 5 15 8 16 3 17 14 18 4 19 2 20 12 21 4 22 11 23 8 24 21 25 25 26 13 27 15 28 23 29 9 30 16 31 9 32 27 33 15 34 12 35 8 36 12 37 7 38 37 39 16 40 24 41 36 42 21 43 29 44 30 45 38 46 3 47 6 48 42 49 37 50 1 51 3 52 30 53 12 54 3 55 3 56 33 5...
output:
689277044
result:
ok single line: '689277044'
Test #57:
score: 0
Accepted
time: 36ms
memory: 4264kb
input:
71 1 2 2 3 2 4 3 5 2 6 1 7 7 8 3 9 2 10 6 11 10 12 9 13 4 14 2 15 14 16 16 17 14 18 14 19 4 20 5 21 16 22 7 23 20 24 16 25 24 26 26 27 14 28 16 29 12 30 14 31 20 32 14 33 25 34 18 35 25 36 22 37 24 38 4 39 32 40 3 41 24 42 30 43 21 44 25 45 21 46 7 47 17 48 42 49 20 50 16 51 45 52 18 53 7 54 47 55 4...
output:
358090698
result:
ok single line: '358090698'
Test #58:
score: 0
Accepted
time: 42ms
memory: 4308kb
input:
73 1 2 1 3 2 4 4 5 5 6 6 7 7 8 2 9 7 10 6 11 9 12 11 13 4 14 10 15 8 16 9 17 11 18 9 19 19 20 1 21 12 22 5 23 6 24 4 25 18 26 20 27 25 28 13 29 10 30 18 31 5 32 2 33 19 34 26 35 19 36 14 37 7 38 9 39 26 40 26 41 37 42 36 43 43 44 17 45 13 46 1 47 4 48 40 49 17 50 8 51 12 52 29 53 19 54 1 55 15 56 20...
output:
959769486
result:
ok single line: '959769486'
Test #59:
score: 0
Accepted
time: 40ms
memory: 4360kb
input:
72 1 2 2 3 2 4 4 5 5 6 2 7 3 8 3 9 4 10 6 11 9 12 10 13 12 14 11 15 8 16 14 17 9 18 8 19 15 20 16 21 16 22 18 23 12 24 13 25 15 26 20 27 25 28 2 29 18 30 7 31 29 32 9 33 20 34 28 35 3 36 13 37 17 38 15 39 16 40 30 41 4 42 27 43 34 44 34 45 22 46 2 47 19 48 36 49 28 50 37 51 40 52 23 53 9 54 20 55 42...
output:
513471410
result:
ok single line: '513471410'
Test #60:
score: 0
Accepted
time: 34ms
memory: 4392kb
input:
76 1 2 1 3 3 4 1 5 1 6 3 7 5 8 4 9 8 10 1 11 4 12 10 13 6 14 8 15 3 16 10 17 9 18 10 19 4 20 8 21 11 22 7 23 2 24 10 25 16 26 25 27 13 28 2 29 28 30 15 31 16 32 23 33 14 34 33 35 31 36 8 37 31 38 36 39 14 40 15 41 14 42 15 43 4 44 39 45 42 46 24 47 34 48 40 49 31 50 33 51 15 52 41 53 43 54 45 55 48 ...
output:
632208880
result:
ok single line: '632208880'
Test #61:
score: 0
Accepted
time: 33ms
memory: 4320kb
input:
74 1 2 1 3 2 4 2 5 5 6 6 7 4 8 4 9 6 10 2 11 3 12 4 13 2 14 2 15 5 16 14 17 2 18 10 19 1 20 5 21 15 22 6 23 11 24 9 25 10 26 19 27 24 28 23 29 18 30 20 31 29 32 9 33 30 34 27 35 2 36 28 37 4 38 17 39 8 40 12 41 16 42 15 43 38 44 23 45 41 46 19 47 18 48 28 49 22 50 49 51 35 52 41 53 32 54 13 55 38 56...
output:
139851470
result:
ok single line: '139851470'
Test #62:
score: 0
Accepted
time: 32ms
memory: 4480kb
input:
73 1 2 2 3 1 4 2 5 1 6 1 7 6 8 1 9 5 10 10 11 10 12 1 13 10 14 13 15 9 16 10 17 3 18 8 19 14 20 20 21 1 22 3 23 3 24 4 25 7 26 5 27 11 28 21 29 6 30 11 31 30 32 10 33 23 34 25 35 3 36 22 37 18 38 15 39 8 40 20 41 10 42 1 43 27 44 12 45 29 46 37 47 18 48 47 49 16 50 17 51 14 52 17 53 43 54 23 55 48 5...
output:
248495359
result:
ok single line: '248495359'