Preface

考完HNOI,忽然听说要给HA出题,于是临时东拼西凑出了几个idea.有个idea也是在别的地方看到的(T2的一个核心结论),T1的模型似乎比较经典,而T3的算法其实并不优美,主要是缺一道工业题所以yy出一个奇怪的字符串匹配.

T1出了点锅,题目描述里有点问题,std数组开小了导致最后两个点数据有问题(竟然不RE),不过还好没有对现场选手造成太大影响.

另外,如果你不知道小C和小G是谁,这里是一些科普:

小C是一位擅长数据结构的dalao,擅长将若干个数据结构题拼在一起,或者把树上问题放在环套树上做.

小G是一位擅长各类思维题的神秘选手,擅长各类博弈问题,但他从不与别人搏弈.

奇怪的背包 (knapsack)

Description

小C非常擅长背包问题,他有一个奇怪的背包,这个背包有一个参数$P$,当他向这个背包内放入若干个物品后,背包的重量是物品总体积对$P$取模后的结果.

现在小C有$n$种体积不同的物品,第$i$种占用体积为$V_i$,每种物品都有无限个.他会进行$q$次询问,每次询问给出重量$w_i$,你需要回答有多少种放入物品的方案,能将一个初始为空的背包的重量变为$w_i$.注意,两种方案被认为是不同的,当且仅当放入物品的种类不同,而与每种物品放入的个数无关.不难发现总的方案数为$2^n$.

由于答案可能很大,你只需要输出答案对$10^9 + 7$取模的结果.

对于所有数据,有$1 \le n, q \le 10^6, 3 \le P \le 10^9, 0 < V_i, w_i < P$.

Analysis

题目就是求,有多少种选择物品的方式,使得下面的同余方程有解,(假设选择的物品的体积为$a_1, a_2, …, a_k$):

根据不定方程的知识(还记得拓展欧几里得吗),我们知道这个方程有解当且仅当 $gcd(a_1, a_2, …, a_k, P) \mid w_j$.

于是我们就可以DP了,设$dp(i, x)$表示前$i$种物品,我们选择的物品的体积的$gcd$再和$P$做$gcd$的结果为$x$,选择的方案数是多少.

转移只需要考虑是否选这个数,这样做的复杂度是$O(n \times d(P))$的,其中$d(P)$表示$P$的约数个数.由于约数个数大约是$P^{\frac{1}{3}}$的级别(此题中不超过$1500$),可以拿到$80$分.

优化也很简单,对于两个物品,如果他们的体积与$P$的$gcd$是相同的,那么他们造成的影响也是相同的,可以放到一起算.相当于物品种类数其实也是$d(P)$的,于是复杂度变为$O((d^2(P) + n + q) \log P)$,$\log$是取$gcd$的复杂度.

Source

#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 2e3 + 10;
const int Mod = 1e9 + 7;

int gcd(int x, int y) {
	return !y ? x : gcd(y, x % y);
}

int cnt[N], d[N], dp[N][N];
int pow2[1000100], ans[N];
int n, q, P, m;

int getpos(int x) {
	return lower_bound(d + 1, d + m + 1, x) - d;
}

int main() {

	scanf("%d%d%d", &n, &q, &P);

	for (int i = 1; i * i <= P; ++i)
		if (P % i == 0) {
			d[++m] = i;
			if (i * i != P) d[++m] = P / i;
		}

	sort(d + 1, d + m + 1);
	For(i, 1, n) {
		int x;
		scanf("%d", &x);
		cnt[getpos(gcd(x, P))]++;
	}

	pow2[0] = 1;
	For(i, 1, n) pow2[i] = pow2[i - 1] * 2 % Mod;

	dp[0][m] = 1;
	For(i, 1, m) For(j, 1, m) {
		int x = getpos(gcd(d[j], d[i]));
		dp[i][x] = (dp[i][x] + 1ll * dp[i - 1][j] * (pow2[cnt[i]] - 1)) % Mod;
		dp[i][j] = (dp[i][j] + dp[i - 1][j]) % Mod;
	}

	For(i, 1, m) For(j, 1, i) if (d[i] % d[j] == 0)
		(ans[i] += dp[m][j]) %= Mod;

	For(i, 1, q) {
		int x;
		scanf("%d", &x);
		printf("%d\n", ans[getpos(gcd(x, P))]);
	}
	
	return 0;
}

反色游戏 (game)

Description

小C和小G经常在一起研究博弈论问题,有一天他们想到了这样一个游戏.

