QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#54423 | #2438. Minimum Spanning Trees | vme50 | WA | 28ms | 4048kb | C++14 | 1.8kb | 2022-10-08 16:17:53 | 2022-10-08 16:17:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 45
#define N1 805
#define M 15
#define C 125
#define MOD 1000000007
int T,n,m,c,o,a[M],bn[N][N],pw[M][N1],pw1[C][C];
int z[C],z1[C],ans[C],dp[M][N][C],dp1[M][N][C];
int add(int x,int y) {x+=y;return x<MOD?x:x-MOD;}
void W(int &x,int y) {x+=y;if(x>=MOD) x-=MOD;}
int qPow(int x,int y)
{int res=1;for(;y;y/=2,x=1ll*x*x%MOD) if(y&1) res=1ll*res*x%MOD;return res;}
void slv()
{
scanf("%d %d",&n,&m);c=(n-1)*(m-1);scanf("%d",&a[m]);
for(int i=0;i<m;++i) scanf("%d",&a[i]);for(int i=m-1;i>=0;--i) a[i]+=a[i+1];
for(int i=0;i<=n;++i) for(int j=0;j<=i;++j)
bn[i][j]=j?add(bn[i-1][j],bn[i-1][j-1]):1;
for(int i=0;i<=m;++i)
{pw[i][0]=1;for(int j=1;j<=n*(n-1)/2;++j) pw[i][j]=1ll*pw[i][j-1]*a[i]%MOD;}
for(int i=0;i<=c;++i)
{pw1[i][0]=dp[0][1][i]=1;for(int j=1;j<=c;++j) pw1[i][j]=1ll*pw1[i][j-1]*i%MOD;}
for(int i=1,t;i<=m;++i) for(int j=1;j<=n;++j)
{
for(int k=0;k<=c;++k) dp[i][j][k]=0,dp1[i][j][k]=dp[i-1][j][k];
for(int k=1;k<j;++k) for(int l=0;l<=c;++l)
{
t=1ll*dp1[i][j-k][l]%MOD*pw1[l][i-1]%MOD*bn[j-1][k-1]%MOD;
W(dp[i][j][l],1ll*dp[i][k][l]%MOD*pw[i][(j-k)*k]*t%MOD);
W(dp1[i][j][l],1ll*dp[i-1][k][l]%MOD*pw[i-1][(j-k)*k]*t%MOD);
}for(int k=0;k<=c;++k) dp[i][j][k]=add(dp1[i][j][k],MOD-dp[i][j][k]);
}for(int i=0;i<=c;++i) z[i]=ans[i]=0;z[0]=1;
for(int i=0;i<=c;++i) for(int j=i;j>=0;--j)
W(z[j+1],z[j]),z[j]=1ll*z[j]*(MOD-i)%MOD;
for(int i=0,t=1;i<=c;++i)
{
t=1;for(int j=0;j<=c;++j) if(i!=j) t=1ll*t*(i-j+MOD)%MOD;t=qPow(t,MOD-2);
for(int j=0;j<=c;++j)
{
z1[j]=i?1ll*add(z[j],j?MOD-z1[j-1]:0)*qPow(MOD-i,MOD-2)%MOD:z[j+1];
W(ans[j],1ll*z1[j]*dp[m][n][i]%MOD*t%MOD);
}
}o=qPow(100,MOD-n*(n-1)/2-1);
for(int i=0;i<=c;++i) printf("%lld ",1ll*ans[i]*o%MOD);putchar('\n');
}
int main() {scanf("%d",&T);while(T--) slv();return 0;}
详细
Test #1:
score: 0
Wrong Answer
time: 28ms
memory: 4048kb
input:
200 3 1 50 50 3 2 0 50 50 3 3 25 25 25 25 8 1 41 59 7 3 37 30 7 26 3 3 16 12 18 54 9 2 9 43 48 9 3 3 40 42 15 9 1 29 71 9 2 40 42 18 5 1 76 24 5 1 39 61 9 2 23 38 39 10 4 18 15 34 2 31 7 2 23 28 49 9 4 15 13 25 19 28 7 1 64 36 6 1 50 50 9 1 4 96 4 1 64 36 9 2 24 45 31 9 2 3 61 36 9 1 65 35 8 4 6 1 3...
output:
500000004 500000004 375000003 125000001 406250003 109375001 250000002 265625002 562500004 962815926 271344123 752195427 570711117 205140706 821281958 864276577 82901022 676933590 124843407 166990953 176114494 20421768 508793427 708608005 271088002 536992004 107032001 312824337 840406904 -75823...
result:
wrong answer 4th lines differ - expected: '858129220', found: '962815926 '