QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#229814#7632. Balanced Arraysucup-team022#RE 2ms9812kbC++171.8kb2023-10-28 16:58:082023-10-28 16:58:09

Judging History

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

  • [2023-10-28 16:58:09]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:9812kb
  • [2023-10-28 16:58:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n, m, jc[1000005], ny[1000005];
int C(int x, int y) {
	if (x < y || y < 0 || x < 0) return 0;
	return 1ll * jc[x] * ny[y] % mod * ny[x - y] % mod;
}
int Power(int x, int y) {
	int r = 1;
	while (y) {
		if (y & 1) r = 1ll * r * x % mod;
		x = 1ll * x * x % mod, y >>= 1;
	}
	return r;
}
// int f[500005][5][5];
int f[105][105][105];
void upd(int &x, int y) { x = (x + y) % mod; }
int Get(int n, int m) {
	memset(f, 0, sizeof(f));
	for (int i = 0; i <= m; i++) {
		f[1][i][i] = 1;
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= m; k++) {
				for (int l = max(j - k, 0); l <= m; l++) {
					upd(f[i + 1][l][k - max(j - l, 0)], f[i][j][k]);
				}
			}
		}
	}
	int ans = 0;
	for (int j = 0; j <= m; j++)
		for (int k = 0; k <= m; k++) upd(ans, f[n][j][k]);
	return ans;
}
int h[500005];
int main() {
	cin >> n >> m;
	if (m <= 2) return cout << Get(n, m) << endl, 0;
	h[1] = Get(n, 1);
	h[2] = Get(n, 2);
	for (int i = 3; i <= m; i++) {
		int v1 = (mod - 1ll * n * (n + 1) % mod + mod - 2ll * i * i % mod) % mod;
		int v2 = (1ll * i * i - i + mod) % mod;
		h[i] = (mod - (1ll * v1 * h[i - 1] + 1ll * v2 * h[i - 2]) % mod * Power(i, mod - 2) % mod *
		                  Power(i + 1, mod - 2) % mod) %
		       mod;
	}
	//$(1 n+ 1 n^{2}) h_ {n} +(998243423+ 998244351 n^{2}) h_ {n-1} +(998244352 n+ 1 n^{2}) h_ {n-2}
	//=0 $
	//
	cout << h[m];
	/*cin >> n >> m, jc[0] = ny[0] = 1;
	for (int i = 1; i <= 1000000; i++) jc[i] = 1ll * jc[i - 1] * i % mod;
	ny[1000000] = Power(jc[1000000], mod - 2);
	for (int i = 1000000 - 1; i; i--) ny[i] = 1ll * ny[i + 1] * (i + 1) % mod;
	int ans = 0;
	for (int i = 0; i <= m; i++) {
	    // b[1]=i
	    for (int j = 0; j <= n - 1; j++) {
	        // j个位置<0
	    }
	}*/
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9812kb

input:

2 2

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Runtime Error

input:

500000 500000

output:


result: