组合数学

HDU6333

link

$T$ 组询问，每次询问 $\sum_{i=0}^m C(n,i)$。

$1 \le T,n,m \le 10^5, m \le n$。

设 $F(n,m)=\sum_{i=0}^m C(n,i)$，画个杨辉三角易得

$$F(n,m+1)=F(n,m)+C(n,m)$$

$$F(n+1,m)=2F(n,m)-C(n,m)$$

莫队即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 100005
#define P 1000000007
#define iv2 500000004
int fac[N], inv[N], n, res[N];
struct node { int n, m, i; } a[N];

int qow(int x, int k, int r = 1) {
	for (; k; k >>= 1, x = x * x % P)
		if (k & 1) r = r * x % P;
	return r;
}
int C(int n, int m) {
	if (!n || !m) return 1; if (m > n) return 0;
	return fac[n] * inv[m] % P * inv[n - m] % P;
}

signed main() {
	fac[0] = 1;
	for (int i = 1; i < N; i ++) {
		fac[i] = fac[i - 1] * i % P;
	}
	inv[N - 1] = qow(fac[N - 1], P - 2);
	for (int i = N - 2; ~i; i --) {
		inv[i] = inv[i + 1] * (i + 1) % P;
	}
	n = read();
	for (int i = 1; i <= n; i ++) {
		a[i].n = read(), a[i].m = read(), a[i].i = i;
	}
	sort(a + 1, a + n + 1, [](node a, node b) {
		return a.m < b.m;
	});
	int B = sqrt(n);
	for (int l = 1, r = B; l <= n;) {
		sort(a + l, a + r + 1, [](node a, node b) {
			return a.n < b.n;
		});
		l = r + 1, r = min(n, l + B - 1);
	}
	int tn = a[1].n, tm = 0ll, ans = 1;
	for (int i = 1; i <= n; i ++) {
		while (tm < a[i].m) (ans += C(tn, ++ tm)) %= P;
		while (tm > a[i].m) (ans += P - C(tn, tm --)) %= P;
		while (tn < a[i].n) ans = (ans * 2 + P - C(tn ++, tm)) % P;
		while (tn > a[i].n) ans = ((ans + C(-- tn, tm)) * iv2 % P) % P;
		res[a[i].i] = ans;
	}
	for (int i = 1; i <= n; i ++) {
		printf("%lld\n", res[i]);
	}
	return 0;
}
/*
F(n, m) = C(n, 0) +...+ C(n, m);
F(n, m + 1) = F(n, m) + C(n,m + 1);
F(n + 1, m) = 2F(n, m) - C(n, m);
*/

HDU7060

link

给定 $n$ 位数，求所有把 $n$ 分割至多成 $k$ 段的方案中所有段数字的和（可以有前导零）。

对 $998244353$ 取模。

$1 \le k \le n \le 10^6$。

考虑每个位置 $i$ 的贡献。如果 $i$ 在数字的第 $j$ 位（$j$ 从 $0$ 开始），那么贡献就是 $10^j$，我们还需要计算此时的方案数。

用隔板法考虑位置，分类讨论：

• $i+j=n$，此时已选一个位置，那么就是在 $n-j-1$ 个位置中选最多 $k-1$ 个，$\sum_{a=0}^{k-1}C_{n-j-1}^a$；
• $i+j< n$,此时已选两个位置，那么就是在 $n-j-2$ 个位置中选最多 $k-2$ 个，$\sum_{a=0}^{k-2}C_{n-j-2}^a$；

贡献与 $i$ 无关，对于每个 $j$ 统计 $i$ 的数量，答案就是：

$$\sum_{i+j=n} \sum_{a=0}^{k-1}C_{n-j-1}^a + \sum_{i+j< n} \sum_{a=0}^{k-2}C_{n-j-2}^a$$

发现就是上题的 $F$，且 $F(n,m)$ 中的 $m$ 只有 $k-1,k-2$，直接预处理即可做到 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define P 998244353
#define N 1000005
int fac[N], inv[N], k, a[N], n, f[N], g[N];
char s[N]; 

int qow(int x, int k, int r = 1) {
	for (; k; k >>= 1, x = x * x % P)
		if (k & 1) r = r * x % P;
	return r;
}
int C(int n, int m) {
	if (!n || !m) return 1; if (m > n) return 0;
	return fac[n] * inv[m] % P * inv[n - m] % P;
}

signed main() {
	fac[0] = 1;
	for (int i = 1; i < N; i ++) {
		fac[i] = fac[i - 1] * i % P;
	}
	inv[N - 1] = qow(fac[N - 1], P - 2);
	for (int i = N - 2; ~i; i --) {
		inv[i] = inv[i + 1] * (i + 1) % P;
	}
	for (int T = read(); T --;) {
		k = read(), scanf("%s", s + 1);
		n = strlen(s + 1);
		for (int i = 1; i <= n; i ++) {
			a[i] = a[i - 1] + (s[i] & 15);
		}
		f[0] = g[0] = 1;
		for (int i = 1; i <= k - 2; i ++) {
			f[i] = (f[i - 1] + C(k - 2, i)) % P;
			g[i] = (g[i - 1] + C(k - 1, i)) % P;
		} g[k - 1] = (g[k - 2] + 1) % P;
		for (int i = max(1ll, k - 1); i <= n; i ++) { if (i >= k)
			g[i] = (2 * g[i - 1] + P - C(i - 1, k - 1)) % P;
			f[i] = (2 * f[i - 1] + P - C(i - 1, k - 2)) % P; 
		}
		int res = 0;
		for (int j = 0; j < n; j ++) {
			int J = qow(10, j), x = 0;
			if (n - j - 2 >= 0 && k - 2 >= 0) {
				if (n - j - 2 < k - 2) x = qow(2, n - j - 2);
				else x = f[n - j - 2];
				res = (res + a[n - j - 1] * J % P * x % P) % P;
			}
			if (n - j - 1 < k - 1) x = qow(2, n - j - 1);
			else x = g[n - j - 1];
			res = (res + (s[n - j] & 15) * J % P * x % P) % P;
		}
		printf("%lld\n", res);
	}
	return 0;
}
/*
F(n, m) = C(n, 0) +...+ C(n, m);
F(n, m + 1) = F(n, m) + C(n,m + 1);
F(n + 1, m) = 2F(n, m) - C(n, m);
*/

