QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54423#2438. Minimum Spanning Treesvme50WA 28ms4048kbC++141.8kb2022-10-08 16:17:532022-10-08 16:17:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-08 16:17:56]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:4048kb
  • [2022-10-08 16:17:53]
  • 提交

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 '