欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

【集训队作业】IOI 2020 集训队作业 试题泛做 10

程序员文章站 2022-06-08 12:58:04
...

Codeforces 576D Flights for Regular Customers

考虑由一个时刻 ii 可达的点集 SiS_i 计算时刻 i+1i+1 可达的点集 Si+1S_{i+1} ，这可以由每个时刻可用的边集计算，其本质是一次矩阵乘法。

因此，使用快速幂和 bitset 优化之，可以得到一个时间复杂度 O(MLogV×N3w)O(MLogV\times \frac{N^3}{w}) 的做法，以下代码实现的是该做法。

事实上，这个算法可以被继续优化，考虑在加入一条边的时候维护转移矩阵的 20,21,22,…2^0,2^1,2^2,\dots 次方，则矩阵乘法复杂度较大的部分就可以通过矩阵乘向量优化了。

加入一条边只会使得矩阵中的一些元素从 0 变为 1 ，由此可以得到一个均摊复杂度 O(N3w×LogV)O(\frac{N^3}{w}\times LogV) 的做法。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 155;
const int INF  = 2e9;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
struct vec {bitset <MAXN> a; };
struct mat {bitset <MAXN> r[MAXN], c[MAXN]; };
int n, m;
vec Veccipher() {
	vec ans; ans.a.reset();
	return ans;
}
mat Matcipher() {
	mat ans;
	for (int i = 1; i <= n; i++) {
		ans.r[i].reset();
		ans.c[i].reset();
	}
	ans.r[n].set(n);
	ans.c[n].set(n);
	return ans;
}
mat unit() {
	mat ans;
	for (int i = 1; i <= n; i++) {
		ans.r[i].reset();
		ans.c[i].reset();
		ans.r[i].set(i);
		ans.c[i].set(i);
	}
	return ans;
}
vec operator * (vec a, mat b) {
	vec ans;
	for (int i = 1; i <= n; i++)
		if ((a.a & b.c[i]).count() != 0) ans.a[i] = true;
		else ans.a[i] = false;
	return ans;
}
mat operator * (mat a, mat b) {
	mat ans;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++) {
		if ((a.r[i] & b.c[j]).count() != 0) ans.r[i][j] = ans.c[j][i] = true;
		else ans.r[i][j] = ans.c[j][i] = false;
	}
	return ans;
}
mat power(mat x, int y) {
	if (y == 0) return unit();
	mat tmp = power(x, y / 2);
	if (y % 2 == 0) return tmp * tmp;
	else return tmp * tmp * x;
}
pair <pair <int, int>, int> e[MAXN];
bool cmp(pair <pair <int, int>, int> x, pair <pair <int, int>, int> y) {
	return x.second < y.second;
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		read(e[i].first.first);
		read(e[i].first.second);
		read(e[i].second);
	}
	sort(e + 1, e + m + 1, cmp);
	e[m + 1] = make_pair(make_pair(1, 1), INF);
	vec now = Veccipher(); now.a[1] = true;
	mat tmp = Matcipher();
	for (int i = 1; i <= m + 1; i++) {
		int cnt = e[i].second - e[i - 1].second;
		vec tnp = now * power(tmp, cnt);
		if (tnp.a[n]) {
			int ans = e[i - 1].second;
			while (now.a[n] == 0) {
				ans++;
				now = now * tmp;
			}
			cout << ans << endl;
			return 0;
		}
		int x = e[i].first.first, y = e[i].first.second;
		tmp.r[x][y] = tmp.c[y][x] = true; now = tnp;
	}
	puts("Impossible");
	return 0;
}

Codeforces 576E Painting Edges

离线操作，考虑用并查集维护连通性。

由于并查集不便删边，考虑用线段树分治解题，这样便只需要支持回退，可以通过按秩合并做到。

在分治结构上 DFS ，每在叶子节点处判断能否加边，并确定该边直到下一次修改的颜色，对对应的时间区间进行修改即可。

时间复杂度 O(QLogQLogN)O(QLogQLogN) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
const int MAXP = 5e7 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int x[MAXN], y[MAXN], last[MAXN];
int e[MAXN], c[MAXN], nxt[MAXN];
int n, m, q, k, f[MAXP], s[MAXP];
struct Node {
	int lc, rc;
	vector <int> mod;
} a[MAXN * 2]; int root, size;
int find(int x) {
	if (f[x] == x) return x;
	else return find(f[x]);
}
inline int point(int x, bool side, int k) {
	return (k - 1) * n * 2 + side * n + x;
}
void modify(int root, int l, int r, int ql, int qr, int d) {
	if (l == ql && r == qr) {
		a[root].mod.push_back(d);
		return;
	}
	int mid = (l + r) / 2;
	if (mid >= ql) modify(a[root].lc, l, mid, ql, min(mid, qr), d);
	if (mid + 1 <= qr) modify(a[root].rc, mid + 1, r, max(mid + 1, ql), qr, d);
}
void work(int root, int l, int r) {
	vector <pair <int, pair <int, int>>> bak;
	for (auto t : a[root].mod) {
		int tx = find(point(x[e[t]], 0, c[t])), ty = find(point(y[e[t]], 1, c[t]));
		if (tx != ty) {
			if (s[tx] > s[ty]) swap(tx, ty);
			bak.emplace_back(tx, make_pair(f[tx], s[tx]));
			bak.emplace_back(ty, make_pair(f[ty], s[ty]));
			f[tx] = ty, s[ty] += s[tx];
		}
		tx = find(point(x[e[t]], 1, c[t])), ty = find(point(y[e[t]], 0, c[t]));
		if (tx != ty) {
			if (s[tx] > s[ty]) swap(tx, ty);
			bak.emplace_back(tx, make_pair(f[tx], s[tx]));
			bak.emplace_back(ty, make_pair(f[ty], s[ty]));
			f[tx] = ty, s[ty] += s[tx];
		}
	}
	if (l == r) {
		if (find(point(x[e[l]], 0, c[l])) == find(point(y[e[l]], 0, c[l]))) {
			puts("NO");
			if (last[e[l]] && l != q) modify(1, 1, q, l + 1, nxt[l], last[e[l]]);
		} else {
			puts("YES");
			last[e[l]] = l;
			if (l != q) modify(1, 1, q, l + 1, nxt[l], last[e[l]]);
		}
	} else {
		int mid = (l + r) / 2;
		work(a[root].lc, l, mid);
		work(a[root].rc, mid + 1, r);
	}
	reverse(bak.begin(), bak.end());
	for (auto x : bak) {
		f[x.first] = x.second.first;
		s[x.first] = x.second.second;
	}
}
void build(int &root, int l, int r) {
	root = ++size;
	if (l == r) return;
	int mid = (l + r) / 2;
	build(a[root].lc, l, mid);
	build(a[root].rc, mid + 1, r);
}
int main() {
	read(n), read(m), read(k), read(q);
	for (int i = 1; i <= m; i++)
		read(x[i]), read(y[i]);
	for (int i = 1; i <= q; i++) {
		read(e[i]), read(c[i]);
		if (last[e[i]] != 0) nxt[last[e[i]]] = i;
		last[e[i]] = i;
	}
	for (int i = 1; i <= q; i++)
		if (nxt[i] == 0) nxt[i] = q;
	for (int i = 1; i <= 2 * n * k; i++)
		f[i] = i, s[i] = 1;
	memset(last, 0, sizeof(last));
	build(root, 1, q);
	work(root, 1, q);
	return 0;
}

