QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#738799#7875. Queue SortingFluoresceAC ✓88ms5656kbC++201.1kb2024-11-12 19:58:552024-11-12 19:58:57

Judging History

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

  • [2024-11-12 19:58:57]
  • 评测
  • 测评结果:AC
  • 用时:88ms
  • 内存:5656kb
  • [2024-11-12 19:58:55]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 507, mod = 998244353;


int a[N], sum[N], dp[N][N], c[N][N];
int n;

void solve(){
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin>>a[i];
		sum[i] = sum[i - 1] + a[i];
	}

	c[0][0] = 1;
	for(int i = 1; i <= sum[n]; i++) {
		c[i][0] = 1;
		for(int j = 1; j <= i; j++) 
			c[i][j] = (c[i][j] + c[i - 1][j - 1] + c[i - 1][j]) % mod;
	}

	dp[0][0] = 1;
	for(int i = 0; i < n; i++) 
		for(int j = 0; j <= sum[i]; j++) if (dp[i][j]) {
			dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
			for (int k = j + 1; k < sum[i + 1]; k++) { 
				//  如果边界比较复杂,可以使用if 代替直接计算
				int lb = max(0, a[i + 1] - (k - j));
				int ub = min(a[i + 1] - 1, sum[i + 1] - k - 1);
				for(int x = lb; x <= ub; x++) 
					dp[i + 1][k] = (dp[i+1][k] + (1ll * dp[i][j] * c[k - j - 1][a[i + 1] - x - 1] % mod)) % mod;
			}
		}

	int ans = 0;
	for(int i = 0; i <= sum[n]; i++) ans = (ans + dp[n][i]) % mod;
	cout<<ans<<'\n';
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while(t--)
		solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3668kb

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 75ms
memory: 5244kb

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:

507010274

result:

ok 1 number(s): "507010274"

Test #3:

score: 0
Accepted
time: 88ms
memory: 5656kb

input:

500
1 1 0 2 1 0 2 3 2 0 0 2 0 2 1 1 0 0 1 1 1 2 1 1 1 0 1 1 2 2 1 4 0 2 1 0 2 3 1 0 1 1 0 2 1 2 2 1 0 0 3 1 4 1 1 2 1 1 0 1 3 1 2 0 0 0 2 1 2 0 0 3 2 1 1 1 1 1 2 1 0 1 0 0 0 1 0 0 2 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 0 0 1 0 0 0 2 1 1 0 1 1 0 1 1 0 0 1 0 3 1 3 0 0 2 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 2 0 0 ...

output:

7590964

result:

ok 1 number(s): "7590964"

Test #4:

score: 0
Accepted
time: 73ms
memory: 4976kb

input:

200
3 1 0 3 2 1 0 3 1 1 2 3 3 1 6 2 1 3 2 1 1 2 1 2 1 5 2 2 3 4 0 4 2 1 2 2 0 2 3 1 2 3 6 3 2 3 2 2 4 2 7 2 1 5 1 9 0 4 4 8 3 3 3 1 3 0 2 2 8 1 3 5 4 3 0 6 1 6 1 3 4 2 2 1 1 4 4 4 1 0 4 3 4 3 3 0 3 2 0 0 3 4 0 3 1 3 2 4 3 2 0 3 2 2 3 2 2 2 1 2 2 1 0 2 0 3 1 3 5 1 3 3 6 5 3 2 2 2 3 6 2 0 5 2 2 2 2 1 ...

output:

507844569

result:

ok 1 number(s): "507844569"

Test #5:

score: 0
Accepted
time: 15ms
memory: 4384kb

input:

100
4 8 2 5 4 4 3 0 2 7 2 3 4 4 1 2 3 4 4 4 3 3 3 3 3 2 4 1 3 5 5 1 4 6 1 1 1 3 2 3 2 1 0 1 4 4 2 4 2 5 3 5 1 6 2 3 3 1 4 4 4 1 4 4 3 4 2 0 2 3 6 1 3 3 5 4 1 1 2 3 0 3 2 2 1 3 3 2 5 6 3 2 3 3 5 4 2 3 4 4

output:

989550242

result:

ok 1 number(s): "989550242"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 4576kb

input:

500
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

1

result:

ok 1 number(s): "1"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3712kb

input:

10
2 1 3 3 2 3 1 1 3 1

output:

165452340

result:

ok 1 number(s): "165452340"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

20
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0

output:

2

result:

ok 1 number(s): "2"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

20
0 0 1 0 0 0 0 1 0 0 0 0 0 0 2 0 1 0 0 0

output:

28

result:

ok 1 number(s): "28"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

10
1 1 1 1 1 1 1 1 1 1

output:

16796

result:

ok 1 number(s): "16796"

Test #12:

score: 0
Accepted
time: 21ms
memory: 4864kb

input:

300
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

431279497

result:

ok 1 number(s): "431279497"

Test #13:

score: 0
Accepted
time: 1ms
memory: 4584kb

input:

2
232 268

output:

929717758

result:

ok 1 number(s): "929717758"

Test #14:

score: 0
Accepted
time: 1ms
memory: 4648kb

input:

1
500

output:

1

result:

ok 1 number(s): "1"

Test #15:

score: 0
Accepted
time: 33ms
memory: 4664kb

input:

3
155 180 165

output:

911108550

result:

ok 1 number(s): "911108550"

Extra Test:

score: 0
Extra Test Passed