QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#229814 | #7632. Balanced Arrays | ucup-team022# | RE | 2ms | 9812kb | C++17 | 1.8kb | 2023-10-28 16:58:08 | 2023-10-28 16:58:09 |
Judging History
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