QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #556074 | #8526. Polygon II | Flamire | AC ✓ | 144ms | 8164kb | C++17 | 2.8kb | 2024-09-10 14:50:49 | 2024-09-10 14:50:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int p=1e9+7;
inline int qpow(int bs,int ex){int ans=1;while(ex){if(ex&1)ans=1ll*ans*bs%p;ex>>=1;bs=1ll*bs*bs%p;}return ans;}
int n,a[1011],cnt[55],C[1011][1011],fac[2011],ifac[2011];
int A[2011],dp[55][1011],ndp[2011],deno[2011],ans[55];
const int K=50;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",a+i),++cnt[a[i]];
for(int i=0;i<=K;++i)if(cnt[i])
{
deno[i]=cnt[i];
for(int j=0;j<=K;++j)
{
deno[i]=1ll*deno[i]*qpow(qpow(qpow(2,j),cnt[j]),p-2)%p;
// printf("deno[%d]:%d\n",i,deno[i]);
}
}
for(int i=K;~i;--i)cnt[i]+=cnt[i+1];
fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%p;
ifac[n]=qpow(fac[n],p-2);for(int i=n-1;~i;--i)ifac[i]=1ll*ifac[i+1]*(i+1)%p;
C[0][0]=1;for(int i=1;i<=n;++i)C[i][0]=C[i][i]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
// for(int i=0;i<=n;++i)
// {
// for(int j=0;j<=n;++j)printf("%d ",C[i][j]);putchar(10);
// }
// printf("ifac:");for(int i=0;i<=n;++i)printf("%d ",ifac[i]);putchar(10);
for(int i=1;i<n;++i)
{
for(int j=0;j<=i;++j)
{
A[i]=(A[i]+(j&1?-1ll:1ll)*C[n-1][j]*qpow(i-j,n)%p*ifac[n])%p;
}
}
A[n]=1;
// printf("A:");for(int i=0;i<=n;++i)printf("%d ",A[i]);putchar(10);
for(int i=0;i<=n-2;++i)A[i]=(A[i+1]-A[i])%p;
// printf("A:");for(int i=0;i<=n;++i)printf("%d ",A[i]);putchar(10);
memset(dp,0,sizeof(dp));
dp[0][n-1]=1;
// printf("cnt:");for(int i=0;i<=K;++i)printf("%d ",cnt[i]);putchar(10);
// printf("deno:");for(int i=0;i<=K;++i)printf("%d ",deno[i]);putchar(10);
for(int i=1;i<=K;++i)
{
for(int j=0;j<=2*n+1;++j)ndp[j]=0;
for(int j=0;j<=n;++j)
{
for(int k=0;k<=cnt[i];++k)
{
ndp[j+k]=(ndp[j+k]+1ll*dp[i-1][j]*C[cnt[i]][k])%p;
}
}
// printf("ndp:");for(int j=0;j<=2*n+1;++j)printf("%d ",ndp[j]);putchar(10);
for(int j=0;j<=n;++j)dp[i][j]=(ndp[2*j]+ndp[2*j+1])%p;
ans[i]=(ans[i]+dp[i][0])%p;
// printf("dp[%d]:",i);for(int j=0;j<=n;++j)printf("%d ",dp[i][j]);putchar(10);
}
// for(int j=0;j<=K;++j)printf("%d ",ans[j]);putchar(10);
memset(dp,0,sizeof(dp));
for(int w=0;w<n-1;++w)dp[0][w]=A[w];
ans[0]=(ans[0]+dp[0][0])%p;
for(int i=1;i<=K;++i)
{
for(int j=0;j<=2*n+1;++j)ndp[j]=0;
for(int j=0;j<=n;++j)
{
for(int k=0;k<cnt[i];++k)
{
ndp[j+k]=(ndp[j+k]+1ll*dp[i-1][j]*C[cnt[i]-1][k])%p;
}
}
// printf("ndp:");for(int j=0;j<=2*n+1;++j)printf("%d ",ndp[j]);putchar(10);
for(int j=0;j<=n;++j)dp[i][j]=(ndp[2*j]+ndp[2*j+1])%p;
ans[i]=(ans[i]+dp[i][0])%p;
// printf("dp[%d]:",i);for(int j=0;j<=n;++j)printf("%d ",dp[i+1][j]);putchar(10);
}
// for(int j=0;j<=K;++j)printf("%d ",ans[j]);putchar(10);
int res=0;
for(int j=0;j<=K;++j)res=(res+1ll*deno[j]*ans[j])%p;
printf("%d\n",((1-res)%p+p)%p);
fclose(stdin);fclose(stdout);return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4212kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5964kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4164kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4172kb
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: 4280kb
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: 4528kb
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: 43ms
memory: 8156kb
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: 91ms
memory: 8120kb
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: 78ms
memory: 8120kb
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: 79ms
memory: 7868kb
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: 3ms
memory: 4716kb
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: 78ms
memory: 8124kb
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: 83ms
memory: 8112kb
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: 83ms
memory: 8116kb
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: 141ms
memory: 8100kb
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: 144ms
memory: 8036kb
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: 144ms
memory: 8164kb
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: 4220kb
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: 19ms
memory: 8116kb
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: 4208kb
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