gym103428 部分题解

B

考虑集合不好算，先算一个长为 \(k\) 的序列（可以重复）的方案数，然后容斥出集合的方案。

第一部分：计算序列个数。

称一个可重集为一个「块」当且仅当其所有元素在 \([c\cdot 2^k,c\cdot 2^{k+1})\) 之间且所有元素的出现次数相同。于是 \([0,n]\) 可以分解成 \(\mathcal O(\log n)\) 个块。容易发现如下两个性质：

从一个块中选择若干个元素异或起来，得到的还是一个大小相同的块
从两个块中选择各若干个（非空个）元素异或起来，得到的还是一个块，且大小等于较大的那个

于是考虑枚举一个块 \((c,2^t)\)，然后统计所有元素中最大的那个出现在这个块中的方案数。注意到此时所有小于这个块的数全都是等价的，只需要统计其个数 \(sum\)，然后容易写出如下的柿子：

\[f_k\gets f_k+\sum_{x\geq 1}\frac{\binom{t}{b-h_x}}{2^t} \binom kx 2^{tx} sum^{k-x} \]

其意义即为从当前块中选取 \(x\) 个元素，然后从后面选取 \(k-x\) 个元素异或起来，其中恰好有 \(h_x\) 个 \(1\) 的我们统计进答案，其中 \(h_x\) 为一个只和 \(x\) 奇偶性有关的量，其表示了二进制大于 \(t\) 的那些位置的 \(1\) 的个数。

然后我们要对每个 \(k\) 计算这个柿子，暴力复杂度是 \(\mathcal O(k^2\log n)\) 的，但是注意到这个柿子只和 \(x\) 奇偶性有关，于是考虑计算 \((A+Bx)^k\bmod (x^2-1)\) 的值，这可用长为 \(2\) 的 NTT 快速进行计算，于是复杂度优化成了 \(\mathcal O(k\log n)\)

第二部分：容斥。

考虑记 \(g_i\) 为 \(i\) 的答案，于是枚举一个 \(j<i\)，然后计算去重后变成 \(j\) 的序列个数。相当于 \(j\) 个元素要求出现奇数次，\(n-j+1\) 个元素要求出现偶数次，可以写出如下的两个多项式：

\[\left\{ \begin{aligned} & \sinh(x)=\frac{e^x-e^{-x}}{2}=\sum_{i\geq 0}\frac{x^{2i+1}}{(2i+1)!}\\ & \cosh(x)=\frac{e^x+e^{-x}}{2}=\sum_{i\geq 0}\frac{x^{2i}}{(2i)!}\\ \end{aligned} \right. \]

于是要求的容斥系数就是 \([x^i]\sinh^j(x)\cosh^{n-j+1}(x)\)。注意到这个函数求导后变成 \(j\sinh^{j-1}(x)\cosh^{n-j+2}(x)+(n-j+1)\sinh^{j+1}(x)\cosh^{n-j}(x)\)，于是可以递归到子问题。

这部分的复杂度为 \(\mathcal O(k^2)\)，总复杂度为 \(\mathcal O(k(k+\log n))\)

#include <ctime>
#include <cstdio>

#define nya(neko...) fprintf(stderr, neko)

__attribute__((destructor))
inline void ptime() {
	nya("\nTime: %.3lf(s)\n", 1. * clock() / CLOCKS_PER_SEC);
}

#include <algorithm>

using ll = long long;
constexpr ll mod = 998244353;
constexpr ll inv2 = (mod + 1) / 2;

inline ll fsp(ll a, ll b, ll res = 1) {
	for(a %= mod; b; a = a * a % mod, b >>= 1)
		b & 1 ? res = res * a % mod : 0; return res;
}

#define ppcnt(x) __builtin_popcount(x)

int n, k, b, cnt;
struct Block { int k, c; } blk[100];

inline ll binom(ll n, int k) {
	ll fz = 1, fm = 1;
	for(int i = 1; i <= k; ++i)
		fm = fm * i % mod, fz = fz * (n - i + 1) % mod;
	return fsp(fm, mod - 2, fz);
}

constexpr int maxk = 5005;

ll C[100][100], coef[2][maxk];

ll f[maxk], g[maxk];
int main() {
	for(int i = 0; i <= 50; ++i) {
		C[i][0] = 1;
		for(int j = 1; j <= i; ++j)
			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
	}

	scanf("%d%d%d", &n, &k, &b);
	
	blk[++cnt] = { 0, n };
	for(int i = 0; i <= 30; ++i) if(n >> i & 1)
		blk[++cnt] = { i, n >> i + 1 << i + 1 };
	
	if(ppcnt(n) == b) for(int i = 0; i <= k; ++i) if(i & 1) ++f[i];
	if(!b) for(int i = 0; i <= k; ++i) if(!(i & 1)) ++f[i];
	
	f[0] = !b;
	for(int i = 2, sum = 1; i <= cnt; ++i) {
		ll A = 1 << blk[i].k, B = sum;
		
		ll w[2] = { 1, 1 }, invA = fsp(A, mod - 2);
		for(int k = 1; k <= ::k; ++k) {
			w[0] = w[0] * (A + B) % mod;
			w[1] = w[1] * (A - B) % mod;
			
			for(int x : { 0, 1 }) {
				int o = k - x & 1 ? blk[i].c : 0;
				int z = x & 1 ? blk[i].c + (1 << blk[i].k) : 0;
				int t = b - ppcnt(o ^ z);
				
				ll fa = (!x ? w[0] + w[1] : w[0] - w[1]) * inv2 % mod * invA % mod;
				if(t >= 0) (f[k] += C[blk[i].k][t] * fa) %= mod;
				
				if(!(k - x & 1)) {
					(f[k] -= invA * fsp(B, k) % mod * C[blk[i].k][t]) %= mod;
				}
			}
		}
		sum += 1 << blk[i].k;
	}
	
	// g_i <- g_i - g_j [x^i]((e^x - e^{-x}) / 2)^j((e^x + e^{-x}) / 2)^{n + 1 - j}
	
	int cur = 0;
	
	coef[0][0] = 1, g[0] = f[0];
	
	ll fac = 1;
	for(int i = 1; i <= k; ++i) {
		fac = fac * i % mod;
		
		cur ^= 1;
		for(int j = 0; j <= i; ++j) {
			coef[cur][j] = j ? j * coef[cur ^ 1][j - 1] % mod : 0;
			(coef[cur][j] += (n - j + 1) * coef[cur ^ 1][j + 1]) %= mod;
		}
		
		g[i] = f[i];
		for(int t = i - 1; t >= 0; --t)
			(g[i] -= g[t] * coef[cur][t]) %= mod;
		g[i] = fsp(fac, mod - 2, g[i]);
	}
	printf("%lld\n", (g[k] + mod) % mod);
}

C

求对数，变成求

\[(\sum_i x^{a_i})\prod_i(1+x^{b_i}) \bmod (x^{\varphi(p)}-1) \]

的各项系数是否为 \(0\)。

考虑每次的转移为 \(dp_x\gets dp_x\or dp_{x-b_i}\)。注意到这个转移中 \(0\to 1\) 和 \(1\to 0\) 的个数是相同的（因为构成环），所以只要每次快速找到 \(dp_x\) 和 \(dp_{x+b_i}\) 不同的位置复杂度就是对的。设上一次修改的位置为 \(p\)，我们可以二分一个值 \(x\)，然后判断 \([p,p+x]\) 和 \([p+b_i,p+b_i+x]\) 是否是相同的。这可以通过树状数组和哈希实现。

总复杂度 \(\mathcal O(n\log^2 n)\)

#include <cstdio>
#include <bitset>
#include <vector>

constexpr int maxn = 1E+6 + 5;
constexpr int maxmod = 2E+5 + 5;

int mod, n, b[maxn], cntb;
bool visa[maxmod], ans0;

inline int fsp(int a, int b, int res = 1) {
	for(a %= mod; b; a = 1ll * a * a % mod, b >>= 1)
		b & 1 && (res = 1ll * res * a % mod); return res;
}

inline int getgen(int md) {
	if(md == 2) return 1;
	
	std::vector<int> pri;

	int x = md - 1;
	for(int i = 2; i * i <= x; ++i) {
		if(x % i == 0) pri.push_back(i);
		while(x % i == 0) x /= i;
	}
	if(x > 1) pri.push_back(x);

	for(int i = 2; i < md; ++i) {
		for(int x : pri) if(fsp(i, (md - 1) / x) == 1) goto fail;
		return i;
		fail:;
	}
}

int lg[maxmod];
bool dp[maxmod << 1];

using ll = long long;
constexpr ll MOD = 19260817;
constexpr ll base = 2333;

ll pw[maxmod << 1];
inline namespace BIT {
	ll t[maxmod << 1];
	inline void Add(int p, ll v) { ++p; while(p <= 2 * mod - 2) (t[p] += v) %= MOD, p += p & -p; }
	inline ll Sum(int l, int r) {
		++r;
		
		ll res = 0;
		while(r > l) (res += t[r]) %= MOD, r -= r & -r;
		while(l > r) (res -= t[l]) %= MOD, l -= l & -l;
		return res;
	}
}
inline void chk(int x) { dp[x] = 1, BIT::Add(x, pw[x]); }
inline bool cmp(int l1, int r1, int l2, int r2) {
	if(l1 > l2) std::swap(l1, l2), std::swap(r1, r2);
	return (BIT::Sum(l1, r1) * pw[l2 - l1] - BIT::Sum(l2, r2)) % MOD == 0;
}

inline int findnxt(int p, int d) {
	if(p >= mod - 1) return -1;
	
	int l = 0, r = mod - 2 - p;
	if(cmp(p, p + r, (p + d) % (mod - 1), (p + d) % (mod - 1) + r)) return -1;
	while(l < r) {
		int mid = l + r >> 1;
		if(!cmp(p, p + mid, (p + d) % (mod - 1), (p + d) % (mod - 1) + mid)) r = mid;
		else l = mid + 1;
	}
	return p + l;
}

int main() {
	scanf("%d%d", &mod, &n);
	for(int i = 1, o, x; i <= n; ++i) {
		scanf("%d%d", &o, &x);
		if(!x) ans0 = 1;
		else if(!o) visa[x] = 1;
		else b[++cntb] = x;
	}
	
	pw[0] = 1;
	for(int i = 1; i <= mod * 2; ++i)
		pw[i] = pw[i - 1] * base % MOD;

	int g = getgen(mod);
	for(int i = 0, cur = 1; i < mod - 1; ++i)
		lg[cur] = i, cur = 1ll * cur * g % mod;
	
	for(int i = 1; i < mod; ++i) if(visa[i]) chk(lg[i]), chk(lg[i] + mod - 1);
	if(!BIT::Sum(0, mod - 2)) return printf("%d\n", mod - 1), 0;
	
	for(int i = 1; i <= cntb; ++i) {
		int l = lg[b[i]];
		
		std::vector<int> pos;
		
		int p = -1;
		while(true) {
			p = findnxt(p + 1, l);
			if(!~p) break;
			pos.push_back(p);
		}
		
		for(int x : pos) if(dp[x]) {
			if(dp[x + l]) continue;
			
			chk((x + l) % (mod - 1)),
			chk((x + l) % (mod - 1) + mod - 1);
		}
	}
	
	int ans = ans0;
	for(int i = 0; i < mod - 1; ++i) ans += dp[i];
	printf("%d\n", mod - ans);
}

I

质因数分解，然后距离为每个质因数乘以两边次数的差值。考虑枚举每个质数考虑贡献，发现 \(\leq \sqrt n\) 的质数可以暴力算贡献，\(>\sqrt n\) 的质数只需要统计一项，也即统计区间素数和，可以 min_25 筛快速实现。

总复杂度 \(\mathcal O(\frac{n^{3/4}}{\log n})\)。

#include<cmath>
#include<algorithm>
#include<cstdio>
#include<unordered_map>

typedef long long ll;
const int maxn = 1E+6 + 5;
const ll mod = 1E+9 + 7;

int m, k, tot;
ll n, w[maxn], g[maxn];
std::unordered_map<ll, ll> id;

inline ll fsp(ll a, ll b, const ll &mod = mod, ll res = 1) {
	for(a %= mod, b %= mod - 1; b; a = a * a % mod, b >>= 1)
		b & 1 && (res = res * a % mod); return res;
}

ll sp[maxn];
int cnt, prime[maxn];
bool nprime[maxn];
inline void pre(int N) {
	for(int i = 2; i <= N; ++i) {
		if(!nprime[i]) prime[++cnt] = i, sp[cnt] = (sp[cnt - 1] + i) % mod;
		for(int j = 1; j <= cnt && i * prime[j] <= N; ++j) {
			nprime[i * prime[j]] = 1;
			if(i % prime[j] == 0) break;
		}
	}
}

inline ll Sum(ll x) { x %= mod; return x * (x + 1) / 2 % mod; }
inline ll calc(ll x) { return (x % mod) * ((n - x) % mod) % mod; }

int main() {
	scanf("%lld", &n);
	
	pre(sqrt(n) + 500);
	for(ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l), w[++tot] = n / l;
		g[tot] = Sum(w[tot]) - 1, id[w[tot]] = tot;
	}
	
	for(int j = 1; j <= cnt; ++j)
		for(int i = 1; i <= tot && 1ll * prime[j] * prime[j] <= w[i]; ++i)
			(g[i] -= prime[j] * (g[id[w[i] / prime[j]]] - sp[j - 1])) %= mod;
	
	ll ans = 0;
	for(int i = 1; i <= cnt; ++i) {
		ll cur = 1ll * prime[i] * prime[i];
		while(cur <= n) (ans += prime[i] * calc(n / cur)) %= mod, cur *= prime[i];
	}
	
	for(ll l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		(ans += calc(n / l) * (g[id[r]] - g[id[l - 1]])) %= mod;
	}

	printf("%lld\n", (ans * 2 % mod + mod) % mod);
}

K

考虑如果每个连通块大小不超过 \(4\) 即可，于是只需要每个点连向的点和它的出边不相同即可。

是二次剩余的连第一种，否则连第二种。在 \(a\) 是非二次剩余的时候可行，概率为 \(\frac 12\)。

#include <cstdio>

int mod;
inline int fsp(int a, int b, int res = 1) {
	for(a %= mod; b; a = 1ll * a * a % mod, b >>= 1)
		b & 1 && (res = 1ll * res * a % mod); return res;
}

int main() {
	scanf("%d", &mod);
	for(int i = 1; i < mod; ++i)
		printf("%d\n", fsp(i, (mod - 1) / 2) == 1);
}

L

最大团等于补图的最大独立集。考虑给补图定向：\(i<j\) 则 \(i\to j\)。

注意到如果 \(i<j<k,i\not\to j,j\not\to k\) 则 \(i\not\to k\)，于是不难证明最大独立集等于定向之后的最长反链长度。

根据 dilworth 定理，这就是最小链覆盖的大小，也即 \(n\) 减去拆入点和出点的二分图的最大匹配数。

现在的问题是，一张二分图，\(i\) 向所有 \(j>i\) 连边，去掉其上的 \(m\) 条边，求最大匹配数。

先考虑如何优化暴力匈牙利：注意到匈牙利实际上每次增广只会 dfs 到每个节点 \(1\) 次，于是如果可以快速知道当前点哪些出边是合法的即可快速进行增广，这可以用并查集实现，这部分的复杂度为单次增广 \(\mathcal O(n\alpha(n)+m)\)。