Codeforces 578E Walking!

显然，最终的交替序列应当是若干个交替子序列前后拼接而成的。

因此，答案显然有下界，令贪心匹配各个位置，最小化交替子序列的个数为 SS ，则答案有下界 S−1S-1 。

并且，按照一定的顺序匹配，我们可以保证取到这个下界，因此，简单贪心即可，具体策略可见代码。

时间复杂度 O(∣S∣)O(|S|) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
char s[MAXN]; int n, nxt[MAXN];
vector <pair <int, int>> rr, rl, lr, ll;
int main() {
	scanf("%s", s + 1), n = strlen(s + 1);
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		pair <int, int> tmp;
		if (s[i] == 'L') {
			if (lr.size()) {
				tmp = lr.back(), lr.pop_back();
				nxt[tmp.second] = i, tmp.second = i;
				ll.push_back(tmp);
			} else if (rr.size()) {
				tmp = rr.back(), rr.pop_back();
				nxt[tmp.second] = i, tmp.second = i;
				rl.push_back(tmp);
			} else ll.emplace_back(i, i);
		} else {
			if (rl.size()) {
				tmp = rl.back(), rl.pop_back();
				nxt[tmp.second] = i, tmp.second = i;
				rr.push_back(tmp);
			} else if (ll.size()) {
				tmp = ll.back(), ll.pop_back();
				nxt[tmp.second] = i, tmp.second = i;
				lr.push_back(tmp);
			} else rr.emplace_back(i, i);
		}
	}
	while (lr.size() >= 2) {
		ans++;
		pair <int, int> tmp = lr.back(); lr.pop_back();
		pair <int, int> tnp = lr.back(); lr.pop_back();
		nxt[tmp.second] = tnp.first, tmp.second = tnp.second;
		lr.push_back(tmp);
	}
	while (rl.size() >= 2) {
		ans++;
		pair <int, int> tmp = rl.back(); rl.pop_back();
		pair <int, int> tnp = rl.back(); rl.pop_back();
		nxt[tmp.second] = tnp.first, tmp.second = tnp.second;
		rl.push_back(tmp);
	}
	while (ll.size() + lr.size() + rr.size() + rl.size() >= 2) {
		ans++;
		if (lr.size()) {
			pair <int, int> tmp = lr.back(), tnp; lr.pop_back();
			if (ll.size()) {
				tnp = ll.back(); ll.pop_back();
				nxt[tmp.second] = tnp.first, tmp.second = tnp.second;
				ll.push_back(tmp);
			} else {
				tnp = rr.back(); rr.pop_back();
				nxt[tnp.second] = tmp.first, tmp.first = tnp.first;
				rr.push_back(tmp);
			}
		} else if (rl.size()) {
			pair <int, int> tmp = rl.back(), tnp; rl.pop_back();
			if (ll.size()) {
				tnp = ll.back(); ll.pop_back();
				nxt[tnp.second] = tmp.first, tmp.first = tnp.first;
				ll.push_back(tmp);
			} else {
				tnp = rr.back(); rr.pop_back();
				nxt[tmp.second] = tnp.first, tmp.second = tnp.second;
				rr.push_back(tmp);
			}
		} else {
			pair <int, int> tmp = ll.back(); ll.pop_back();
			pair <int, int> tnp = rr.back(); rr.pop_back();
			nxt[tmp.second] = tnp.first, tmp.second = tnp.second;
			lr.push_back(tmp);
		}
	}
	cout << ans << endl;
	int pos = 0;
	if (ll.size()) pos = ll.back().first;
	if (lr.size()) pos = lr.back().first;
	if (rl.size()) pos = rl.back().first;
	if (rr.size()) pos = rr.back().first;
	while (pos != 0) {
		printf("%d ", pos);
		pos = nxt[pos];
	}
	return 0;
}

Codeforces 578F Mirror Box

题目要求从某处射入的光线要从相邻的地方射出，那么，若增设一些镜子，将这些光线首尾相连，则可以得到一个环，如下图所示：

【集训队作业】IOI 2020 集训队作业 试题泛做 10

在放入镜子后，这个环应当经过所有的边的中点，因而也是唯一的。

这个环将所有的镜子分为了环内外两个部分，不难发现，这两部分都是连通且无环的。

进而，我们可以证明，一个放置方案合法，当且仅当增设一些镜子后，镜子形成了两棵树。

可以发现，若将交叉点黑白染色，一个镜子只会连接同色的两个点，因此，同色的点必须完全连通。

注意到若同一种颜色的点构成一棵树，另一种颜色的点在增设一些镜子后一定也构成一棵树，因此，只需要用矩阵树定理计算某种颜色的点的生成树的个数，然后相加即可。

时间复杂度 O(N×M+Cnt3)O(N\times M+Cnt^3) ，其中 CntCnt 表示不确定的位置个数。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 405;
const int MAXM = 1e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, m, tot, P, a[MAXN][MAXN];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
char s[MAXN][MAXN];
int num[MAXN][MAXN], f[MAXM], g[MAXM];
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
int gauss(int n) {
	int ans = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++)
			if (a[j][i]) {
				swap(a[i], a[j]);
				ans = P - ans;
			}
		int inv = power(a[i][i], P - 2);
		for (int j = i + 1; j <= n; j++)
			if (a[j][i]) {
				int tmp = 1ll * a[j][i] * inv % P;
				for (int k = i; k <= n; k++)
					update(a[j][k], P - 1ll * a[i][k] * tmp % P);
			}
	}
	for (int i = 1; i <= n; i++)
		ans = 1ll * ans * a[i][i] % P;
	return ans;
}
int solve(int type) {
	for (int i = 0; i <= n; i++)
	for (int j = 0; j <= m; j++)
		if ((i + j) % 2 == type) f[num[i][j]] = num[i][j];
		else f[num[i][j]] = 0;
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
		if ((i + j) % 2 == type) {
			if (s[i][j] == '\\') {
				int x = find(num[i][j]), y = find(num[i - 1][j - 1]);
				if (x == y) return 0;
				else f[x] = y;
			}
		} else {
			if (s[i][j] == '/') {
				int x = find(num[i - 1][j]), y = find(num[i][j - 1]);
				if (x == y) return 0;
				else f[x] = y;
			}
		}
	}
	int cnt = 0;
	for (int i = 1; i <= tot; i++)
		if (f[i] == i) g[i] = ++cnt;
	if (cnt > 200) return 0;
	memset(a, 0, sizeof(a));
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= m; j++) {
		if ((i + j) % 2 == type) {
			if (s[i][j] == '*') {
				int x = g[find(num[i][j])], y = g[find(num[i - 1][j - 1])];
				if (x != y) {
					update(a[x][x], 1);
					update(a[y][y], 1);
					update(a[x][y], P - 1);
					update(a[y][x], P - 1);
				}
			}
		} else {
			if (s[i][j] == '*') {
				int x = g[find(num[i - 1][j])], y = g[find(num[i][j - 1])];
				if (x != y) {
					update(a[x][x], 1);
					update(a[y][y], 1);
					update(a[x][y], P - 1);
					update(a[y][x], P - 1);
				}
			}
		}
	}
	return gauss(cnt - 1);
}
int main() {
	read(n), read(m), read(P);
	for (int i = 1; i <= n; i++)
		scanf("\n%s", s[i] + 1);
	for (int i = 0; i <= n; i++)
	for (int j = 0; j <= m; j++)
		num[i][j] = ++tot;
	int ans = solve(0);
	update(ans, solve(1));
	cout << ans << endl;
	return 0;
}

Codeforces 582D Number of Binominal Coefficients

考虑在 pp 进制下对 N,N−K,KN,N-K,K 进行数位动态规划。

令 f(x,p)f(x,p) 表示 x!x! 中质因数 pp 的个数，则有 f(x,p)=⌊xp⌋+⌊xp2⌋+⌊xp3⌋+…f(x,p)=\lfloor\frac{x}{p}\rfloor+\lfloor\frac{x}{p^2}\rfloor+\lfloor\frac{x}{p^3}\rfloor+\dots

也就是说， f(x,p)f(x,p) 就等于 xx 在 pp 进制下的前一位、 前两位、前三位……相加得到的结果。

题目中给出的限制是 f(N,p)−f(K,p)−f(N−K,p)≥αf(N,p)-f(K,p)-f(N-K,p)\geq \alpha 。
注意到由上文的推导， f(N,p)−f(K,p)−f(N−K,p)f(N,p)-f(K,p)-f(N-K,p) 就是 pp 进制下 K+(N−K)K+(N-K) 的进位次数。

因此， f(N,p)−f(K,p)−f(N−K,p)≤LogpAf(N,p)-f(K,p)-f(N-K,p)\leq Log_pA ，可以计入数位动态规划的状态。

时间复杂度 O(∣A∣2)O(|A|^2) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3405;
const int Q = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int MAXP = 205, P = 1e9;
struct INT {
	int len, a[MAXP];
	INT () {
		len = 1;
		memset(a, 0, sizeof(a));
	}
	INT (int num) {
		assert(num < P);
		len = 1;
		memset(a, 0, sizeof(a));
		a[0] = num;
	}
};
bool operator < (const INT &x, const INT &y) {
	if (x.len < y.len) return true;
	if (x.len > y.len) return false;
	for (int i = x.len - 1; i >= 0; i--) {
		if (x.a[i] < y.a[i]) return true;
		if (x.a[i] > y.a[i]) return false;
	}
	return false;
}
bool operator > (const INT &x, const INT &y) {
	if (x.len > y.len) return true;
	if (x.len < y.len) return false;
	for (int i = x.len - 1; i >= 0; i--) {
		if (x.a[i] > y.a[i]) return true;
		if (x.a[i] < y.a[i]) return false;
	}
	return false;
}
bool operator <= (const INT &x, const INT &y) {
	if (x.len < y.len) return true;
	if (x.len > y.len) return false;
	for (int i = x.len - 1; i >= 0; i--) {
		if (x.a[i] < y.a[i]) return true;
		if (x.a[i] > y.a[i]) return false;
	}
	return true;
}
bool operator >= (const INT &x, const INT &y) {
	if (x.len > y.len) return true;
	if (x.len < y.len) return false;
	for (int i = x.len - 1; i >= 0; i--) {
		if (x.a[i] > y.a[i]) return true;
		if (x.a[i] < y.a[i]) return false;
	}
	return true;
}
bool operator == (const INT &x, const INT &y) {
	if (x.len != y.len) return false;
	for (int i = x.len - 1; i >= 0; i--)
		if (x.a[i] != y.a[i]) return false;
	return true;
}
bool operator != (const INT &x, const INT &y) {
	if (x.len != y.len) return true;
	for (int i = x.len - 1; i >= 0; i--)
		if (x.a[i] != y.a[i]) return true;
	return false;
}
INT operator + (const INT &x, const INT &y) {
	INT res;
	res.len = max(x.len, y.len) + 1;
	for (int i = 0; i < res.len; i++) {
		res.a[i] += x.a[i] + y.a[i];
		if (res.a[i] >= P) {
			res.a[i + 1] += res.a[i] / P;
			res.a[i] %= P;
		}
	}
	while (res.len >= 2 && res.a[res.len - 1] == 0) res.len--;
	return res;
}
INT operator += (INT &x, const INT &y) {
	x = x + y;
	return x;
}
INT operator - (const INT &x, const INT &y) {
	INT res; assert(x >= y);
	res.len = x.len;
	for (int i = 0; i < res.len; i++) {
		res.a[i] += x.a[i] - y.a[i];
		if (res.a[i] < 0) {
			res.a[i + 1] += res.a[i] / P;
			res.a[i] %= P;
			if (res.a[i] < 0) {
				res.a[i + 1] -= 1;
				res.a[i] += P;
			}
		}
	}
	while (res.len >= 2 && res.a[res.len - 1] == 0) res.len--;
	return res;
}
INT operator -= (INT &x, const INT &y) {
	x = x - y;
	return x;
}
INT operator * (const INT &x, const INT &y) {
	INT res;
	res.len = x.len + y.len;
	static long long tres[MAXP];
	memset(tres, 0, sizeof(tres));
	for (int i = 0; i < x.len; i++)
	for (int j = 0; j < y.len; j++) {
		long long tmp = 1ll * x.a[i] * y.a[j];
		tres[i + j] += tmp % P;
		tres[i + j + 1] += tmp / P;
	}
	for (int i = 0; i < res.len; i++) {
		tres[i + 1] += tres[i] / P; 
		res.a[i] = tres[i] % P;
	}
	while (res.len >= 2 && res.a[res.len - 1] == 0) res.len--;
	return res;
}
INT operator *= (INT &x, const INT &y) {
	x = x * y;
	return x;
}
INT operator / (const INT &x, const int &y) {
	INT res; ll rem = 0;
	res.len = x.len;
	for (int i = x.len - 1; i >= 0; i--) {
		rem += x.a[i];
		res.a[i] = rem / y;
		rem = rem % y * P;
	}
	while (res.len >= 2 && res.a[res.len - 1] == 0) res.len--;
	return res;
}
INT operator /= (INT &x, const int &y) {
	x = x / y;
	return x;
}
int operator % (const INT &x, const int &y) {
	int ans = x.a[x.len - 1] % y;
	for (int i = x.len - 2; i >= 0; i--)
		ans = (1ll * P * ans + x.a[i]) % y;
	return ans;
}
INT operator %= (INT &x, const int &y) {
	x = x % y;
	return x;
}
void print(const INT &x) {
	printf("%d", x.a[x.len - 1]);
	for (int i = x.len - 2; i >= 0; i--)
		printf("%09d", x.a[i]);
	printf("\n");
}
int p, q; INT n;
int tot, a[MAXN], dp[MAXN][2][2][MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= Q) x -= Q;
}
int func(int Max, int Lft) {
	if (Lft == 0) return (1ll + Max) * (2ll + Max) / 2 % Q;
	else return (1ll + Max) * (0ll + Max) / 2 % Q;
}
int gunc(int Max, int Lft) {
	if (Lft == 0) return (1ll + Max) * (p - 1 + p - 1 - Max) / 2 % Q; 
	else return (1ll + Max) * (p + p - Max) / 2 % Q;
}
int work(int pos, bool top, int last, int sum) {
	if (dp[pos][top][last][sum] != -1) return dp[pos][top][last][sum];
	int &ans = dp[pos][top][last][sum]; ans = 0;
	if (pos == 0) return ans = (last == 0) && (sum >= q);
	if (top) {
		if (last) {
			update(ans, 1ll * (p - 1 - a[pos]) * work(pos - 1, true, 0, sum) % Q);
			update(ans, 1ll * (p - 0 - a[pos]) * work(pos - 1, true, 1, sum + 1) % Q);
			update(ans, 1ll * gunc(a[pos] - 1, 0) * work(pos - 1, false, 0, sum) % Q);
			update(ans, 1ll * gunc(a[pos] - 1, 1) * work(pos - 1, false, 1, sum + 1) % Q);
		} else {
			update(ans, 1ll * (a[pos] + 1) * work(pos - 1, true, 0, sum) % Q);
			update(ans, 1ll * (a[pos] + 0) * work(pos - 1, true, 1, sum + 1) % Q);
			update(ans, 1ll * func(a[pos] - 1, 0) * work(pos - 1, false, 0, sum) % Q);
			update(ans, 1ll * func(a[pos] - 1, 1) * work(pos - 1, false, 1, sum + 1) % Q);
		}
	} else {
		if (last) {
			update(ans, 1ll * gunc(p - 1, 0) * work(pos - 1, false, 0, sum) % Q);
			update(ans, 1ll * gunc(p - 1, 1) * work(pos - 1, false, 1, sum + 1) % Q);
		} else {
			update(ans, 1ll * func(p - 1, 0) * work(pos - 1, false, 0, sum) % Q);
			update(ans, 1ll * func(p - 1, 1) * work(pos - 1, false, 1, sum + 1) % Q);
		}
	}
	return ans;
}
int main() {
	read(p), read(q), read(n);
	while (n > 0) {
		a[++tot] = n % p;
		n /= p;
	}
	memset(dp, -1, sizeof(dp));
	cout << work(tot, 1, 0, 0) << endl;
	return 0;
}

Codeforces 582E Boolean Function

考虑如何描述一个已知的函数，可以用 1616 个 0/10/1 变量分别表示其在各种变量取值下的取值。

由此，不难想到进行状态压缩动态规划，注意到转移是或 / 与卷积的形式，可以用 FWT 优化转移。

