QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#296100#4893. Imbalancezyc0704190 78ms20096kbC++149.0kb2024-01-02 09:08:392024-01-02 09:08:39

Judging History

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

  • [2024-01-02 09:08:39]
  • 评测
  • 测评结果：0
  • 用时：78ms
  • 内存：20096kb
查看
  • [2024-01-02 09:08:39]
  • 提交

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;
}
源文件, 语言: C++14

详细

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%
English 繁體中文 简体中文

服务器时间: 2024-12-12 00:16:06 | 开源项目