排列数：\(A_n^m = n \times (n-1) \times \cdots \times (n-m+1) = \dfrac{n!}{(n-m)!}\)
组合数：\(C_n^m = \dfrac{A_n^m}{m!} = \dfrac{n!}{m!(n-m)!}\)
组合数与杨辉三角：\(C_n^m = C_{n-1}^{m-1} + C_{n-1,m}\)，特殊地，\(C_0^0 = 1, C_i^0 = i\)
组合数常用等式：\(C_n^m = C_n^{n-m}, \ \sum \limits_{i=0}^n C_n^i = 2^n\)
当 \(n,m\) 较小（允许 \(O(nm)\) 做法），模数不一定是质数时，可以使杨辉三角递推计算组合数。
当 \(n,m\) 较大但比模数小（只允许 \(O(n)\) 或 \(O(n \log n)\) 做法）且模数是质数时，可以使用杨辉三角递推计算组合数。
当 \(m\) 很小时，可以用 \(\dfrac{n \times (n-1) \times \cdots \times (n-m+1)}{m!}\) 暴力乘除（如果需要取模且模数是质数，除法用乘以逆元替代）。
\(t\) 组数据，\(k\) 都是相同的，所以可以预处理出所有 \(n,m \le 2000\) 组合数 \(\bmod k\) 的结果，本题的 \(k\) 不一定是质数，所以用杨辉三角递推预处理。
为了快速求出一组数据的答案，可以令 \(a_{i,j}\) 表示 \(C_i^j \bmod k\) 是否为 \(0\)，特殊地，如果 \(i \lt j\)，则 \(a_{i,j}=0\)。
对 \(a\) 数组做二维前缀和，单组数据求解的时间复杂度就是 \(O(1)\) 了。
总的时间复杂度为 \(O(nm+t)\)。
#include <cstdio>
const int N = 2005;
int c[N][N], a[N][N];
int main()
{
int t, k; scanf("%d%d", &t, &k);
for (int i = 1; i <= 2000; i++) {
c[i][0] = 1; a[i][0] = a[i - 1][0];
for (int j = 1; j < i; j++) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + (c[i][j] == 0);
}
c[i][i] = 1;
for (int j = i; j <= 2000; j++) a[i][j] = a[i][j - 1];
}
for (int i = 1; i <= t; i++) {
int n, m; scanf("%d%d", &n, &m);
printf("%d\n", a[n][m]);
}
return 0;
}
因为模数 \(p\) 是质数，且 \(n,m\) 均比模数小，可以用 \(C_n^m = \dfrac{n!}{m!(n-m)!}\) 求解。
预处理阶乘数组，\(f_i\) 表示 \(i! \bmod p\)，阶乘逆元数组，\(g_i\) 表示 \(i!\) 的乘法逆元。
预处理阶乘逆元时，可以先求 \(f_n\) 的逆元，再倒着求每个阶乘的逆元，\(g_i = g_{i+1} \times (i+1) \bmod p\)，这样求所有逆元的时间复杂度是线性的。
每次询问的答案就是 \(f_n \times g_m \times g_{n-m}\)，注意取模。
总时间复杂度为 \(O(N+T)\)。
#include <cstdio>
const int N = 5000005;
const int MOD = 998244353;
int f[N], g[N];
int qpow(int x, int y) {
int res = 1;
while (y > 0) {
if (y & 1) res = 1ll * res * x % MOD;
x = 1ll * x * x % MOD;
y >>= 1;
}
return res;
}
void init(int n) {
f[0] = g[0] = 1;
for (int i = 1; i <= n; i++) f[i] = 1ll * f[i - 1] * i % MOD;
g[n] = qpow(f[n], MOD - 2);
for (int i = n - 1; i > 0; i--) g[i] = 1ll * g[i + 1] * (i + 1) % MOD;
}
int main()
{
int t, maxn;
scanf("%d%d", &t, &maxn);
init(maxn);
int ans = 0;
for (int i = 1; i <= t; i++) {
int n, m; scanf("%d%d", &n, &m);
int res = 1ll * f[n] * g[m] % MOD * g[n - m] % MOD;
ans ^= res;
}
printf("%d\n", ans);
return 0;
}
\((x+y)^n = \overbrace{(x+y) \times (x+y) \times \cdots \times (x+y)}^\text{共 n 项} = C_n^0 x^n y^0 + C_n^1 x^{n-1}y^1 + \cdots + C_n^r x^{n-r}y^r + \cdots + C_n^n x^0 y^n\)，对于 \(C_n^r x^{n-r} y^r\) 这一项来说，相当于有 \(r\) 个 \((x+y)\) 提供了 \(x\)，有 \(n-r\) 个 \((x+y)\) 提供了 \(y\)。
\((1+(-1))^n = C_n^0 (-1)^0 + C_n^1 (-1)^1 + \cdots = -C_n^0 + C_n^1 - C_n^2 + C_n^3 - \cdots = 0\)，所以 \(\sum C_n^{奇数} = \sum C_n^{偶数} = 2^{n-1}\)。
\((1+2)^n = \sum \limits_{k=0}^n \binom{n}{k} 1^{n-k} \cdot 2^k = \sum\limits_{k=0}^n \binom{n}{k} 2^k = 3^n\)
把括号展开再合并同类项，\(x^ny^m\) 这一项相当于有 \(n\) 个括号选了 \(ax\) 这一项，其它括号选了 \(by\) 这一项，因此其系数为 \(C_k^n \times a^n \times b^m\)。
本题这个组合数，可以用杨辉三角递推，也可以选择预处理阶乘和阶乘逆元来做。
#include <cstdio>
#include <vector>
using std::vector;
const int MOD = 10007;
int main()
{
int a, b, k, n, m;
scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
int ans = 1;
for (int i = 1; i <= n; i++) ans = 1ll * ans * a % MOD;
for (int i = 1; i <= m; i++) ans = 1ll * ans * b % MOD;
vector<vector<int>> c(k + 1, vector<int>(n + 1));
for (int i = 1; i <= k; i++) {
c[i][0] = 1;
if (i <= n) c[i][i] = 1;
for (int j = 1; j < i && j <= n; j++)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD;
}
ans = 1ll * ans * c[k][n] % MOD;
printf("%d\n", ans);
return 0;
}
对二进制下每一位分别讨论。
枚举当前位，假设有 \(k\) 个数的二进制在当前位上取 \(1\)。
显然当前位为 \(0\) 的数取不取无所谓，当且仅当选取的子集中有奇数个 \(1\) 的数才对答案有贡献。
\((C_k^1 + C_k^3 + \cdots) \times 2^{n-k} = 2^{k-1+n-k} = 2^{n-1}\)，也就是说只要这些数在第 \(i\) 位上有 \(1\)，就会产生 \(2^{n-i} \times 2^i\) 的贡献。
#include <cstdio>
#include <vector>
using std::vector;
const int MOD = 998244353;
void solve() {
int n; scanf("%d", &n);
vector<int> v(n + 1);
int num = 0, p = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &v[i]); num |= v[i];
if (i > 1) p = 1ll * p * 2 % MOD;
}
int i = 0, ans = 0;
while (num > 0) {
if (num & 1) ans += (1 << i);
num >>= 1; i++;
}
ans = 1ll * ans * p % MOD;
printf("%d\n", ans);
}
int main()
{
int t; scanf("%d", &t);
for (int i = 1; i <= t; i++) solve();
return 0;
}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。