然后考虑如何减少增广次数。我们把所有点按照度数排序，然后从小到大暴力，如果当前点的所有出边中有没有匹配的点则直接匹配（即先考虑长度为 \(1\) 的增广路），然后对剩下的点暴力做上述匈牙利。可以证明做完这个操作之后剩余的点个数为 \(\mathcal O(\sqrt m)\) 级别。于是总复杂度为 \(\mathcal O((n\alpha(n)+m)\sqrt m)\)。

实际实现写的是 \(\mathcal O((n\log n+m\log m)\sqrt m)\)。

#include <set>
#include <cstdio>
#include <algorithm>

constexpr int maxn = 2E+5 + 5;

int n, m, a[maxn], deg[maxn], p[maxn];
std::set<std::pair<int, int>> fuck;

int matchl[maxn], matchr[maxn];

int fa[maxn];
inline int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
inline bool DFS(int u) {
	int p = u + 1;
	while(p = getfa(p), p <= n) {
		if(fuck.count({ u, p })) { ++p; continue; }
		else {
			fa[p] = p + 1;
			if(!matchr[p] || DFS(matchr[p])) {
				matchl[u] = p, matchr[p] = u;
				return true;
			}
		}
	}
	return false;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		deg[i] = n - i, p[i] = a[i] = i;
	for(int i = 1, x; i <= m; ++i) {
		scanf("%d", &x);
		fuck.emplace(std::min(a[x], a[x + 1]), std::max(a[x], a[x + 1]));
		--deg[std::min(a[x], a[x + 1])], std::swap(a[x], a[x + 1]);
	}
	
	std::set<int, std::greater<int>> S;
	for(int i = 1; i <= n; ++i) S.insert(i);
	
	std::sort(p + 1, p + n + 1, [](int x, int y) { return deg[x] < deg[y]; });

	int ans = 0;
	for(int I = 1; I <= n; ++I) {
		int i = p[I];
		if(deg[i] > ans) for(int p : S)
			if(p > i && !fuck.count({ i, p }))
				{ matchl[i] = p, matchr[p] = i, S.erase(p), ++ans; break; }
	}
	
	for(int i = 1; i <= n; ++i) if(!matchl[i]) {
		for(int j = 1; j <= n + 1; ++j) fa[j] = j;
		ans += DFS(i);
	}

	printf("%d\n", n - ans);
}