QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #296100 | #4893. Imbalance | zyc070419 | 0 | 78ms | 20096kb | C++14 | 9.0kb | 2024-01-02 09:08:39 | 2024-01-02 09:08:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
inline int add(int x, int y) {x += y; return x >= mod ? x - mod : x;}
inline int del(int x, int y) {x -= y; return x < 0 ? x + mod : x;}
//inline void Add(int &x, int y) {x += y; (x >= mod && (x -= mod, x));}
//inline void Del(int &x, int y) {x -= y; (x < 0 && (x += mod, x));}
inline void Add(int &x, int y) {x = add(x, y);}
inline void Del(int &x, int y) {x = del(x, y);}
int n, k, m, a[200];
char s[200];
namespace subtask1 {
int dp[2][(1 << 22) + 3], opt, ans, cnt[(1 << 22) + 3];
void work() {
int o = k / 2;
// memset(dp, 0, sizeof(dp));
dp[opt][0] = 1;
for (int i = 1; i <= n; ++i) {
opt ^= 1;
for (int S = 0; S < (1 << k); ++S) dp[opt][S] = 0;
for (int S = 0, T; S < (1 << k); ++S) {
if (!dp[opt][S]) continue;
if (i > m || a[i] == 0) {
T = (S >> 1);
if (i < k || cnt[T] != o) Add(dp[opt][T], dp[opt ^ 1][S]);
}
if (i > m || a[i] == 1) {
T = (S >> 1) | (1 << (k - 1));
if (i < k || cnt[T] != o) Add(dp[opt][T], dp[opt ^ 1][S]);
}
}
}
for (int S = 0; S < (1 << k); ++S)
if (dp[opt][S]) Add(ans, dp[opt][S]);
}
void solve() {
for (int i = 1; i < (1 << k); ++i) cnt[i] = __builtin_popcount(i);
work();
printf("%d\n", ans);
}
}
namespace subtask2 {
const int Mod = 10997;
struct Hash_Table {
struct edge {
int to, nxt;
edge() {}
edge(int x, int y) {to = x; nxt = y;}
};
struct node {
vector<int> id;
int val;
node() {}
node(vector<int> x, int y) {id = x; val = y;}
};
vector<node> q;
vector<edge> e;
int link[Mod + 10];
inline int g(int x) {return (1ll * x * x % Mod * x % Mod + (x ^ 287) % Mod) % Mod + 1;}
inline int f(vector<int> &tmp) {
int res = 0;
for (auto x : tmp) res = (res + g(x)) % Mod;
return res;
}
void ins(vector<int> &tmp, int val) {
if (val == 0) return;
int ID = f(tmp); bool pd;
for (int i = link[ID], y; i; i = e[i].nxt) {
y = e[i].to; pd = true;
for (int j = 0; j < q[y].id.size(); ++j) pd &= (q[y].id[j] == tmp[j]);
if (pd) {
Add(q[y].val, val);
return;
}
}
q.push_back(node(tmp, val));
e.push_back(edge(q.size() - 1, link[ID]));
link[ID] = e.size() - 1;
}
void clear() {
e.clear(); e.push_back(edge());
q.clear();
for (int i = 1; i <= Mod; ++i) link[i] = 0;
}
}H[2];
int st[10], mx, opt, ans;
vector<int> now, nxt;
void work() {
H[0].clear(); H[1].clear();
now.resize(mx + 1);
for (int i = 0; i <= mx; ++i) now[i] = 0;
H[opt].ins(now, 1);
int pos;
for (int i = 1; i < k; ++i) {
for (int j = 0; j <= mx; ++j) {
pos = j * k + i;
opt ^= 1;
for (auto o : H[opt ^ 1].q) {
now = o.id;
if (pos > m || a[pos] == 0) {
nxt = now; bool pd = true;
if (j < mx && st[j] + nxt[j] + k - i - ((j + 1) * k <= m && a[(j + 1) * k] == 0) < st[j + 1]) pd = false;
if (j < mx && st[j] + nxt[j] + ((j + 1) * k <= m && a[(j + 1) * k] == 1) > st[j + 1]) pd = false;
if (j && nxt[j - 1] + st[j - 1] > nxt[j] + st[j]) pd = false;
if (j && nxt[j - 1] + st[j - 1] + k / 2 <= nxt[j] + st[j]) pd = false;
if (pd) H[opt].ins(nxt, o.val);
}
if (pos <= n && (pos > m || a[pos] == 1)) {
nxt = now; bool pd = true;
nxt[j]++;
if (j < mx && st[j] + nxt[j] + k - i - ((j + 1) * k <= m && a[(j + 1) * k] == 0) < st[j + 1]) pd = false;
if (j < mx && st[j] + nxt[j] + ((j + 1) * k <= m && a[(j + 1) * k] == 1) > st[j + 1]) pd = false;
if (j && nxt[j - 1] + st[j - 1] > nxt[j] + st[j]) pd = false;
if (j && nxt[j - 1] + st[j - 1] + k / 2 <= nxt[j] + st[j]) pd = false;
if (pd) H[opt].ins(nxt, o.val);
}
}
H[opt ^ 1].clear();
}
}
for (auto o : H[opt].q) {
now = o.id;
Add(ans, o.val);
}
}
void dfs(int t, int lst) {
if (t > mx) return work(), void();
for (int i = lst; i < lst + k / 2; ++i) {
st[t] = i;
dfs(t + 1, i);
}
}
void solve() {
mx = n / k;
dfs(1, 0);
for (int i = 1; i <= m; ++i) a[i] ^= 1;
dfs(1, 0);
printf("%d\n", ans);
}
}
namespace subtask3 {
struct node {
int x, y;
}p[10];
int st[10], a[10][10], ans, mx, fac[505], inv[505];
inline int qpow(int x, int y) {
int res = 1;
while (y) {
if (y & 1) res = 1ll * res * x % mod;
x = 1ll * x * x % mod;
y >>= 1;
}
return res;
}
inline int C(int x, int y) {return (x < 0 || y < 0 || x < y) ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod;}
void work() {
for (int i = 0; i < mx; ++i) {
p[i].x = st[i] - k / 2 * i;
p[i].y = st[i + 1] - k / 2 * i;
}
p[mx].x = st[mx] - k / 2 * mx;
p[mx].y = st[mx + 1] - k / 2 * mx;
for (int i = 0; i <= mx; ++i) {
for (int j = 0; j <= mx; ++j) {
if (j < mx) {
if (p[i].x > p[mx].y) a[i][j] = C(k, p[j].y - p[i].x);
else {
a[i][j] = 0;
for (int o = p[mx].y - p[i].x; o <= p[j].y - p[i].x; ++o) {
if (o > p[mx].y - p[i].x) Add(a[i][j], 1ll * C(n % k, o) * C(k - n % k, p[j].y - p[i].x - o) % mod);
else Add(a[i][j], 1ll * C(n % k, o) * C(k - n % k - 1, p[j].y - p[i].x - o - 1) % mod);
}
}
}
else a[i][j] = C(n % k, p[j].y - p[i].x);
}
}
int res = 1;
for (int i = 0; i <= mx; ++i) {
for (int j = i + 1; j <= mx; ++j) {
while (a[j][i]) {
swap(a[j], a[i]); res = mod - res;
int tmp = a[j][i] / a[i][i];
for (int o = i; o <= mx; ++o) Del(a[j][o], 1ll * tmp * a[i][o] % mod);
}
}
res = 1ll * res * a[i][i] % mod;
}
Add(ans, res);
}
void dfs(int t, int lst) {
if (t > mx + 1) return work(), void();
if (t > mx) {
for (int i = lst; i <= lst + n % k; ++i) {
st[t] = i;
dfs(t + 1, i);
}
return;
}
for (int i = lst; i < lst + k / 2; ++i) {
st[t] = i;
dfs(t + 1, i);
}
}
void solve() {
fac[0] = 1;
for (int i = 1; i <= 500; ++i) fac[i] = 1ll * fac[i - 1] * i % mod;
inv[500] = qpow(fac[500], mod - 2);
for (int i = 500; i >= 1; --i) inv[i - 1] = 1ll * inv[i] * i % mod;
mx = n / k;
dfs(1, 0); ans = add(ans, ans);
printf("%d\n", ans);
}
}
namespace subtask4 {
const int B = 100;
struct node {
int x, y;
}p[10];
int st[10], A[10][10], ans, mx, dp[1000][1000], vis[200][200];
bool check(int ox, int oy) {return ox < n % k || oy > p[mx].y || (ox == n % k && oy == p[mx].y);}
void work() {
// for (int i = 0; i <= mx; ++i) printf("%d ", st[i]); puts("");
int lst_x = 0, lst_y = 0;
for (int i = 1; i <= m; ++i) {
if (a[i] == 1) vis[lst_x][lst_y + B] = 1, lst_x++, lst_y++;
else vis[lst_x][lst_y + B] = -1, lst_x++;
if (lst_x == k) lst_x = 0, lst_y -= k / 2;
}
for (int i = 0; i < mx; ++i) {
p[i].x = st[i] - k / 2 * i;
p[i].y = st[i + 1] - k / 2 * i;
}
p[mx].x = st[mx] - k / 2 * mx;
p[mx].y = st[mx + 1] - k / 2 * mx;
// for (int i = 0; i <= mx; ++i) printf("(%d %d)->(%d %d)\n", 0, p[i].x, i < mx ? k : n % k, p[i].y);
for (int i = 0; i <= mx; ++i) {
dp[0][p[i].x + B] = 1;
for (int ox = 0; ox < k; ++ox)
for (int oy = p[i].x; oy <= p[0].y; ++oy) {
if (!dp[ox][oy + B]) continue;
if (vis[ox][oy + B] != 1 && check(ox, oy + 1)) Add(dp[ox + 1][oy + B], dp[ox][oy + B]);
if (vis[ox][oy + B] != -1 && check(ox + 1, oy + 1) && oy < p[0].y) Add(dp[ox + 1][oy + B + 1], dp[ox][oy + B]);
}
for (int j = 0; j < mx; ++j) A[i][j] = dp[k][p[j].y + B];
A[i][mx] = dp[n % k][p[mx].y + B];
for (int ox = 0; ox <= k; ++ox)
for (int oy = p[i].x; oy <= p[0].y; ++oy)
dp[ox][oy + B] = 0;
// for (int j = 0; j <= mx; ++j) printf("%d ", A[i][j]);
// puts("");
}
// return;
// puts("");
int res = 1;
for (int i = 0; i <= mx; ++i) {
for (int j = i + 1; j <= mx; ++j) {
while (A[j][i]) {
swap(A[j], A[i]); res = mod - res;
int tmp = A[j][i] / A[i][i];
for (int o = i; o <= mx; ++o) Del(A[j][o], 1ll * tmp * A[i][o] % mod);
}
}
res = 1ll * res * A[i][i] % mod;
}
Add(ans, res);
lst_x = 0, lst_y = 0;
for (int i = 1; i <= m; ++i) {
vis[lst_x][lst_y] = 0;
lst_x++; lst_y += a[i];
if (lst_x == k) lst_x = 0, lst_y -= k / 2;
}
}
void dfs(int t, int lst) {
if (t > mx + 1) return work(), void();
if (t > mx) {
for (int i = lst; i <= lst + n % k; ++i) {
st[t] = i;
dfs(t + 1, i);
}
return;
}
for (int i = lst; i < lst + k / 2; ++i) {
st[t] = i;
dfs(t + 1, i);
}
}
void solve() {
mx = n / k;
dfs(1, 0);
for (int i = 1; i <= m; ++i) a[i] ^= 1;
dfs(1, 0);
printf("%d\n", ans);
}
}
int main() {
scanf("%d%d%d%s", &n, &k, &m, s + 1);
// double st = clock();
for (int i = 1; i <= m; ++i) a[i] = s[i] - '0';
// subtask4 :: solve(); return 0;
if (k <= 22) subtask1 :: solve();
else if (n <= 66) subtask2 :: solve();
else if (m == 0) subtask3 :: solve();
else subtask4 :: solve();
// double ed = clock();
// printf("%.10lf\n", (ed - st) / CLOCKS_PER_SEC);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 7868kb
input:
2 2 0
output:
0
result:
wrong answer 1st numbers differ - expected: '2', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Wrong Answer
Test #137:
score: 0
Wrong Answer
time: 78ms
memory: 20096kb
input:
114 20 0
output:
0
result:
wrong answer 1st numbers differ - expected: '849724285', found: '0'
Subtask #5:
score: 0
Skipped
Dependency #2:
0%