QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #448843 | #8526. Polygon II | marher | AC ✓ | 213ms | 4584kb | C++14 | 1.2kb | 2024-06-20 09:50:52 | 2024-06-20 09:50:53 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e3+50,mod=1e9+7;
int ksm(int a,int b)
{
int ans=1;
while(b)
{
if(b&1)ans=ans*a%mod;
b>>=1;a=a*a%mod;
}
return ans;
}
int n,a[N],f[80][N],cm[N],icm[N],ans,cc[55];
int binom(int n,int m)
{
if(n<m)return 0;
return cm[n]*icm[m]%mod*icm[n-m]%mod;
}
void ad(int&x,int y)
{
x+=y;
x-=x>=mod?mod:0;
}
main()
{
cin>>n;
cm[0]=icm[0]=1;
for(int i=1;i<=n;i++)cm[i]=cm[i-1]*i%mod,icm[i]=ksm(cm[i],mod-2);
for(int i=1;i<=n;i++)cin>>a[i],++cc[a[i]];
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)ad(f[0][i],((j&1)?mod-1:1)*binom(n,j)%mod*ksm(i-j,n)%mod*icm[n]%mod);
for(int i=n;i>=1;i--)f[0][i]=(f[0][i]-f[0][i-1]+mod)%mod;
for(int i=0;i<=50;i++)
{
int tot=0,num=0;
for(int j=1;j<=n;j++)if(a[j]>i)tot+=a[j]-i;
for(int j=1;j<=n;j++)num+=a[j]>i;
ad(ans,(f[i][0]+f[i][1])*cc[i]%mod*ksm((mod+1)/2,tot)%mod);
for(int k=0;k<=num;k++)
{
int p=binom(num,k)*ksm((mod+1)/2,num)%mod;
for(int j=0;j<=2*n;j++)ad(f[i+1][(j+k+1)/2],f[i][j]*p%mod);
}
}
cout<<(1+mod-ans)%mod<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3708kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3936kb
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: 3936kb
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: 2ms
memory: 3788kb
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: 56ms
memory: 4292kb
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: 134ms
memory: 4444kb
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: 104ms
memory: 4424kb
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: 111ms
memory: 4328kb
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: 0ms
memory: 3772kb
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: 114ms
memory: 4228kb
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: 112ms
memory: 4340kb
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: 116ms
memory: 4360kb
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: 205ms
memory: 4584kb
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: 213ms
memory: 4496kb
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: 213ms
memory: 4368kb
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: 3788kb
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: 4212kb
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: 0ms
memory: 3852kb
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