# A. 数正方体

推了 2.5h 没有推出来，心态非常崩。

主要是没有网通项式方面去想，考场上推出来递推式之后一直在优化递推……

~~通过手模不难发现~~， $f_{i, j} = f_{i - 1, j - 1} + 2 \times f_{i - 1, j}$ .

然后再打一个更大的表，不难发现

$f_{n, m} = 2^{n - m} \dbinom {n}{m}$

然后 $O(n)$ 预处理， $O(1)$ 查询就好了。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	const int M = 1e4 + 10;
	const int mod = 998244353;
	int T, n, m;

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	int fac[N], ifac[N];

	inline int qpow(int a, int b){
	int res = 1;
	while(b){
	if(b & 1) res = mul(res, a);
	a = mul(a, a), b >>= 1;
	}
	return res;
	}

	inline void init(int n){
	fac[0] = 1;
	for(int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	ifac[n] = qpow(fac[n], mod - 2);
	for(int i = n - 1; i >= 0; --i) ifac[i] = mul(ifac[i + 1], i + 1);
	}

	inline int C(int n, int m){
	return mul(fac[n], mul(ifac[m], ifac[n - m]));
	}

	inline void solve(){
	n = read(), m = read();
	write(mul(C(n, m), qpow(2, n - m))), puts("");
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	T = read(), init(N - 10);
	while(T--) solve();
	return 0;
	}

# B. 数连通块

首先把题目中的树跑出来，设 $p_i$ 表示 $i$ 点存在的概率， $q_i$ 表示 $i$ 点不存在的概率。

对于询问 $l \sim r$ ，考虑每个点对连通块个数的贡献。

设当前点为 $x$ ，分类讨论：

$fa_x$ 在 $l \sim r$ 中， $x$ 想要对答案有贡献，那么必须 $fa_x$ 不存在，且 $x$ 存在，所以贡献为 $q[fa_x] \times p[x]$ 。
$fa_x$ 不在 $l \sim r$ 中，只要 $x$ 存在就对答案就贡献，所以贡献为 $p[x]$ 。

暴力是 $O(n^2)$ 的，期望得分 $\text{10pts}$ ，考虑使用莫队优化，然后就可以过了……

	#include <bits/stdc++.h>
	#define pb push_back
	#define be(x) x / B

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e5 + 10;
	const int mod = 1e9 + 7;
	int n, m, Q, B;
	int p[N], q[N];
	vector <int> g[N];

	inline int add(int x, int y) {return x + y >= mod ? x + y - mod : x + y;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	inline int qpow(int a, int b){
	int res = 1;
	while(b){
	if(b & 1) res = mul(res, a);
	a = mul(a, a), b >>= 1;
	}
	return res;
	}

	inline int inv(int a) {return qpow(a, mod - 2);}

	int fa[N];

	inline void dfs(int x, int f){
	fa[x] = f;
	for(auto y : g[x]) if(y != f) dfs(y, x);
	}

	struct node{
	int l, r, id;
	inline bool operator < (const node &b) const{
	return be(l) != be(b.l) ? l < b.l : r < b.r;
	}
	}a[N];
	int ans[N], s[N];
	int l, r, res;

	inline void add(int x){
	if(fa[x] >= l && fa[x] <= r) res = add(res, mul(p[x], q[fa[x]]));
	else res = add(res, p[x]);
	s[fa[x]] = add(s[fa[x]], p[x]), res = add(sub(res - s[x]), mul(s[x], q[x]));
	}

	inline void del(int x){
	if(fa[x] >= l && fa[x] <= r) res = sub(res - mul(p[x], q[fa[x]]));
	else res = sub(res - p[x]);
	s[fa[x]] = sub(s[fa[x]] - p[x]), res = add(sub(res - mul(s[x], q[x])), s[x]);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), m = read(), Q = read(), B = sqrt(n);
	for(int i = 1, a, b; i <= n; ++i)
	a = read(), b = read(), p[i] = mul(a, inv(b)), q[i] = sub(1 - p[i]);
	for(int i = 1; i <= m; ++i){
	int u = read(), v = read();
	g[u].pb(v), g[v].pb(u);
	}
	dfs(1, 0);
	for(int i = 1; i <= Q; ++i) a[i] = (node){read(), read(), i};
	sort(a + 1, a + 1 + Q);
	l = 1, r = 0;
	for(int i = 1; i <= Q; ++i){
	while(l > a[i].l) add(--l);
	while(r < a[i].r) add(++r);
	while(l < a[i].l) del(l++);
	while(r > a[i].r) del(r--);
	ans[a[i].id] = res;
	}
	for(int i = 1; i <= Q; ++i) write(ans[i]), puts("");
	return 0;
	}

# C. 数大模拟

拿了暴力分跑路了 /kk

正解现在还不会，先咕了。

# D. 数字符串

暴力 $\text{Hash}$ 没什么好说的了，可以得 $\text{50pts}$ 。

观察题目条件 $2x \equiv i\ (\bmod k)$ ，我们开个桶记录合法的 $2x$ 个数就好， $f_i$ 就可以直接算出来了。

考虑在失配树上跑，开个栈记录一条从上到下的链。因为是失配树，所以父亲是儿子的 $\text{border}$ ，也就是满足条件②。

对于条件③，记录 $p_x$ 表示 $x$ 到祖先的链上最远的合法的位置，具体怎么维护看代码吧。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	const int mod = 998244353;
	char s[N];
	int n, k, ans = 1;
	int nxt[N];
	vector <int> g[N];
	int stk[N], top, buk[N], p[N], f[N];

	inline void dfs(int x, int fa){
	if(x) stk[++top] = x, buk[2 * x % k]++;
	p[x] = p[fa];
	while(p[x] < top && 2 * stk[p[x] + 1] < x + 1) p[x]++, buk[2 * stk[p[x]] % k]--;
	f[x] = buk[x % k];
	for(auto y : g[x]) dfs(y, x);
	while(p[x] > p[fa]) buk[2 * stk[p[x]] % k]++, p[x]--;
	if(x) top--, buk[2 * x % k]--;
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	scanf("%s", s + 1), k = read();
	n = strlen(s + 1);
	for(int i = 2, j = 0; i <= n; ++i){
	while(j && s[i] != s[j + 1]) j = nxt[j];
	if(s[i] == s[j + 1]) j++;
	nxt[i] = j;
	}
	for(int i = 1; i <= n; ++i) g[nxt[i]].pb(i);
	dfs(0, 0);
	for(int i = 1; i <= n; ++i) ans = 1ll * ans * (f[i] + 1) % mod;
	write(ans), puts("");
	return 0;
	}

# A. 数正方体

# B. 数连通块

# C. 数大模拟

# D. 数字符串

20220708

二维数点问题