CF1716F

link

设一个长度为 $n$，元素取值在 $[1,m]$ 内的数组 $A$ 中奇数元素个数为 $x$，则令 $F(A)=x$。

对所有可能的 $A$，求 $\sum F(A)$。

对 $998244353$ 取模。

$T \le 5000$；$k\le 2000$；$n,m\le 998244353$

设 $[1,m]$ 中奇数个数为 $x$，偶数为 $y$，枚举奇数个数，则答案为：

$$\sum_{i=1}^n i^k C(n,i) x^{i}y^{n-i}$$

这个东西怎么算呢。。。。

---

考虑 $\sum_{i=1}^n iC_{n,i} = n\times 2^{n-1}$ 的证明过程：

$$(1+x)^n=\sum_{i=0}^n C(n,i)x^i$$

对两边同时求导：

$$n(1+x)^{n-1}=\sum_{i=1}^n iC(n,i)x^{i-1}$$

取 $x=1$ 即得证。

拓展一下：

$$(x+y)^n=\sum_{i=0}^n C(n,i)x^iy^{n-i}$$

右边这个和我们要求的很像，但是少了个 $i$，我们把 $y$ 看成常数求个导再乘上 $x$，就变成了我们想要的东西：

$$(x+y)^n=\sum_{i=0}^n C(n,i)x^iy^{n-i}$$

$$nx(x+y)^{n-1}=\sum_{i=1}^n iC(n,i)x^iy^{n-i}$$

但这只是 $k=1$ 的情况。我们可以通过求 $k$ 阶导并乘 $x^k$ 得到答案，例如 $k=2$：

$$nx(x+y)^{n-1}=\sum_{i=1}^n iC(n,i)x^iy^{n-i}$$

$$nx(x+y)^{n-1}+n(n-1)x^2(x+y)^{n-2} =\sum_{i=1}^n i^2C(n,i)x^iy^{n-i}$$

观察发现，答案形如 $\sum_{i=1}^k c_{k,i} x^i(x+y)^{n-i}$，其中 $c_{k,i}$ 是一个我们还不知道的系数。

考虑求出 $c_{k,i}$ 的递推式，那么对 $c_{k,i} x^i(x+y)^{n-i}$ 导：

$$c_{k,i} x^i(x+y)^{n-i}$$

$$c_{k,i} (n-i)x^i(x+y)^{n-i-1} + c_{k,i} ix^{i-1}(x+y)^{n-i}$$

$$c_{k+1,i} \gets (n-i)c_{k,i},c_{k+1,i-1}\gets ic_{k,i}$$

然后发现 $c_{k,i}=s_{k,i}\times n^{\underline{i}}$，$s$ 是斯特林数。别问我怎么看出来的然后预处理就可以做到 $O(k)$ 了。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 2005
#define P 998244353
int n, m, k, s[N][N];

int qow(int x, int k, int r = 1) {
	for (; k; k >>= 1, x = x * x % P) {
		if (k & 1) r = r * x % P;
	}
	return r;
}

signed main() {
	s[1][1] = 1;
	for (int i = 2; i < N; i ++) {
		for (int j = 1; j <= i; j ++) {
			s[i][j] = (s[i - 1][j - 1] + j * s[i - 1][j]) % P;
		}
	}
	for (int T = read(); T --;) {
		n = read(), m = read(), k = read(); int res = 0, x = (m + 1) / 2, inv = qow(m, P - 2);
		for (int i = 1, K = x * qow(m, n - 1) % P * n % P; i <= min(n, k); i ++, K = K * x % P * inv % P * (n - i + 1) % P) res = (res + s[k][i] * K) % P;
		printf("%lld\n", res);
	}
	return 0;
}

ARC137D

link

求对于长度为 $n$ 的序列 $a$ 对于每个 $1\le k \le m$ 求进行 $k$ 次操作后的 $a_n$。

一次操作为令 $a_i=\oplus _{j=1}^n a_j$。

$1 \le n,m \le 10^6$，$0 \le a_i < 2^{30}$。

将每次操作后的 $a$ 写成一行排成一个矩阵 $A$，考虑 $A_{0,i}$ 对 $A_{k,n}$ 的贡献。

经典问题，贡献是 $C_{k}^{n-i+k}$，因为是异或考虑这个东西的奇偶性。

Lucas 定理的推论：$C_k^{n-i+k}$ 是奇数当且仅当 $k$ 是 $n-i+k$ 的二进制子集。

因为 $k$ 是 $n-i+k$ 的二进制子集，那么 $k$ 和 $n-i$ 在二进制下是互斥的。高维前缀和即可。

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define M 21
#define N (1 << 21)
int n, m, a[N], f[N];

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; i ++) {
		a[i] = read(), f[n - i] ^= a[i];
	}
	for (int i = 0; i <= 20; i ++) {
		for (int j = 0; j < 1 << 20; j ++) {
			if (j >> i & 1) f[j] ^= f[j ^ (1 << i)];
		}
	}
	for (int i = 0; i < m; i ++) {
		printf("%d ", f[((1 << 20) - 1) ^ i]);
	}
	puts("");
	return 0;
}