QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #454125 | #8526. Polygon II | ucup-team1525# | AC ✓ | 65ms | 8108kb | C++20 | 1.8kb | 2024-06-24 16:47:09 | 2024-06-24 16:47:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3;
const int mod=1e9+7;
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int ksm(ll x,int tp,int s=1){
for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
return s;
}
int C[N+5][N+5];
int ikp[N+5];
int n;
int a[N+5];
int f[55][N+5];
int g[N*2+5];
int ans;
void get0(int *f){
static int h[N+5];
int iv=1;
for(int i=1;i<=n;i++) iv=1ll*iv*i%mod;
iv=ksm(iv,mod-2);
for(int i=1;i<=n;i++)
h[i]=ksm(i,n,iv);
for(int i=1;i<=n;i++){
for(int j=0;j<=i;j++)
if(j&1) f[i]=(f[i]-1ll*C[n][j]*h[i-j])%mod;
else f[i]=(f[i]+1ll*C[n][j]*h[i-j])%mod;
if(f[i]<0)
f[i]+=mod;
}
for(int i=0;i<n;i++)
f[i]=sub(f[i+1],f[i]);
f[n]=0;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
ikp[0]=1;
for(int i=1;i<=n;i++)
ikp[i]=ksm(2,mod-2,ikp[i-1]);
C[0][0]=1;
for(int i=1;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=add(C[i-1][j],C[i-1][j-1]);
}
get0(f[0]);
for(int i=0;i<=50;i++){
int m=0;
for(int j=1;j<=n;j++){
if(a[j]==i)
ans=add(ans,f[i][0]);
if(a[j]>i)
m++;
}
ans=1ll*ans*ikp[m]%mod;
memset(g,0,sizeof g);
for(int j=0;j<=n;j++)
for(int k=0;k<=m;k++)
g[j+k]=(g[j+k]+1ll*f[i][j]*C[m][k])%mod;
for(int j=0;j<n*2;j++)
f[i+1][j/2]=(f[i+1][j/2]+1ll*g[j]*ikp[m])%mod;
// printf("%d\n",ans);
}
printf("%d\n",sub(1,ans));
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4096kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 0ms
memory: 4132kb
input:
10 39 11 25 1 12 44 10 46 27 15
output:
913863330
result:
ok 1 number(s): "913863330"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4388kb
input:
57 43 22 3 16 7 5 24 32 25 16 41 28 24 30 28 10 32 48 41 43 34 37 48 34 3 9 21 41 49 25 2 0 36 45 34 33 45 9 42 29 43 9 38 34 44 33 44 6 46 39 22 36 40 37 19 34 3
output:
400729664
result:
ok 1 number(s): "400729664"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4508kb
input:
100 44 32 6 6 6 44 12 32 6 9 23 12 14 23 12 14 23 49 6 14 32 23 49 9 32 24 23 6 32 6 49 23 12 44 24 9 14 6 24 44 24 23 44 44 49 32 49 12 49 49 24 49 12 23 3 14 6 3 3 6 12 3 49 24 49 24 24 32 23 32 49 14 3 24 49 3 32 14 44 24 49 3 32 23 49 44 44 9 23 14 49 9 3 6 44 24 3 3 12 44
output:
32585394
result:
ok 1 number(s): "32585394"
Test #8:
score: 0
Accepted
time: 16ms
memory: 7960kb
input:
1000 2 27 0 0 27 0 2 0 27 0 27 27 0 0 0 0 0 2 0 27 0 2 2 0 27 27 0 0 0 27 2 2 2 27 0 2 27 2 0 2 27 0 0 27 0 27 0 0 27 2 27 2 2 27 2 27 0 0 27 0 27 0 2 27 2 2 0 27 27 27 27 0 27 0 27 0 2 2 0 2 2 27 0 0 27 0 0 27 0 2 27 27 2 27 2 0 0 2 27 27 27 27 27 27 2 2 0 2 2 0 2 2 0 27 0 27 2 2 0 27 27 0 0 27 2 2...
output:
94588769
result:
ok 1 number(s): "94588769"
Test #9:
score: 0
Accepted
time: 39ms
memory: 8040kb
input:
1000 40 14 47 3 32 18 3 49 22 23 32 18 23 24 18 32 23 39 32 27 49 49 22 50 50 22 23 47 14 47 50 32 22 24 49 49 18 22 18 22 50 3 32 47 40 3 39 22 24 47 32 49 49 22 32 39 14 49 39 3 32 22 24 18 39 49 24 18 40 23 23 49 39 39 18 39 27 49 14 27 27 14 18 24 39 22 40 50 18 18 18 39 39 18 23 23 22 3 49 47 2...
output:
626481946
result:
ok 1 number(s): "626481946"
Test #10:
score: 0
Accepted
time: 29ms
memory: 7968kb
input:
1000 28 32 35 9 21 11 43 23 45 15 23 2 8 3 39 41 31 9 45 35 27 14 40 28 31 9 31 9 9 40 8 6 27 43 3 27 23 49 27 6 28 25 11 9 15 27 38 27 12 28 25 2 15 27 45 6 27 1 21 38 1 25 27 21 49 31 31 14 39 39 8 39 40 28 15 31 21 14 43 38 11 8 8 23 9 11 15 2 11 39 32 14 28 15 40 49 27 9 23 9 9 6 21 2 2 1 14 11 ...
output:
644443122
result:
ok 1 number(s): "644443122"
Test #11:
score: 0
Accepted
time: 31ms
memory: 7928kb
input:
972 39 15 23 0 40 29 43 47 6 9 30 9 2 8 19 9 45 25 26 38 33 18 6 33 44 48 24 8 4 16 33 42 33 31 36 33 13 16 3 12 21 19 1 30 24 23 43 35 0 33 31 32 23 31 36 12 26 0 29 48 28 33 28 28 3 49 9 5 29 8 29 28 49 41 33 49 5 49 6 9 50 25 39 11 1 36 6 44 10 34 32 31 25 31 36 36 3 9 50 35 47 43 25 46 30 18 5 2...
output:
684920840
result:
ok 1 number(s): "684920840"
Test #12:
score: 0
Accepted
time: 2ms
memory: 4680kb
input:
147 34 47 42 23 46 3 41 9 15 42 21 32 24 1 19 46 29 35 38 20 2 43 36 47 19 23 20 9 6 28 48 46 45 21 19 41 31 36 50 7 11 25 0 43 38 46 21 2 26 40 32 14 45 35 47 21 13 26 26 30 3 36 35 45 36 21 21 25 2 40 35 50 23 3 16 44 40 42 6 37 36 19 20 14 30 47 13 49 47 45 26 12 15 21 42 30 19 5 21 9 28 8 3 34 4...
output:
972735235
result:
ok 1 number(s): "972735235"
Test #13:
score: 0
Accepted
time: 36ms
memory: 8032kb
input:
1000 36 15 9 5 35 37 17 30 24 13 18 32 14 35 36 26 23 7 21 15 43 15 21 11 33 33 9 16 5 26 1 45 48 27 20 20 20 48 42 27 22 7 39 35 11 38 33 47 22 34 43 4 32 0 47 35 48 8 9 3 40 3 27 22 20 43 12 37 30 18 2 37 37 35 44 3 42 14 20 24 44 5 17 38 46 41 28 23 21 7 13 15 35 38 21 14 6 37 37 6 13 34 32 13 23...
output:
179933029
result:
ok 1 number(s): "179933029"
Test #14:
score: 0
Accepted
time: 36ms
memory: 8044kb
input:
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7...
output:
540327646
result:
ok 1 number(s): "540327646"
Test #15:
score: 0
Accepted
time: 33ms
memory: 8108kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 49 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 48 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 47 46 46 46 46 46 46 46 46 46 46 46 46 46 4...
output:
169647494
result:
ok 1 number(s): "169647494"
Test #16:
score: 0
Accepted
time: 65ms
memory: 8052kb
input:
1000 11 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 40 50 50 50 50 50 21 50 12 50 50 50 50 50 0 50 50 50 38 50 50 50 50 50 50 25 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 7 50 50 50 50 50 50 50 50 ...
output:
862643524
result:
ok 1 number(s): "862643524"
Test #17:
score: 0
Accepted
time: 63ms
memory: 7956kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...
output:
819612372
result:
ok 1 number(s): "819612372"
Test #18:
score: 0
Accepted
time: 63ms
memory: 7956kb
input:
1000 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 5...
output:
18215579
result:
ok 1 number(s): "18215579"
Test #19:
score: 0
Accepted
time: 1ms
memory: 4228kb
input:
16 0 2 24 1 23 9 14 17 28 29 25 27 15 19 11 20
output:
115090079
result:
ok 1 number(s): "115090079"
Test #20:
score: 0
Accepted
time: 4ms
memory: 7916kb
input:
1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
819612372
result:
ok 1 number(s): "819612372"
Test #21:
score: 0
Accepted
time: 1ms
memory: 4156kb
input:
18 9 4 21 5 22 6 9 16 3 14 11 2 0 12 6 3 7 21
output:
0
result:
ok 1 number(s): "0"
Extra Test:
score: 0
Extra Test Passed