有一个$n$个点$m$条边的无向图,初始时每个节点有一个颜色,要么是黑色,要么是白色.现在他们对于每条边做出一次抉择:要么将这条边连接的两个节点都反色(黑变白,白变黑),要么不作处理.他们想把所有节点都变为白色,他们想知道在$2^m$种决策中,有多少种方案能达成这个目标.

小G认为这个问题太水了,于是他还想知道,对于第$i$个点,在删去这个点及与它相连的边后,新的答案是多少.

由于答案可能很大,你只需要输出答案对$10^9 + 7$取模后的结果.

对于所有数据,有$1 \le T \le 5, 1 \le n, m \le 10^5, 1 \le u, v \le n$,没有重边和自环.

Analysis

感觉很有趣的一个题.

首先我们不管删点操作,思考一下什么时候是无解的.一个显然的必要条件是,一个连通块内必须要有偶数个黑点,而这个条件也是充分的.为什么呢?我们将黑点任意两两配对,对一对黑点考虑它们之间的任意一条路径,将路径上的边的状态(操作or不操作)取反,立即可以得到一种合法方案.

同时我们发现,对于任意一种偶数个黑点的方案,如果进行上面的配对,都可以唯一对应到一种全为白色的方案.也就是说,只要有解,解的个数都是相同的.对于一个连通块,假设边数为$m$,点数为$n$,有$2^{n - 1}$种对点染色的方案是有解的且解的个数相同,总方案数为$2^m$,那么对于一个有解的局面这个连通块的方案数就是$2^{m - n + 1}$! 对于整张图,总的方案数就是$2^{m - n + p}$,其中$p$是连通块个数.

上面的推导比较简洁,但思路看起来不是很自然,其实还有一种更科学的理解.

这道题的部分分可以用高斯消元解决,将$m$条边的决策看成$m$个变量,对于$n$个点不难各列出一个异或方程($adj(i)$表示与$i$相邻的边的集合):

我们需要求矩阵的秩(也就是m - 自由元),若有解答案就是$2^{\text{自由元}}$.分析矩阵中出现若干个行向量(也就上面的若干个方程)线性相关的情况,如果若干个行向量的异或为$0$,这说明不存在一条边连接这些向量对应的点与其他点,也就是这些点构成了完整的一个或多个连通块.对于一个连通块的行向量,我们能选出的极大线性无关组的大小为$n - 1$,那么整个矩阵的秩就是$n - p$,方案数就是$2^{m - n + p}$.

考虑删点操作,剩下的部分是很简单的,我们只需要知道删掉一个点后连通块数量的变化,以及是否新产生的连通块是否有解.做一遍Tarjan求割点的算法就可以求出.$O(n + m)$

Source

#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)

using namespace std;

const int N = 1e5 + 10;
const int Mod = 1e9 + 7;

int Begin[N], Next[N << 1], to[N << 1], e = 1;
int deg[N];

void add(int u, int v) {
	to[++e] = v, Next[e] = Begin[u], Begin[u] = e;
}

int low[N], dfn[N], clk;
int cut[N], sz[N], flag[N], bel[N], sub[N], now;
char S[N];

void Tarjan(int o, int fa = 0) {
	low[o] = dfn[o] = ++clk;
	flag[o] = true, sz[o] = S[o] == '1';
	bel[o] = now;
	for (int i = Begin[o]; i; i = Next[i]) {
		int u = to[i];
		if (!dfn[u]) {
			Tarjan(u, o);
			sz[o] += sz[u];
			if (low[u] >= dfn[o]) {
				++cut[o], flag[o] &= sz[u] % 2 == 0;
				sub[o] += sz[u];
			} else {
				low[o] = min(low[o], low[u]);
			}
		} else if (u != fa) {
			low[o] = min(low[o], dfn[u]);
		}
	}
	if (!fa) --cut[o];
}

int n, m;
int pow2[N];

int main() {

	pow2[0] = 1;
	For(i, 1, 100000) pow2[i] = pow2[i - 1] * 2 % Mod;

	int Case;
	scanf("%d", &Case);

	while (Case--) {
		
		scanf("%d%d", &n, &m);
		e = 1, clk = 0;
		For(i, 1, n) Begin[i] = dfn[i] = sz[i] = deg[i] = sub[i] = cut[i] = 0;
		For(i, 1, m) {
			int u, v;
			scanf("%d%d", &u, &v);
			add(u, v), add(v, u);
			++deg[u], ++deg[v];
		}
		scanf("%s", S + 1);		
		
		int cnt = 0, cnt_odd = 0;
		For(i, 1, n) if (!dfn[i]) {
			now = i;
			Tarjan(i), ++cnt;
			cnt_odd += sz[i] & 1;
		}
		
		int ans = m - n + cnt;
		printf("%d", cnt_odd ? 0 : pow2[ans]);
		For(i, 1, n) {
			if (!deg[i]) printf(" %d", cnt_odd - sz[i] == 0 ? pow2[ans] : 0);
			else {
				if (flag[i] && (sz[bel[i]] - (S[i] == '1') - sub[i]) % 2 == 0 
						&& cnt_odd - (sz[bel[i]] & 1) == 0)
					printf(" %d", pow2[ans - deg[i] + 1 + cut[i]]);
				else printf(" 0");
			}
		}
		puts("");

	}

	return 0;
}