时间复杂度 O(∣S∣×XLogX)O(|S|\times XLogX) ，其中 X=224=65536X=2^{2^4}=65536 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXS = 1 << 16;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
char s[MAXN];
int tot, dp[MAXN][MAXS];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
void FWTOR(int *a, int N) {
	for (int len = 2; len <= N; len <<= 1)
	for (int s = 0; s < N; s += len)
	for (int i = s, j = s + len / 2; j < s + len; i++, j++)
		a[j] = (a[i] + a[j]) % P;
}
void UFWTOR(int *a, int N) {
	for (int len = 2; len <= N; len <<= 1)
	for (int s = 0; s < N; s += len)
	for (int i = s, j = s + len / 2; j < s + len; i++, j++)
		a[j] = (a[j] - a[i] + P) % P;
}
void FWTAND(int *a, int N) {
	for (int len = 2; len <= N; len <<= 1)
	for (int s = 0; s < N; s += len)
	for (int i = s, j = s + len / 2; j < s + len; i++, j++)
		a[i] = (a[i] + a[j]) % P;
}
void UFWTAND(int *a, int N) {
	for (int len = 2; len <= N; len <<= 1)
	for (int s = 0; s < N; s += len)
	for (int i = s, j = s + len / 2; j < s + len; i++, j++)
		a[i] = (a[i] - a[j] + P) % P;
}
void getor(int *f, int *g, int *h) {
	static int a[MAXS], b[MAXS], c[MAXS];
	for (int i = 0; i < MAXS; i++)
		a[i] = f[i], b[i] = g[i];
	FWTOR(a, MAXS), FWTOR(b, MAXS);
	for (int i = 0; i < MAXS; i++)
		c[i] = 1ll * a[i] * b[i] % P;
	UFWTOR(c, MAXS);
	for (int i = 0; i < MAXS; i++)
		update(h[i], c[i]);
}
void getand(int *f, int *g, int *h) {
	static int a[MAXS], b[MAXS], c[MAXS];
	for (int i = 0; i < MAXS; i++)
		a[i] = f[i], b[i] = g[i];
	FWTAND(a, MAXS), FWTAND(b, MAXS);
	for (int i = 0; i < MAXS; i++)
		c[i] = 1ll * a[i] * b[i] % P;
	UFWTAND(c, MAXS);
	for (int i = 0; i < MAXS; i++)
		update(h[i], c[i]);
}
int solve(int l, int r) {
	int res = ++tot;
	if (l == r) {
		if (s[l] == 'A' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if (s & 1) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'B' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if (s & 2) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'C' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if (s & 4) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'D' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if (s & 8) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'a' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if ((s ^ 1) & 1) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'b' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if ((s ^ 2) & 2) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'c' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if ((s ^ 4) & 4) mask += 1 << s;
			dp[res][mask]++;
		}
		if (s[l] == 'd' || s[l] == '?') {
			int mask = 0;
			for (int s = 0; s <= 15; s++)
				if ((s ^ 8) & 8) mask += 1 << s;
			dp[res][mask]++;
		}
		return res;
	}
	int mid = 0, pre = 0;
	for (int i = l; i <= r; i++) {
		if (s[i] == '(') pre++;
		else if (s[i] == ')') pre--;
		else if (pre == 0) mid = i;
	}
	int x = solve(l + 1, mid - 2), y = solve(mid + 2, r - 1);
	if (s[mid] == '|' || s[mid] == '?') getor(dp[x], dp[y], dp[res]);
	if (s[mid] == '&' || s[mid] == '?') getand(dp[x], dp[y], dp[res]);
	return res;
}
int main() {
	scanf("%s", s + 1);
	int T, f = 0, g = 0; read(T);
	while (T--) {
		int a, b, c, d, x;
		read(a), read(b), read(c), read(d), read(x);
		int mask = a + b * 2 + c * 4 + d * 8;
		if (x == 0) f |= 1 << mask;
		else g |= 1 << mask;
	}
	int res = solve(1, strlen(s + 1)), ans = 0;
	for (int i = 0; i < MAXS; i++)
		if ((i & g) == g && (~i & f) == f) update(ans, dp[res][i]);
	cout << ans << endl;
	return 0;
}

Codeforces 585E Present for Vitalik the Philatelist

不考虑对于赠品集合 gcd>1gcd>1 的限制，则问题显然可以用莫比乌斯反演求解，只需要枚举购买的数，以及该数的一个因数即可。

注意到当赠品集合 gcd=1gcd=1 时，其余限制也都满足，因此，可以单独计算赠品集合 gcd=1gcd=1 的情况数，再在总数中减去。

赠品集合 gcd=1gcd=1 的情况数同样可以使用莫比乌斯反演计算，其中需要计算如下算式
∑i=0x(xi)(N−i)=∑i=0x(xi)N−∑i=0x(xi)i=N×2x−x×2x−1\sum_{i=0}^{x}\binom{x}{i}(N-i)=\sum_{i=0}^{x}\binom{x}{i}N-\sum_{i=0}^{x}\binom{x}{i}i=N\times2^x-x\times2^{x-1}

时间复杂度 O(N+VLogV)O(N+VLogV) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e7 + 5;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int tot, prime[MAXN], f[MAXN], miu[MAXN];
void sieve(int n) {
	miu[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (f[i] == 0) prime[++tot] = f[i] = i, miu[i] = P - 1;
		for (int j = 1; j <= tot && prime[j] <= f[i]; j++) {
			int tmp = prime[j] * i;
			if (tmp > n) break;
			f[tmp] = prime[j];
			if (prime[j] == f[i]) miu[tmp] = 0;
			else miu[tmp] = (P - miu[i]) % P;
		}
	}
}
int cnt[MAXN], two[MAXN];
int func(int cnt, int n) {
	int ans = 1ll * two[cnt] * n % P;
	update(ans, P - 1ll * two[cnt - 1] * cnt % P);
	update(ans, P - n);
	return ans;
}
int main() {
	int n, m = 1e7, ans = 0; read(n);
	for (int i = 1; i <= n; i++) {
		int x; read(x);
		cnt[x]++;
	}
	sieve(m), two[0] = 1;
	for (int i = 1; i <= m; i++)
		two[i] = two[i - 1] * 2 % P;
	for (int i = 1; i <= m; i++) {
		int all = 0;
		for (int j = i; j <= m; j += i)
			all += cnt[j];
		if (all && miu[i]) {
			int coef = 1ll * miu[i] * two[all - 1] % P;
			for (int j = i; j <= m; j += i)
				update(ans, 1ll * coef * cnt[j] % P);
			if (miu[i] == 1) update(ans, P - func(all, n));
			else update(ans, func(all, n));
		}
	}
	cout << ans << endl;
	return 0;
}

