QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#446443 | #8526. Polygon II | PhantomThreshold | AC ✓ | 334ms | 4324kb | C++17 | 1.8kb | 2024-06-17 10:44:51 | 2024-06-17 10:44:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll inv2=(mod+1)/2;
inline ll ksm(ll a,ll x){
ll ret=1;
for (;x;x>>=1,a=a*a%mod) if (x&1) ret=ret*a%mod;
return ret;
}
inline ll inv(ll a){return ksm(a,mod-2);}
void add(ll &A,ll B){A+=B;if (A>=mod) A-=mod;}
void sub(ll &A,ll B){A-=B;if (A<0) A+=mod;}
const int maxn=2000;
ll fac[maxn+50];
ll ifac[maxn+50];
void prepare(){
fac[0]=1;
for (int i=1;i<=maxn;i++) fac[i]=fac[i-1]*i%mod;
ifac[maxn]=inv(fac[maxn]);
for (int i=maxn-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
// for (int i=0;i<=5;i++) cout << fac[i] << " ";
// cout << endl;
// for (int i=0;i<=5;i++) cout << ifac[i] << " ";
// cout << endl;
}
ll C(ll n,ll m){
if (m<0 || m>n) return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
ll n;
ll a[maxn+50];
ll cnt[55];
ll sum[55];
ll dp[55][maxn+50];
int main(){
ios_base::sync_with_stdio(false);
prepare();
cin >> n;
for (int i=1;i<=n;i++){
cin >> a[i];
for (int j=0;j<a[i];j++) cnt[j]++;
}
for (int i=50;i>=0;i--) sum[i]=sum[i+1]+cnt[i];
for (int i=1;i<=n;i++){
for (int j=0;j<=i;j++){
ll res=ksm(i-j,n)*C(n,j)%mod*ifac[n]%mod;
if (j%2==0) add(dp[0][i-1],res);
else sub(dp[0][i-1],res);
}
}
for (int i=n-1;i>=1;i--) sub(dp[0][i],dp[0][i-1]);
int lim=n-1;
for (int i=0;i<=50;i++){
ll invr=ksm(inv2,cnt[i]);
int mx=0;
for (int j=0;j<=lim;j++){
for (int l=0;l<=cnt[i];l++){
ll coef=C(cnt[i],l)*invr%mod;
int index=(j+l)/2;
mx=max(mx,index);
add(dp[i+1][index],dp[i][j]*coef%mod);
}
}
lim=mx;
}
ll ans=0;
for (int i=1;i<=n;i++){
add(ans,dp[a[i]][0]*ksm(inv2,sum[a[i]])%mod);
}
ans=(mod+1-ans)%mod;
cout << ans << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3944kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3904kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3816kb
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: 3828kb
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: 3948kb
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: 48ms
memory: 3912kb
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: 166ms
memory: 4100kb
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: 118ms
memory: 4000kb
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: 127ms
memory: 4040kb
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: 4ms
memory: 3816kb
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: 127ms
memory: 4036kb
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: 133ms
memory: 3984kb
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: 128ms
memory: 3988kb
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: 321ms
memory: 4324kb
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: 330ms
memory: 4284kb
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: 334ms
memory: 4232kb
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: 3940kb
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: 21ms
memory: 3904kb
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: 3828kb
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