字串覆盖 (cover)

Description

小C对字符串颇有研究,他觉得传统的字符串匹配太无聊了,于是他想到了这样一个问题.

对于两个长度为$n$的串$A, B$, 小C每次会给出给出$4$个参数$s, t, l, r$. 令$A$从$s$到$t$的子串(从$1$开始标号)为$T$,令$B$从$l$到$r$的子串为$P$.然后他会进行下面的操作:

如果$T$的某个子串与$P$相同,我们就可以删掉$T$的这个子串,并获得$K - i$的收益,其中$i$是初始时$A$中(注意不是$T$中)这个子串的起始位置,$K$是给定的参数.删除操作可以进行任意多次,你需要输出获得收益的最大值.

注意每次询问都是独立的,即进行一次询问后,删掉的位置会复原.

对于所有数据,有$1 \le n, q \le 10^5$,$A, B$仅由小写英文字母组成,$1 \le s \le t \le n, 1 \le l \le r \le n, n < K \le 10^9$.

对于$n = 10^5$的测试点,满足$51 \le r - l \le 2000$的询问不超过$11000$个,且$r - l$在该区间内均匀随机.

Analysis

部分分中有特别明显的提示:讨论询问串长度.

如果询问串长度很长,那么答案一定很小,我们只需要贪心地找靠前的匹配位置即可,找到一个后改变询问区间使得找到的串不重叠.找的方法可以用经典的后缀数组-主席树套路,即将两个串拼起来做后缀数组,后缀数组上二分出与询问串匹配的区间,问题就变成区间内找大于给定值的最小的数,利用线段树的二分结构即可做到单次$\log$.

如果很短的话考虑对每一种串都预处理,利用后缀数组快速找到每一种串出现的所有位置,将位置排序之后可以快速找到一个出现位置之后第一次不重叠的再次出现的位置,这构成了一个森林结构,树上倍增记录信息即可解决.空间不太好开,可以将询问离线.

$O(n \sqrt{n} \log n)$,为了让正解显著快于暴力,数据范围中有一个对询问长度的特殊约束,所以只要对长度不超过$50$的串预处理即可.

Source

#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; i++)
#define Forr(i, j, k) for (int i = j; i >= k; i--)

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;
const int LIM = 50;

struct Persistent_Segment_Tree {

	const static int NODE = N * 20;

	int lc[NODE], rc[NODE], sz[NODE], node;

	#define M ((L + R) >> 1)

	void insert(int &o, int ro, int L, int R, int x) {
		o = ++node;
		sz[o] = sz[ro] + 1, lc[o] = lc[ro], rc[o] = rc[ro];
		if (L < R) {
			if (x <= M) insert(lc[o], lc[ro], L, M, x);
			else insert(rc[o], rc[ro], M + 1, R, x);
		}
	}

	int getnxt(int lo, int ro, int L, int R, int x) {
		if (sz[ro] - sz[lo] == 0) return 0; 
		if (L == R) return L;
		if (x <= M) {
			int ret = getnxt(lc[lo], lc[ro], L, M, x);
			if (ret) return ret;
		}
		return getnxt(rc[lo], rc[ro], M + 1, R, x);
	}

}T;

int buffer[N * 10];
int sa[N];
char S[N];
int n;

void buildsa(int m) {
	int *x = buffer, *y = x + (N << 1), *c = y + (N << 1);
	For(i, 1, m) c[i] = 0;
	For(i, 1, n) c[x[i] = S[i]]++;
	For(i, 1, m) c[i] += c[i - 1];
	For(i, 1, n) sa[c[x[i]]--] = i;
	for (int k = 1; k <= n; k <<= 1) {
		int p = 0;
		For(i, n - k + 1, n) y[++p] = i;
		For(i, 1, n) if (sa[i] > k) y[++p] = sa[i] - k;
		For(i, 1, m) c[i] = 0;
		For(i, 1, n) c[x[y[i]]]++;
		For(i, 1, m) c[i] += c[i - 1];
		Forr(i, n, 1) sa[c[x[y[i]]]--] = y[i];
		swap(x, y);
		x[sa[1]] = p = 1;
		For(i, 2, n) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p;
		if (p == n) break;
		m = p;
	}
}