Codeforces 585F Digits of Number Pi

对所有可行的匹配串建立 AC 自动机，然后在上面数位 DP 即可。

时间复杂度 O(Nd2)O(Nd^2) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 55;
const int MAXP = 3e4 + 5;
const int P = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
namespace ACAutomaton {
	const int MAXP = 3e4 + 5;
	const int MAXC = 10;
	int root, size;
	bool key[MAXP];
	int child[MAXP][MAXC];
	int depth[MAXP], fail[MAXP], last[MAXP];
	void init() {root = size = 0; }
	int index(char x) {
		return x - '0';
	}
	void insert(char *s, int len) {
		int now = root;
		for (int i = 1; i <= len; i++) {
			int tmp = index(s[i]);
			if (child[now][tmp] == 0) {
				child[now][tmp] = ++size;
				depth[size] = depth[now] + 1;
			}
			now = child[now][tmp];
		}
		key[now] = true;
	}
	void build() {
		static int q[MAXP];
		int l = 0, r = -1;
		for (int i = 0; i < MAXC; i++)
			if (child[root][i]) {
				q[++r] = child[root][i];
				fail[child[root][i]] = root;
				last[child[root][i]] = root;
			}
		while (l <= r) {
			int tmp = q[l++];
			for (int i = 0; i < MAXC; i++)
				if (child[tmp][i]) {
					q[++r] = child[tmp][i];
					fail[child[tmp][i]] = child[fail[tmp]][i];
				} else child[tmp][i] = child[fail[tmp]][i];
			last[tmp] = key[fail[tmp]] ? fail[tmp] : last[fail[tmp]];
		}
	}
	bool run(char *s, int n) {
		int pos = root;
		for (int i = 1; i <= n; i++) {
			pos = child[pos][index(s[i])];
			if (key[pos]) return true;
		}
		return false;
	}
	int dp[MAXN][2][MAXP];
	int work(char *s, int n) {
		memset(dp, 0, sizeof(dp)), dp[0][1][root] = 1;
		for (int i = 1; i <= n; i++)
		for (int j = 0; j <= size; j++) {
			int tmp = dp[i - 1][0][j];
			if (tmp) {
				for (int k = 0; k <= 9; k++) {
					int nxt = key[j] ? j : child[j][k];
					update(dp[i][0][nxt], tmp);
				}
			}
			tmp = dp[i - 1][1][j];
			if (tmp) {
				int tnp = index(s[i]);
				for (int k = 0; k <= tnp; k++) {
					int nxt = key[j] ? j : child[j][k];
					update(dp[i][k == tnp][nxt], tmp);
				}
			}
		}
		int ans = 0;
		for (int i = 0; i <= size; i++)
			if (key[i]) {
				update(ans, dp[n][0][i]);
				update(ans, dp[n][1][i]);
			}
		return ans;
	}
}
char s[MAXN], x[MAXN], y[MAXN];
int main() {
	scanf("\n%s", s + 1);
	scanf("\n%s", x + 1);
	scanf("\n%s", y + 1);
	int n = strlen(s + 1), m = strlen(x + 1);
	for (int i = 0; i + m / 2 <= n; i++)
		ACAutomaton :: insert(s + i, m / 2);
	ACAutomaton :: build();
	int ans = ACAutomaton :: work(y, m);
	update(ans, P - ACAutomaton :: work(x, m));
	update(ans, ACAutomaton :: run(x, m));
	cout << ans << endl;
	return 0;
}

Codeforces 587D Duff in Mafia

首先二分答案，考虑如何判断是否可以只删除 ≤x\leq x 的边完成目标。

单独考虑某一种颜色的边，如果一个点的度数 ≥3\geq 3 ，则问题显然无解。

否则，所构成的图应当是若干条链，或者环，可分为以下几类：
(1)(1) 、奇环：问题无解
(2)(2) 、偶环：任取一组最大匹配删去
(3)(3) 、奇链：优先删去不含头尾的一组匹配
(4)(4) 、偶链：存在两种删法，分别需要多占用一个节点

偶链的匹配问题可以通过并查集解决，可见 【CodeForces875F】Royal Questions 。

