QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #555208 | #8526. Polygon II | tx344 | WA | 153ms | 4292kb | C++14 | 1.6kb | 2024-09-09 20:36:34 | 2024-09-09 20:36:35 |
Judging History
answer
//
#include<bits/stdc++.h>
#define ll long long
#define ld double
#define PII pair<int,int>
#define PLI pair<ll,int>
#define fi first
#define se second
#define iter set<PII>::iterator
using namespace std;
const int N=1005,M=55,Mod=1e9+7;
int n,a[N],f[M][N],b[N],fac[N],inv[N],ifac[N],ipw2[N],ans=1;
int C(int x,int y){return (ll)fac[x]*ifac[y]%Mod*ifac[x-y]%Mod;}
int ksm(int x,int y=Mod-2)
{
int z=1;
while(y){if(y&1)z=(ll)z*x%Mod;x=(ll)x*x%Mod;y>>=1;}
return z;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
fac[0]=ifac[0]=inv[0]=inv[1]=ipw2[0]=1;
for(int i=2;i<N;i++)inv[i]=(ll)(Mod-Mod/i)*inv[Mod%i]%Mod;
for(int i=1;i<N;i++)fac[i]=(ll)fac[i-1]*i%Mod,ifac[i]=(ll)ifac[i-1]*inv[i]%Mod,ipw2[i]=(ll)ipw2[i-1]*inv[2]%Mod;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),++b[a[i]];
for(int i=49;~i;i--)b[i]+=b[i+1];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
(f[0][i]+=(ll)(j&1?Mod-1:1)*C(n,j)%Mod*ksm(i+1-j,n)%Mod)%=Mod;
}
// printf("%d ",f[0][i]);
}
// puts("");
for(int i=n-1;i;i--)(f[0][i]+=Mod-f[0][i-1])%=Mod;
for(int i=1;i<=50;i++)
{
for(int j=0;j<=n*2;j++)
{
for(int k=0;k<=b[i];k++)
{
(f[i][(j+k)/2]+=(ll)f[i-1][j]*C(b[i],k)%Mod*ipw2[b[i]]%Mod)%=Mod;
// printf("%d %d %d\n",i,j,k),fflush(stdout);
}
// if(f[i-1][j])printf("%d %d %d\n",i-1,j,4ll*f[i-1][j]%Mod);
}
}
for(int i=50,sum=(ll)(Mod-1)*ifac[n]%Mod;~i;i--)
{
ans=(ans+(ll)sum*f[i][0]%Mod*(b[i]-b[i+1]))%Mod;
sum=(ll)sum*ipw2[b[i]]%Mod;
}
printf("%d\n",ans);
cerr<<1.0*clock()/CLOCKS_PER_SEC<<'\n';
}
/*
4
1 2 1 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4240kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4292kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 1ms
memory: 4244kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4116kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4176kb
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: 2ms
memory: 4240kb
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: 4ms
memory: 4236kb
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: -100
Wrong Answer
time: 153ms
memory: 4248kb
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:
312816408
result:
wrong answer 1st numbers differ - expected: '94588769', found: '312816408'