QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276206 | #7875. Queue Sorting | shm | WA | 71ms | 5404kb | C++14 | 1.4kb | 2023-12-05 18:07:22 | 2023-12-05 18:07:24 |
Judging History
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'