时间复杂度 O((N+M)LogV)O((N+M)LogV) ，以下代码为了实现方便在检查时使用了排序。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int INF  = 1e9 + 7;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
vector <int> b[MAXN], e[2], pointsII;
int n, m, f[MAXN], s[MAXN], Max[2];
bool vis[MAXN][2], vise[MAXN], cole[MAXN], used[MAXN];
struct edge {int x, y, n, c, t; } a[MAXN];
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void dfs(int pos, bool c) {
	chkmax(Max[c], a[pos].t);
	e[c].push_back(pos);
	vise[pos] = true, cole[pos] = c;
	pointsII.push_back(a[pos].x);
	pointsII.push_back(a[pos].y);
	for (auto x : b[a[pos].x])
		if (!vise[x]) dfs(x, c ^ true);
		else if (pos != x && cole[pos] == cole[x]) Max[0] = Max[1] = INF;
	for (auto x : b[a[pos].y])
		if (!vise[x]) dfs(x, c ^ true);
		else if (pos != x && cole[pos] == cole[x]) Max[0] = Max[1] = INF;
}
bool check(int x) {
	for (int i = 1; i <= n; i++)
		f[i] = i, s[i] = 0, used[i] = false;
	for (int i = 1; i <= m; i++)
		vise[i] = false;
	for (int i = 1, nxt; i <= m; i = nxt + 1) {
		nxt = i; while (nxt + 1 <= m && a[nxt + 1].c == a[i].c) nxt++;
		vector <int> points;
		for (int j = i; j <= nxt; j++) {
			points.push_back(a[j].x);
			points.push_back(a[j].y);
		}
		sort(points.begin(), points.end());
		points.erase(unique(points.begin(), points.end()), points.end());
		for (auto x : points) {
			vis[x][0] = vis[x][1] = false;
			b[x].clear();
		}
		for (int j = i; j <= nxt; j++) {
			b[a[j].x].push_back(j);
			b[a[j].y].push_back(j);
			
		}
		for (auto x : points)
			if (b[x].size() >= 3) return false;
		for (int j = i; j <= nxt; j++)
			if (!vise[j]) {
				Max[0] = Max[1] = 0;
				e[0].clear();
				e[1].clear();
				pointsII.clear();
				dfs(j, false);
				if (Max[0] > x && Max[1] > x) return false;
				if (Max[0] > x) {
					for (auto x : e[1]) {
						if (used[a[x].x] || used[a[x].y]) return false;
						used[a[x].x] = used[a[x].y] = true;
					}
				} else if (Max[1] > x) {
					for (auto x : e[0]) {
						if (used[a[x].x] || used[a[x].y]) return false;
						used[a[x].x] = used[a[x].y] = true;
					}
				} else {
					if (e[0].size() > e[1].size()) swap(e[0], e[1]);
					if (e[0].size() < e[1].size()) {
						for (auto x : e[0]) {
							if (used[a[x].x] || used[a[x].y]) return false;
							used[a[x].x] = used[a[x].y] = true;
						}
					} else {
						int tx = 0, ty = 0;
						for (auto x : e[0]) vis[a[x].x][0] = vis[a[x].y][0] = true;
						for (auto x : e[1]) vis[a[x].x][1] = vis[a[x].y][1] = true;
						sort(pointsII.begin(), pointsII.end());
						pointsII.erase(unique(pointsII.begin(), pointsII.end()), pointsII.end());
						for (auto x : pointsII) {
							if (vis[x][0] && !vis[x][1]) {
								assert(tx == 0);
								tx = x;
							}
							if (vis[x][1] && !vis[x][0]) {
								assert(ty == 0);
								ty = x;
							}
							if (vis[x][1] && vis[x][0]) {
								if (used[x]) return false;
								used[x] = true;
							}
						}
						if (tx != 0) {
							tx = find(tx), ty = find(ty);
							if (tx != ty) f[tx] = ty, s[ty] += s[tx] + 1;
							else s[tx]++;
						}
					}
				}
			}
	}
	for (int i = 1; i <= n; i++)
		if (!used[i]) s[find(i)]--;
	for (int i = 1; i <= n; i++)
		if (s[find(i)] > 0) return false;
	return true;
}
vector <int> ans;
vector <pair <int, pair <vector <int>, vector <int>>>> c[MAXN];
void getans(int pos, int fa) {
	for (auto x : c[pos])
		if (x.first != fa) {
			if (!used[x.first]) getans(x.first, pos);
			if (!used[x.first]) {
				used[x.first] = true;
				for (auto y : x.second.first) ans.push_back(a[y].n);
			} else {
				assert(!used[pos]), used[pos] = true;
				for (auto y : x.second.second) ans.push_back(a[y].n);
			}
		}
}
void printans(int x) {
	for (int i = 1; i <= n; i++)
		f[i] = i, s[i] = 0, used[i] = false;
	for (int i = 1; i <= m; i++)
		vise[i] = false;
	for (int i = 1, nxt; i <= m; i = nxt + 1) {
		nxt = i; while (nxt + 1 <= m && a[nxt + 1].c == a[i].c) nxt++;
		vector <int> points;
		for (int j = i; j <= nxt; j++) {
			points.push_back(a[j].x);
			points.push_back(a[j].y);
		}
		sort(points.begin(), points.end());
		points.erase(unique(points.begin(), points.end()), points.end());
		for (auto x : points) {
			vis[x][0] = vis[x][1] = false;
			b[x].clear();
		}
		for (int j = i; j <= nxt; j++) {
			b[a[j].x].push_back(j);
			b[a[j].y].push_back(j);
		}
		for (auto x : points)
			if (b[x].size() >= 3) assert(false);
		for (int j = i; j <= nxt; j++)
			if (!vise[j]) {
				Max[0] = Max[1] = 0;
				e[0].clear();
				e[1].clear();
				pointsII.clear();
				dfs(j, false);
				if (Max[0] > x && Max[1] > x) assert(false);
				if (Max[0] > x) {
					for (auto x : e[1]) {
						if (used[a[x].x] || used[a[x].y]) assert(false);
						used[a[x].x] = used[a[x].y] = true;
						ans.push_back(a[x].n);
					}
				} else if (Max[1] > x) {
					for (auto x : e[0]) {
						if (used[a[x].x] || used[a[x].y]) assert(false);
						used[a[x].x] = used[a[x].y] = true;
						ans.push_back(a[x].n);
					}
				} else {
					if (e[0].size() > e[1].size()) swap(e[0], e[1]);
					if (e[0].size() < e[1].size()) {
						for (auto x : e[0]) {
							if (used[a[x].x] || used[a[x].y]) assert(false);
							used[a[x].x] = used[a[x].y] = true;
							ans.push_back(a[x].n);
						}
					} else {
						int tx = 0, ty = 0;
						for (auto x : e[0]) vis[a[x].x][0] = vis[a[x].y][0] = true;
						for (auto x : e[1]) vis[a[x].x][1] = vis[a[x].y][1] = true;
						sort(pointsII.begin(), pointsII.end());
						pointsII.erase(unique(pointsII.begin(), pointsII.end()), pointsII.end());
						for (auto x : pointsII) {
							if (vis[x][0] && !vis[x][1]) {
								assert(tx == 0);
								tx = x;
							}
							if (vis[x][1] && !vis[x][0]) {
								assert(ty == 0);
								ty = x;
							}
							if (vis[x][1] && vis[x][0]) {
								if (used[x]) assert(false);
								used[x] = true;
							}
						}
						if (tx != 0) {
							if (find(tx) != find(ty)) {
								f[find(tx)] = find(ty);
								c[tx].emplace_back(ty, make_pair(e[1], e[0]));
								c[ty].emplace_back(tx, make_pair(e[0], e[1]));
							} else {
								used[tx] = true;
								for (auto x : e[0]) ans.push_back(a[x].n);
							}
						} else for (auto x : e[0]) ans.push_back(a[x].n);
					}
				}
			}
	}
	for (int i = 1; i <= n; i++)
		if (!used[i]) getans(i, 0);
	cout << ans.size() << endl;
	for (auto x : ans)
		printf("%d ", x);
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= m; i++) {
		read(a[i].x), read(a[i].y), a[i].n = i;
		read(a[i].c), read(a[i].t);
	}
	sort(a + 1, a + m + 1, [&] (edge x, edge y) {return x.c < y.c; });
	int l = 0, r = INF;
	while (l < r) {
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	if (l == INF) puts("No");
	else {
		puts("Yes");
		printf("%d ", l);
		printans(l);
	}
	return 0;
}

