QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #556071 | #8526. Polygon II | Flamire | WA | 1ms | 4316kb | C++17 | 2.8kb | 2024-09-10 14:49:41 | 2024-09-10 14:49:45 |
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[55],ifac[55];
int A[55],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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4112kb
input:
3 0 2 0
output:
166666668
result:
ok 1 number(s): "166666668"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4188kb
input:
3 0 0 0
output:
500000004
result:
ok 1 number(s): "500000004"
Test #3:
score: 0
Accepted
time: 0ms
memory: 4108kb
input:
3 5 6 7
output:
208333335
result:
ok 1 number(s): "208333335"
Test #4:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
3 0 25 50
output:
889268532
result:
ok 1 number(s): "889268532"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4140kb
input:
10 39 11 25 1 12 44 10 46 27 15
output:
913863330
result:
ok 1 number(s): "913863330"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 4316kb
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:
124533415
result:
wrong answer 1st numbers differ - expected: '400729664', found: '124533415'