QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882925#7875. Queue SortingxuyiyangAC ✓300ms4864kbC++141.6kb2025-02-05 13:33:192025-02-05 13:33:20

Judging History

This is the latest submission verdict.

  • [2025-02-05 13:33:20]
  • Judged
  • Verdict: AC
  • Time: 300ms
  • Memory: 4864kb
  • [2025-02-05 13:33:19]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 510, mod = 998244353;
typedef long long LL;

int n, m, w[N];
int fc[N], ifc[N];
int f[N][N], g[N][N];

int inv(int x) {
	int y = mod - 2, z = 1;
	while (y) {
		if (y & 1) z = (LL)z * x % mod;
		x = (LL)x * x % mod; y >>= 1;
	} return z; 
}
int binom(int x, int y) {
	if (x < 0 || y < 0 || x < y) return 0;
	return (LL)fc[x] * ifc[y] % mod * ifc[x - y] % mod;
}
inline void addt(int &x, int y) { x += y, x >= mod && (x -= mod); }

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]), m += w[i];
	
	fc[0] = ifc[0] = 1;
	for (int i = 1; i <= m; i ++ ) {
		fc[i] = (LL)fc[i - 1] * i % mod;
		ifc[i] = inv(fc[i]);
	}
	
	f[1][0] = 1;
	for (int i = 1, s = w[1]; i < n; i ++ , s += w[i]) {
		// 0 
		addt(f[i + 1][0], f[i][0]);
		for (int k = 1; k <= s; k ++ ) {
			for (int x = 0; x < w[i + 1]; x ++ ) {
				int val = binom(s - k + w[i + 1] - x - 1, w[i + 1] - x - 1);
				addt(f[i + 1][x + k + 1], (LL)f[i][0] * val % mod);
			} // k + 1 ~ s
		}
		for (int j = 1; j <= m; j ++ ) {
			addt(f[i + 1][j + w[i + 1]], f[i][j]);
			for (int k = 1; k < j; k ++ ) {
				for (int x = 0; x < w[i + 1]; x ++ ) {
					int val = binom(j - k - 1 + w[i + 1] - x - 1, w[i + 1] - x - 1);
					addt(f[i + 1][x + k + 1], (LL)f[i][j] * val % mod);
				}
			}
		}
	} 
//	for (int i = 1; i <= n; i ++ , puts("")) for (int j = 0; j <= m; j ++ ) cout << f[i][j] << ' ';
	int res = 0;
	for (int i = 0; i <= m; i ++ ) addt(res, f[n][i]);
	printf("%d\n", res); return 0;
}

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

詳細信息

Test #1:

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

input:

4
1 1 1 1

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 0
Accepted
time: 281ms
memory: 4480kb

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: 300ms
memory: 4864kb

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: 269ms
memory: 4224kb

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: 56ms
memory: 3968kb

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: 3840kb

input:

1
1

output:

1

result:

ok 1 number(s): "1"

Test #7:

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

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: 1ms
memory: 3840kb

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: 1ms
memory: 3840kb

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: 3840kb

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: 3840kb

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: 67ms
memory: 4480kb

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: 128ms
memory: 3840kb

input:

2
232 268

output:

929717758

result:

ok 1 number(s): "929717758"

Test #14:

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

input:

1
500

output:

1

result:

ok 1 number(s): "1"

Test #15:

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

input:

3
155 180 165

output:

911108550

result:

ok 1 number(s): "911108550"

Extra Test:

score: 0
Extra Test Passed