Codeforces 587F Duff is Mad

首先建立后缀树，然后离线操作，考虑计算形如 1 r k1\ r\ k 的询问，原有的询问显然可以拆分为两份。

那么，我们需要在线支持对某点子树中所有后缀节点所在串的答案 +1+1 ，以及查询一个串当前的答案。

可以通过 DFS 序将问题转化到序列上，则问题可以形式化地表述为：
给定长度为 NN 的序列 aia_i ，以及初始时全为 0 的数组 ansians_i 。
在线支持以下两种操作：
(1)(1) 、给定 l,rl,r ，对于 l≤i≤rl\leq i\leq r ，令 ansaians_{a_i} +1+1
(2)(2) 、给定 xx ，查询 ansxans_x

可以通过序列分块，记录整块被操作的次数做到 O(N)O(\sqrt{N}) 的修改和查询。

时间复杂度 O(NN)O(N\sqrt{N}) 。

#include<bits/stdc++.h>
using namespace std;
const int MAXK = 405;
const int MAXN = 1e5 + 5;
typedef long long ll;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int timer, a[MAXN], l[MAXN], r[MAXN];
namespace MultipleSuffixAutomaton {
	const int MAXN = 2 * 100005;
	const int MAXC = 26;
	int root, size, last;
	int child[MAXN][MAXC];
	int fail[MAXN], depth[MAXN];
	vector <int> col[MAXN], fin[MAXN], e[MAXN];
	int newnode(int dep) {
		fail[size] = 0;
		depth[size] = dep;
		memset(child[size], 0, sizeof(child[size]));
		return size++;
	}
	void extend(int ch, int colour) {
		int p = last;
		if (child[p][ch]) {
			int q = child[p][ch];
			if (depth[p] + 1 == depth[q]) col[last = q].push_back(colour);
			else {
				int np = newnode(depth[p] + 1);
				while (child[p][ch] == q) {
					child[p][ch] = np;
					p = fail[p];
				}
				fail[np] = fail[q]; fail[q] = np;
				memcpy(child[np], child[q], sizeof(child[q]));
				col[last = np].push_back(colour);
			}
		} else {
			int np = newnode(depth[p] + 1);
			while (child[p][ch] == 0) {
				child[p][ch] = np;
				p = fail[p];
			}
			if (child[p][ch] == np) fail[np] = root;
			else {
				int q = child[p][ch];
				if (depth[p] + 1 == depth[q]) fail[np] = q;
				else {
					int nq = newnode(depth[p] + 1);
					memcpy(child[nq], child[q], sizeof(child[q]));
					fail[nq] = fail[q];
					fail[q] = fail[np] = nq;
					while (child[p][ch] == q) {
						child[p][ch] = nq;
						p = fail[p];
					}
				}
			}
			col[last = np].push_back(colour);
		}
	}
	void init() {
		size = 0;
		root = newnode(0);
	}
	void insert(char *s, int colour) {
		last = root;
		int len = strlen(s + 1);
		for (int i = 1; i <= len; i++)
			extend(s[i] - 'a', colour);
		fin[last].push_back(colour);
	}
	void dfs(int pos) {
		int dfn = timer + 1;
		for (auto x : col[pos]) a[++timer] = x;
		for (auto x : e[pos]) dfs(x);
		int rit = timer;
		for (auto x : fin[pos]) l[x] = dfn, r[x] = rit;
	}
	void work() {
		for (int i = 1; i < size; i++)
			e[fail[i]].push_back(i);
		dfs(0);
	}
}
char s[MAXN]; int ans[MAXN], bns[MAXN], cnt[MAXK][MAXN];
int n, m, tot, block, belong[MAXN], ql[MAXN], qr[MAXN];
ll res[MAXN]; vector <pair <int, int>> qry[MAXN];
ll query(int x) {
	ll res = ans[x];
	for (int i = 1; i <= tot; i++)
		res += 1ll * cnt[i][x] * bns[i];
	return res;
}
void modify(int l, int r) {
	if (belong[l] == belong[r]) {
		for (int i = l; i <= r; i++)
			ans[a[i]]++;
	} else {
		for (int i = l; i <= qr[belong[l]]; i++)
			ans[a[i]]++;
		for (int i = belong[l] + 1; i <= belong[r] - 1; i++)
			bns[i]++;
		for (int i = ql[belong[r]]; i <= r; i++)
			ans[a[i]]++;
	}
}
int main() {
	read(n), read(m);
	MultipleSuffixAutomaton :: init();
	for (int i = 1; i <= n; i++) {
		scanf("\n%s", s + 1);
		MultipleSuffixAutomaton :: insert(s, i);
	}
	MultipleSuffixAutomaton :: work();
	block = sqrt(timer);
	for (int i = 1; i <= timer; i++) {
		if (i % block == 1 % block) ql[++tot] = i;
		belong[i] = tot, qr[tot] = i;
	}
	for (int i = 1; i <= tot; i++)
	for (int j = ql[i]; j <= qr[i]; j++)
		cnt[i][a[j]]++;
	for (int i = 1; i <= m; i++) {
		int l, r, x; read(l), read(r), read(x);
		qry[r].emplace_back(x, i);
		qry[l - 1].emplace_back(x, -i);
	}
	for (int i = 1; i <= n; i++) {
		modify(l[i], r[i]);
		for (auto x : qry[i]) {
			if (x.second < 0) res[-x.second] -= query(x.first);
			else res[x.second] += query(x.first);
		}
	}
	for (int i = 1; i <= m; i++)
		writeln(res[i]);
	return 0;
}
相关标签： 【类型】做题记录

上一篇： 洛谷P1646 [国家集训队]happiness【网络流二元关系】

下一篇： 【集训队作业】IOI 2020 集训队作业 试题泛做 3

推荐阅读