QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276206#7875. Queue SortingshmWA 71ms5404kbC++141.4kb2023-12-05 18:07:222023-12-05 18:07:24

Judging History

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

  • [2023-12-05 18:07:24]
  • 评测
  • 测评结果:WA
  • 用时:71ms
  • 内存:5404kb
  • [2023-12-05 18:07:22]
  • 提交

answer

#include <iostream>
using namespace std;

const int mod=998244353,N=505;
int dp[N][N];
int a[N];

int c[505][505]; // c[i][j] --> c[5][2]==10

void init()
{
	for(int i=0; i<505; i++)
		c[i][0] = 1;
    for(int i=1; i<505; i++)
        for(int j=0; j<=i; j++)
        {
            if(j==0)
                c[i][j]=1;
            else
                c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
}

int C(int x, int y)
{
	return c[x][y];
}

int main()
{
	init();
	int n; scanf("%d", &n);
	for(int i=1; i<=n; i++) scanf("%d", &a[i]);
	dp[0][0] = 1;
	int sum = 0;
	for(int i=0; i<n; i++,sum+=a[i])
	{
		// 全部放前面 
		for(int j=2; j<=sum; j++)
			dp[i+1][j+a[i+1]] = dp[i][j];
		dp[i+1][0] = dp[i][0];
		//枚举前面放多少个(后面至少放一个)
		for(int x=0; x<a[i+1]; x++)
		{
			//枚举剩余部分从哪个位置后面开始放 
			for(int k=1; k<=sum; k++)
			{
				for(int j=k+1; j<=sum; j++)
					dp[i+1][k+1+x] = (1ll*dp[i+1][k+1+x] + 1ll*dp[i][j] * C(j - k - 1 + a[i+1] - x - 1, a[i+1] - x - 1)) % mod;
					
				//j == 0 的情况 
				dp[i+1][k+1+x] = (1ll*dp[i+1][k+1+x] + 1ll*dp[i][0] * C(sum - k + a[i+1] - x - 1, a[i+1] - x - 1)) % mod;
			}
		}
	}
//	cout << dp[3][0] << " " << dp[3][2] << " " << dp[3][3] << '\n';
//	cout << dp[2][0] << " " << dp[2][2]  <<  "  " << dp[1][0]<< '\n';
	int ans = 0;
	for(int i=0; i<=sum; i++) ans = (1ll*ans + dp[n][i])%mod;
	cout << ans << '\n'; 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4624kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: -100
Wrong Answer
time: 71ms
memory: 5404kb

input:

300
0 5 2 2 1 0 3 2 2 5 2 1 1 2 1 3 2 3 2 0 0 0 0 1 2 2 3 0 2 2 3 2 0 2 3 0 6 0 0 2 0 1 3 2 1 1 1 3 4 0 1 0 4 1 1 1 1 1 1 2 3 2 1 2 3 2 3 0 5 3 3 2 0 1 1 0 2 1 1 2 0 0 2 1 1 3 2 2 1 2 1 3 0 3 0 1 2 2 0 5 0 2 2 0 0 0 1 2 1 4 2 1 1 0 3 0 2 0 3 1 1 2 0 2 1 1 0 2 0 1 2 2 3 3 1 1 1 1 0 1 3 3 1 0 2 2 4 2 ...

output:

964989333

result:

wrong answer 1st numbers differ - expected: '507010274', found: '964989333'