int rk[N], Min[N][18];

void buildheight() {
	int p = 0;
	For(i, 1, n) rk[sa[i]] = i;
	For(i, 1, n) {
		if (p) --p;
		int j = sa[rk[i] + 1];
		if (!j) continue;
		while (S[i + p] == S[j + p]) ++p;
		Min[rk[i]][0] = p;
	}
	For(j, 1, 16)
		for (int i = 1; i + (1 << j) <= n; ++i)
			Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
}

int Log2[N], K;
LL ans[N];

struct Query {
	int s, t, l, len, id, pos;

	bool operator < (const Query& A) const {
		return len == A.len ? pos < A.pos : len < A.len;
	}
}Q[N];

int fa[N][18];
LL sum[N][18];

void work(int len, int& it) {
	static int pos[N];
	For(l, 1, n * 2 + 1) {
		int r = l, c = 0;
		while (Min[r][0] >= len) ++r;
		For(j, l, r) if (sa[j] <= n) pos[++c] = sa[j];

		if (Q[it].len != len || Q[it].pos < l || Q[it].pos > r) { l = r; continue; }

		sort(pos + 1, pos + c + 1);
		int lim = Log2[min(c + 1, n / len)], k = 1;
		pos[c + 1] = 2 * n + 1;

		For(i, 1, c + 1) For(j, 0, lim) fa[i][j] = sum[i][j] = 0;

		For(j, 1, c) {
			while (pos[k] - pos[j] < len) ++k;
			fa[j][0] = k, sum[j][0] = K - pos[j];
		}
		For(y, 1, lim) for (int j = 1; j + (1 << y) - 1 <= c; ++j)
			fa[j][y] = fa[fa[j][y - 1]][y - 1],
			sum[j][y] = sum[j][y - 1] + sum[fa[j][y - 1]][y - 1];

		while (Q[it].len == len && Q[it].pos <= r) {
			int L = Q[it].s, R = Q[it].t;
			int x = lower_bound(pos + 1, pos + c + 2, L) - pos;

			if (pos[x] > R) ans[Q[it].id] = 0;
			else {
				int o = x;
				LL ret = 0;
				Forr(j, lim, 0) if (pos[fa[o][j]] && pos[fa[o][j]] <= R) 
					ret += sum[o][j], o = fa[o][j];
				ans[Q[it].id] = ret + sum[o][0];
			}

			++it;
		}

		l = r;
	}
}

int root[N];

int main() {

	scanf("%d%d", &n, &K);
	For(i, 2, n) Log2[i] = Log2[i >> 1] + 1;
	scanf("%s", S + 1);
	S[n + 1] = '#';
	scanf("%s", S + n + 2);

	n = n * 2 + 1;
	buildsa('z');
	buildheight();
	n /= 2;

	int q;
	scanf("%d", &q);
	For(i, 1, q) {
		scanf("%d%d%d%d", &Q[i].s, &Q[i].t, &Q[i].l, &Q[i].len);
		Q[i].len -= Q[i].l - 1, Q[i].id = i, Q[i].pos = rk[Q[i].l + n + 1];
		Q[i].t -= Q[i].len - 1;
	}
	sort(Q + 1, Q + q + 1);

	int it = 1;
	For(i, 1, min(n, LIM)) work(i, it);

	For(i, 1, 2 * n + 1) {
		root[i] = root[i - 1];
		if (sa[i] <= n) T.insert(root[i], root[i], 1, n, sa[i]);
	}

	while (it <= q) {

		Query A = Q[it];
		int x = A.pos, L = x, R = x;
		Forr(i, 16, 0) if (L - (1 << i) > 0 && Min[L - (1 << i)][i] >= A.len) L -= 1 << i;
		Forr(i, 16, 0) if (R + (1 << i) <= 2 * n + 1 && Min[R][i] >= A.len) R += 1 << i;

		int pos = A.s;
		while (pos <= n) {
			int s = T.getnxt(root[L - 1], root[R], 1, n, pos);
			if (!s || s > A.t) break;
			ans[A.id] += K - s, pos = s + A.len;
		}
		++it;
	}
		
	For(i, 1, q) printf("%lld\n", ans[i]);

	return 0;
}