毅毅：统计不是数学（断章取义 ed）。故删掉了数学标签。 其实并没有。
A. 二分图染色
http://222.180.160.110:61235/contest/6181/problem/1
首先只看红色。显然一个左部点最多只能用红边连接一个右部点，反之同理。把左部点视为下标，其用红边相连的右部点视为值，则一个合法的方案为 \(n\) 的只保留一部分元素的排列。显然为 \(f(n)=\sum\limits_{i=0}^nC_n^i\cdot A_n^i\)。
再加上蓝色，\(f^2(n)\) 会给一条边涂两种颜色，故钦定有两种颜色的边数，容斥得到 \(\sum\limits_{i=0}^n(-1)^i\cdot C_n^i\cdot A_n^i\cdot f^2(n-i)\)。发现 \(f\) 的计算可能需要优化一下。考虑已经知道 \(f(n-1)\)，此时对于新增的第 \(n\) 对点：
- 任意连边（显然两个当中只能有一个点发出边），共有 \(2n-1\) 种方案，因为 \((n, n)\) 会被算重。
- 不连，共 \(1\) 种方案。
- 发现 1 中可能连到已经有连边的点上了，新边的目的地有 \(n-1\) 个选项，目的地原本连接的点也有 \(n-1\) 个选项，去掉两边共 \(4\) 个点，非法的即为 \((n-1)^2\cdot f(n-2)\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> f(n + 1), fac(n + 1), inv(n + 1);
f[0] = 1ll, f[1] = 2ll;
fac[0] = 1ll, fac[1] = 1ll, inv[0] = 1ll;
for (int i = 2; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
f[i] = (f[i - 1] * 2 * i % mod + mod - f[i - 2] * (i - 1) % mod * (i - 1) % mod) % mod;
}
auto qkp = [](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
auto A = [&](int n, int m) {
return fac[n] * inv[n - m] % mod;
};
long long res = 0ll;
for (int i = 0, k = 1; i <= n; ++i, k = mod - k)
(res += k * C(n, i) % mod * A(n, i) % mod * f[n - i] % mod * f[n - i]) %= mod;
std::cout << res << '\n';
return 0;
}B. 七选五
http://222.180.160.110:61235/contest/6181/problem/2
首先 \(p\) 固定，钦定有 \(x\) 个数相等，有 \(C_k^x\) 个方案，剩下的就是从 \(n-x\) 个元素里选出 \(k-x\) 个来错排，考虑钦定相同的个数来容斥：
\[ \sum_{i=0}^{k-x}(-1)^i\cdot C_{k-x}^i\cdot A_{n-x-i}^{k-x-i} \]
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k, x;
std::cin >> n >> k >> x;
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = 1ll, fac[1] = 1ll, inv[0] = 1ll;
for (int i = 2; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
auto A = [&](int n, int m) {
return fac[n] * inv[n - m] % mod;
};
long long res = C(k, x), sum = 0ll;
for (int i = 0, p = 1; i <= k - x; ++i, p = mod - p)
(sum += p * C(k - x, i) % mod * A(n - x - i, k - x - i) % mod) %= mod;
std::cout << res * sum % mod << '\n';
return 0;
}D. 硬币购物
http://222.180.160.110:61235/contest/6181/problem/4
每次多重背包会超时，考虑用钦定每种硬币是否超额来容斥。令 \(f_s\) 表示凑出 \(s\) 的方案数（完全背包），那么 \(f_{s-c_1\times (d_1 + 1)}\) 就表示钦定第 1 种硬币超额时凑出 \(s\) 的方案数，以此类推。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int c[4], T, m = 1e5;
std::vector<long long> f(m + 1);
f[0] = 1;
for (int i = 0; i < 4; ++i) {
std::cin >> c[i];
for (int j = c[i]; j <= m; ++j)
f[j] += f[j - c[i]];
}
std::cin >> T;
for (int d[4], m; T--; ) {
for (int i = 0; i < 4; ++i)
std::cin >> d[i];
std::cin >> m;
long long res = 0ll;
for (int i = 0; i < (1 << 4); ++i) {
int s = m;
for (int j = 0; j < 4; ++j)
if ((i >> j) & 1)
s -= (d[j] + 1) * c[j];
if (s >= 0) {
int k = (__builtin_popcount(i) & 1) ? -1 : 1;
res += k * f[s];
}
}
std::cout << res << '\n';
}
return 0;
}E. Distinct Multiples
http://222.180.160.110:61235/contest/6181/problem/5
推式子题。题意转化为，给定 \(n\) 个位置可选的值集合，要求任意两个位置值不等，问方案数。
如果把两个位置取等视作在团上选中边，那么有朴素做法钦定选边的集合 \(S\) 然后容斥，考虑它们构成的连通块 \(\{s\} \subseteq S\)，有 \(res=\sum\limits_{S\subseteq V}(-1)^{|S|}\cdot \prod\limits_{s_i} \left\lfloor \frac m{\operatorname{lcm} s_i} \right\rfloor\)。
有个很神奇的操作是把 \(S\) 丢掉，直接枚举 \(\{s\}\) 尝试子集 DP。有：\(res=\sum\limits_{\{s\}}\prod\limits_s f(s)\cdot\left\lfloor \frac m{\operatorname{lcm} s} \right\rfloor\)。其中 \(f(s)\) 表示选取一个 \(s\) 的导出子图的容斥系数之和，其中次数为导出子图中边数。
怎么把 \(f\) 算出来呢？容易发现其值只与 \(|s|\) 有关，考虑钦定与 \(1\) 连通的点数容斥，则有：
\[ f(n)=\sum\limits_{i=0}^{n - 1} (-1)^i \times C_{n-1}^{i-1} \times f(i) \cdot \sum_{j=0}^{m\gets i\times (i-1)\div 2} (-1)^j\cdot C_m^j \]
我们知道，二项式定理取 \(a=1, b = -1\) 有 \(0^m=[m=0]=\sum_{j=0}^m(-1)^j\cdot C_m^j\)，代入得：
\[ \begin{aligned} f(n)&=\sum\limits_{i=0}^{n - 1} (-1)^i \times C_{n-1}^{n-i-1} \times f(n-i)\cdot [m=0\iff i=1]\\ &=(1 - n)\cdot f(n-1) \end{aligned} \]
然后就能线性求出。再用一个子集 DP，为了保证顺序枚举最小的未被确定的点所在连通块进行转移。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, l;
long long m;
std::cin >> n >> m, l = 1 << n;
std::vector<long long> d(n), f(n + 1), dp(l), g(l);
f[1] = 1ll;
for (int i = 1; i <= n; ++i) {
std::cin >> d[i - 1];
if (i >= 2)
f[i] = (1 + mod - i) * f[i - 1] % mod;
// printf("f[%d] = %lld\n", i, f[i]);
}
for (int i = 0; i < l; ++i) {
long long now = 1ll;
for (int j = 0; j < n; ++j)
if ((i >> j) & 1) {
if (now / std::__gcd(now, d[j]) > m / d[j])
goto nosol;
now = now / std::__gcd(now, d[j]) * d[j];
}
g[i] = (m / now) % mod;
// printf("lcm = %lld, g[%d] = %lld\n", now, i, g[i]);
nosol: ;
}
dp[0] = 1ll;
auto lowbit = [](int x) {
return x & -x;
};
for (int i = 1; i < l; ++i) {
int to = std::__lg(lowbit(i));
for (int j = i; j; j = (j - 1) & i)
if ((j >> to) & 1)
(dp[i] += dp[i ^ j] * f[__builtin_popcount(j)] % mod * g[j] % mod) %= mod;
}
std::cout << dp[l - 1] << '\n';
return 0;
}F. Permutation
http://222.180.160.110:61235/contest/6181/problem/6
如果全是 <，方案数为 \(1\)。
现在把其中一些 < 变成 ?，比如 <<??<?<<<< 的方案数，太好了是多重集排列，我们没救了 显然被 < 连接起来的一段元素只有一种排列方式，所以可以视为多重集排列，方案数为 \(\dfrac {11!}{3!\times 2!\times 5!}\)。
似乎只需要枚举把 > 变成 < 或 = 的 \(2^k\) 种情况再计算就可以了，可惜 \(k\) 有点大。但我们发现它在一定程度上是没有后效性的，比如 <<??< 和 <<?<<，前面的 << 不会对后面的内容带来影响。
故令 \(f_i\) 表示对于前 \(i\) 个元素的方案数，枚举最后一个被钦定为 ? 的 > \(j\)（即 \([j + 1, i-1]\) 间的 > 都被替换为 <），带上容斥系数，有 \(f_i=\sum\limits_{s_j=\texttt{'>'}}(-1)^{cnt_\texttt{'>'}[j + 1, i - 1]}\times f_j\times\dfrac1{(i-j)!}\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n;
std::cin >> n;
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = 1ll, inv[0] = 1ll;
for (int i = 1; i <= n; ++i)
fac[i] = fac[i - 1] * i % mod;
auto qkp = [](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
std::vector<char> s(n + 1);
for (int i = 1; i <= n; ++i)
std::cin >> s[i];
std::vector<long long> f(n + 1);
s[0] = '>', f[0] = 1ll;
for (int i = 1; i <= n; ++i) {
int cnt = 0;
for (int j = i - 1; ~j; --j)
if (s[j] == '>') {
long long k = (cnt & 1) ? mod - 1 : 1;
(k *= f[j]) %= mod, (k *= inv[i - j]) %= mod;
(f[i] += k) %= mod;
++cnt;
}
// printf("f[%d] = %lld\n", i, f[i]);
}
std::cout << f[n] * fac[n] % mod << '\n';
return 0;
}忳郁邑余侘傺兮，余独穷困乎此时也。
H. ~K Perm Counting
http://222.180.160.110:61235/contest/6181/problem/8
考虑钦定令几个元素不满足条件进行容斥，即答案为 \(\sum\limits_{i=0}^n (-1)^i\cdot f(i)\)。但我们发现 \([n-k,n+k]\) 都有两个不能选的值，直接取 \(f(i)=\prod 2\) 肯定会选到相同值，一个自然（？）的想法是再容斥一遍，可惜手玩一下发现似乎容不动。考虑把玩意儿拍在棋盘上：
其中 \(\times\) 是非法格子，边是非法格子间的不同选关系，同颜色的边隶属同一条链。容易发现如果棋盘继续扩大，这些链还会继续延长。
会发现这些链互不干扰，就是说我选了这条链上的某个点和链外的点没有任何关系（显然）。把这些链首尾相连拼起来，要做的就是拼接处可以选相邻，其余位置不能选相邻，选出来 \(i\) 个的方案数。提前预处理出来整个序列，令 \(tag_j\) 表示 \(j\) 是否能和 \(j-1\) 同选，设 \(dp_{j,i,0/1}\) 表示 DP 到了 \(j\)，已经选了 \(i\) 个数，第 \(j\) 个元素（不）选的方案数，那么有：
\[ dp_{j,i,0} = dp_{j - 1, i, 0} + dp_{j-1, i, 1}\\ dp_{j,i,1} = \begin{cases} dp_{j-1, i - 1, 1} + dp_{j-1,i - 1,0}&tag_j=1 \\ dp_{j-1,i,0}&\text{otherwise} \end{cases} \]
大力 DP 即可。\(f(i)\) 即为 \((n-i)!\times (dp_{m, i, 0} + dp_{m, i, 1})\)，其中 \(m\) 为总链长。
注意不滚动可能会 MLE 
#include <bits/stdc++.h>
const int mod = 924844033;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
std::vector<int> tag(1);
std::vector<long long> fac(n + 1);
std::vector<std::vector<int> > vis(n + 1, std::vector<int> (n + 1));
auto calc = [&](int i, int j, int s) {
tag.push_back(1);
for (; ; s ^= 1) {
// printf("(%d, %d) ", i, j);
vis[i][j] = 1;
if (!s) {
i = j + k;
if (i <= n)
tag.push_back(0);
else
break;
}
else {
j = i + k;
if (j <= n)
tag.push_back(0);
else
break;
}
}
// puts("");
return;
};
fac[0] = 1ll;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
int j = i - k;
if (j >= 1 && !vis[i][j])
calc(i, j, 1);
j = i + k;
if (j <= n && !vis[i][j])
calc(i, j, 0);
}
int m = (int)tag.size() - 1;
// printf("m = %d\n", m);
std::vector<std::vector<std::vector<long long> > > dp(2, std::vector<std::vector<long long> > (n + 1, std::vector<long long> (2)));
dp[0][0][0] = 1ll;
for (int j = 1, now = 1; j <= m; ++j, now ^= 1) {
for (int i = 0; i <= n && i <= j; ++i) {
dp[now][i][0] = dp[!now][i][0];
dp[now][i][1] = 0ll;
if (i) {
(dp[now][i][0] += dp[!now][i][1]) %= mod;
dp[now][i][1] = dp[!now][i - 1][0];
if (tag[j]) {
(dp[now][i][1] += dp[!now][i - 1][1]) %= mod;
// assert(0);
}
}
// printf("dp[%d][%d] = %lld / %lld\n", j, i, dp[j][i][0], dp[j][i][1]);
}
}
long long res = 0ll;
for (int i = 0, p = 1; i <= n; ++i, p = mod - p)
(res += p * fac[n - i] % mod * (dp[m & 1][i][0] + dp[m & 1][i][1]) % mod) %= mod;
std::cout << res << '\n';
return 0;
}A - Positions in Permutations
https://codeforces.com/problemset/problem/285/E
（看向上一题）这照片是你吗？
在上一题的基础上，令 \(k=1\)。但是有个小小的问题——所求的「至少」不为 \(0\)，无法简单容斥。具体地，如果一个排列一共有 \(p\) 个非法排列，那么它会被 \(f(i)\) 统计 \(C_p^i\) 次。令 \(g(p)\) 表示非法格子数恰好为 \(p\) 的排列的真实数量，则 \(f(i)=\sum\limits_{j=i}^n C_j^i\cdot g(j)\)，二项式反演即可得到真实值 \(g(m)=\sum\limits_{j=m}^n (-1)^{j-m}\cdot C_j^m\cdot f(j)\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k;
std::cin >> n >> k;
std::vector<int> tag(1);
std::vector<long long> fac(n + 1), inv(n + 1);
std::vector<std::vector<int> > vis(n + 1, std::vector<int> (n + 1));
auto calc = [&](int i, int j, int s) {
tag.push_back(1);
for (; i <= n && j <= n; s ^= 1) {
vis[i][j] = 1;
if (!s) {
i = j + 1;
if (i <= n)
tag.push_back(0);
}
else {
j = i + 1;
if (j <= n)
tag.push_back(0);
}
}
return;
};
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
fac[0] = 1ll, inv[0] = 1ll;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
int j = i - 1;
if (j >= 1 && !vis[i][j])
calc(i, j, 1);
j = i + 1;
if (j <= n && !vis[i][j])
calc(i, j, 0);
}
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
int m = (int)tag.size() - 1;
std::vector<std::vector<std::vector<long long> > > dp(2, std::vector<std::vector<long long> > (n + 1, std::vector<long long> (2)));
dp[0][0][0] = 1ll;
for (int j = 1, now = 1; j <= m; ++j, now ^= 1) {
for (int i = 0; i <= n && i <= j; ++i) {
dp[now][i][0] = dp[!now][i][0];
dp[now][i][1] = 0ll;
if (i) {
(dp[now][i][0] += dp[!now][i][1]) %= mod;
dp[now][i][1] = dp[!now][i - 1][0];
if (tag[j])
(dp[now][i][1] += dp[!now][i - 1][1]) %= mod;
}
}
}
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
long long res = 0ll;
for (int i = k, p = 1; i <= n; ++i, p = mod - p) {
// printf("%d: %lld\n", i, C(i, k) * fac[n - i] % mod * (dp[m & 1][i][0] + dp[m & 1][i][1]) % mod);
(res += p * C(i, k) % mod * fac[n - i] % mod * (dp[m & 1][i][0] + dp[m & 1][i][1]) % mod) %= mod;
}
std::cout << res << '\n';
return 0;
}D - All Pairs Similarity P
https://www.luogu.com.cn/problem/P11458
省流：求 \(\forall\,i,f_i=\sum\limits_{j=1}^n \dfrac{|a_i\cap a_j|}{|a_i\cup a_j|}\)。
首先分离常数，有：
\[ \begin{aligned} f_i&=\sum\limits_{j=1}^n \dfrac{|a_i\cap a_j|}{|a_i\cup a_j|}\\ &=\sum_{j=1}^n\dfrac {|a_i|+|a_j|-|a_i\cup a_j|}{|a_i\cup a_j|}\\ &=\sum_{j=1}^n \dfrac {|a_i|+|a_j|}{|a_i\cup a_j|}-1 \end{aligned} \]
尽量把分子变得更简：
\[ \begin{aligned} f_i&=\sum_{j=1}^n \dfrac {|a_i|+|a_j|}{|a_i\cup a_j|}-1\\ &=|a_i|\cdot\left(\sum_{j=1}^n\dfrac 1{|a_i\cup a_j|}\right)-n+\sum_{j=1}^n \dfrac {|a_j|}{|a_i\cup a_j|} \end{aligned} \]
问题转化为求解 \(\sum\limits_{j=1}^n\dfrac 1{|a_i\cup a_j|}\) 和 \(\sum\limits_{j=1}^n\dfrac {|a_j|}{|a_i\cup a_j|}\)，以 \(*=\sum\limits_{j=1}^n\dfrac 1{|a_i\cup a_j|}\) 为例。令 \(b_i\) 为 \(a_i\) 补集，则：
\[ \begin{aligned} *&=\sum\limits_{j=1}^n\dfrac 1{|a_i\cup a_j|}\\ &=\sum_{j=1}^n\dfrac 1{k-|b_i\cap b_j|} \end{aligned} \]
为什么要做这个转换呢？相比起并集运算，交集运算有着优秀的性质：\(s\subseteq(b_i\cap b_j)\iff s\subseteq b_i\land s\subseteq b_j\)，直接取或当然也有相似的性质，但是太烧脑了。
基于这个性质，我们有一个想法：对于所有 \(j\)，在 \(\forall \, s\subseteq b_j\) 处放置 \(\dfrac 1{k-|s|}\) 的贡献；对于 \(i\)，将 \(\forall \, s\subseteq b_i\) 处的贡献求和。但是这样肯定会拿到很多我们不想要的贡献，例如 \(\forall \, s\subset (b_i\cap b_j)\)。
考虑精细布置贡献——构造 \(g(|s|)\) 满足 \(\sum\limits_{j=1}^n\sum\limits_{s\subseteq b_j}g(|s|)=*\)。
这里可以二项式反演得到 \(g\)，具体地，令 \(F(|S|)=\dfrac 1{k-|S|}=\sum\limits_{s\subseteq S}g(|s|)=\sum\limits_{j=0}^{|S|} C_{|S|}^j g(j)\)，则 \(g(i)=\sum\limits_{j=0}^iC_i^j\cdot \dfrac {(-1)^{i-j}}{k-j}\)。
再令 \(h(s)=\sum\limits_{b_j\supseteq s}g(|s|)=g(|s|)\cdot \sum\limits_{b_j\supseteq s}1\)，那么 \(h\) 就是高维后缀和。我们正在做的事情就是求解 \(*=\sum\limits_{s\subseteq b_i}h(s)\)，这就又是一个高维前缀和了。
对于 \(\sum\limits_{j=1}^n\dfrac {|a_j|}{|a_i\cup a_j|}\) 呢，令 \(h(s)=\sum\limits_{b_j\supseteq s}g(|s|)\cdot {\color{red}{|a_j|}} = g(|s|) \cdot \sum\limits_{b_j\supseteq s} \color{red}{k - |b_j|}\)，改变高维后缀和求和对象即可。
复杂度就是 \(O(n+k\cdot 2^k)\)，其中 \(k\cdot 2^k\) 来自整体高维前 / 后缀和，\(n\cdot k\) 来自枚举 \(i\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, k, l;
std::cin >> n >> k, l = 1 << k;
std::vector<int> a(n + 1), b(n + 1), cnt(l);
for (int i = 1; i <= n; ++i) {
std::cin >> a[i], b[i] = (l - 1) ^ a[i];
++cnt[b[i]];
}
std::vector<long long> g(k + 1), fac(k + 1);
auto qkp = [&](long long x, int y = mod - 2) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto C = [&](int n, int m) {
return fac[n] * qkp(fac[n - m]) % mod * qkp(fac[m]) % mod;
};
fac[0] = 1ll;
for (int i = 1; i <= k; ++i)
fac[i] = fac[i - 1] * i % mod;
for (int i = 0; i <= k; ++i) {
for (int j = 0, p = (i & 1) ? mod - 1 : 1; j <= i; ++j, p = mod - p)
(g[i] += C(i, j) * p % mod * qkp(k - j) % mod) %= mod;
// printf("g[%d] = %lld\n", i, g[i]);
}
// for (int i = 0; i <= k; ++i) {
// long long F = 0ll;
// for (int j = 0; j <= i; ++j)
// (F += C(i, j) * g[j] % mod) %= mod;
// printf("%d: %lld / %lld\n", i, F, qkp(k - i));
// }
std::vector<long long> h(l);
std::copy(cnt.begin(), cnt.end(), h.begin());
for (int i = 0; i < k; ++i)
for (int j = l - 1; ~j; --j)
if (!((j >> i) & 1))
(h[j] += h[j ^ (1 << i)]) %= mod;
auto f1(h);
for (int i = 0; i < l; ++i)
(f1[i] *= g[__builtin_popcount(i)]) %= mod;
for (int i = 0; i < k; ++i)
for (int j = 0; j < l; ++j)
if ((j >> i) & 1)
(f1[j] += f1[j ^ (1 << i)]) %= mod;
for (int i = 0; i < l; ++i)
h[i] = cnt[i] * (k - __builtin_popcount(i));
for (int i = 0; i < k; ++i)
for (int j = l - 1; ~j; --j)
if (!((j >> i) & 1))
(h[j] += h[j ^ (1 << i)]) %= mod;
auto f2(h);
for (int i = 0; i < l; ++i)
(f2[i] *= g[__builtin_popcount(i)]) %= mod;
for (int i = 0; i < k; ++i)
for (int j = 0; j < l; ++j)
if ((j >> i) & 1)
(f2[j] += f2[j ^ (1 << i)]) %= mod;
for (int i = 1; i <= n; ++i) {
// fprintf(stderr, "%d: %d * %lld - %d + %lld\n", i, __builtin_popcount(a[i]), f1[b[i]], n, f2[b[i]]);
std::cout << (__builtin_popcount(a[i]) * f1[b[i]] % mod + mod - n + f2[b[i]]) % mod << '\n';
}
return 0;
}E - Prefix XORs
https://atcoder.jp/contests/arc137/tasks/arc137_d
省流：做 \(k\) 次前缀和，\(k=1,2,\cdots,m\)，分别询问：令 \(x_i\gets a_i\) 对 \(s_n\) 的贡献次数，则 \(\sum a_i\cdot (x_i\bmod 2)\)？
对于 \(a_p\)，容易发现第一轮其对任意 \(s_q\) 有 \(1\) 次贡献，拉开来就是常数列；第二轮有 \((q-p+1)\) 次贡献，是公差为 \(1\) 的等差数列；第三轮是类三角形数——至此，肯定和组合数有关了。手玩可以发现第 \(k\) 轮 \(a_p\) 对 \(s_n\) 的贡献为 \(C_{n-p+(k-2)}^{n-p}\)，尽量令其中一个不动，得到 \(C_{n-p+(k-2)}^{k-1}\)。
但是我们发现直接枚举每轮每个数会起飞，而且模数为 \(2\) 似乎只能 Lucas（再带个 \(\log\)），怎么办呢？
那就 Lucas 呗。由其观察容易发现 \(C_{n-p+(k-2)}^{k-2}\bmod2=1\) 当且仅当 \((k-2)\subseteq (n-p+k-2)\iff (k-2)\subseteq \complement_U(n-p)\)，故问题转化为高维后缀和，当然你也可以做一次 and-FWT，那么 \(res_k=\sum (C_{n-p+(k-2)}^{k-2}\bmod 2)\cdot a_p=S_{k-2}\)，其中 \(S\) 为高维后缀和，初值为 \(S_{\complement_u(n-i)}\gets a_i\)。
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, l, k;
std::cin >> n >> m, k = std::__lg(n + m) + 1, l = 1 << k;
std::vector<int> s(l);
for (int i = 1; i <= n; ++i)
std::cin >> s[l - 1 - (n - i)];
for (int i = 0; i < k; ++i)
for (int j = l - 1; ~j; --j)
if (!((j >> i) & 1))
s[j] ^= s[j ^ (1 << i)];
for (int i = 1; i <= m; ++i)
std::cout << s[i - 1] << ' ';
std::cout << '\n';
return 0;
}B - The Top Scorer
https://codeforces.com/problemset/problem/1096/E
鉴于每种方案等概率（翻译没说，但原题面有提到），考虑计算小明能够取胜的方案数，再对总方案数做除法。先枚举最高分 \(k\ge r\)，再枚举包括小明在内恰有 \(c\ge 1\) 个人 拿到 \(k\) 分。但剩下的人呢？显然是不能插板随机分配的，因为存在 \(<k\) 的限制。
考虑容斥，钦定剩下的 \(p-c\) 个人中拿到 \(\ge k\) 分的人数后再可空地插板即可，则总方案数为：
\[ \sum_{k=r}^s\sum_{c=1}^p\dfrac {C_{p - 1}^{c-1}}c\cdot \sum_{i=0}^{p-c}C_{p-c}^i\cdot C_{s-k\cdot (c+i)+(p-c-1)}^{p-c-1} \]
其中分母上的 \(c\) 来源于等概率分配给最高分，虽然不是整数，但也代表着「小明获胜可行方案数」。最后将答案除上总方案数 \(C_{s-r+p-1}^{p-1}\) 即可。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int p, s, r;
std::cin >> p >> s >> r;
std::vector<long long> fac(s + p), inv(s + p);
fac[0] = inv[0] = 1ll;
for (int i = 1; i < s + p; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
auto qkp = [&](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv.back() = qkp(fac.back(), mod - 2);
for (int i = s + p - 2; i > 0; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
if (n == -1 && m == -1)
return 1ll;
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
auto res(0ll);
for (int k = r; k <= s; ++k)
for (int c = 1; c <= p; ++c)
if ((p - c) * (k - 1) + c * k >= s) {
auto t(0ll);
for (int i = 0, now = 1; i <= p - c && k * (c + i) <= s; ++i, now = mod - now)
(t += now * C(p - c, i) % mod * C(s - k * (c + i) + (p - c - 1), p - c - 1) % mod) %= mod;
(res += C(p - 1, c - 1) * qkp(c, mod - 2) % mod * t % mod) %= mod;
}
std::cout << res * qkp(C(s - r + p - 1, p - 1), mod - 2) % mod << '\n';
return 0;
}C - Sky Full of Stars
https://codeforces.com/problemset/problem/997/C
发现用 \(3^{n\times n}\) 减去任意一行一列不同色的方案就是答案。
考虑一元容斥，如令 \(f_i\) 表示至少 \(i\) 行 \(i\) 列同色的方案，但会发现 \(f_0\) 中包含 \(0\) 行 \(1\) 列同色等与预期不符的情况。受此启发考虑令 \(f_{i,j}\) 表示至少 \(i\) 行 \(j\) 列同色进行二元容斥。容易发现当 \(i\times j\ne 0\) 时，被选中的 \(i\) 行 \(j\) 列全部连通，应为同一种颜色；将它们挪到角落，可以发现未被选中的格子共有 \((n-i)\times (n-j)\) 个。故有：
\[ f_{i,j}=\begin{cases} C_n^j\times 3^j\times 3^{n\times(n - j)}&i=0\\ C_n^i\times 3^i\times 3^{n\times(n-i)}&j=0\\ C_n^i\times C_n^j\times 3\times 3^{(n-i)\times (n-j)}&\text{otherwise} \end{cases} \]
令 \(g_{i,j}\) 表示恰好 \(i\) 行 \(j\) 列同色的方案数，那么答案为 \(3^{n\times n}-g_{0,0}\)。二项式反演 / 容斥原理得 \(g_{0,0}=\sum\limits_{i=0}^n\sum\limits_{j=0}^n (-1)^{i+j}\cdot f_{i,j}\)。很惊讶地发现这是 \(O(n^2)\) 的！考虑优化。把 \(f_{1\to n,1\to n}\) 合并同类项，得到：
\[ \begin{aligned} g_{0, 0} &=\left[\sum_{j=0}^n (-1)^j\cdot f_{0,j}\right]+\sum_{i=1}^n (-1)^i\cdot f_{i,0}+\sum_{j=1}^n (-1)^{i+j}\cdot C_n^i\times C_n^j\times 3^{(n-i)\times (n-j)+1}\\ &=\left[\sum_{j=0}^n (-1)^j\cdot f_{0,j}\right]+\sum_{i=1}^n (-1)^i\cdot f_{i,0}+(-1)^i\cdot C_n^i\times 3^{n^2-n\times i+1}\times\sum_{j=1}^n (-1)^j\cdot C_n^j\times 3^{j\times(-n+i)}\\ &=\left[\sum_{j=0}^n (-1)^j\cdot f_{0,j}\right]+\sum_{i=1}^n (-1)^i\cdot f_{i,0}+(-1)^i\cdot C_n^i\times 3^{n^2-n\times i+1}\times\left[\left(\sum_{j=0}^n (-1)^j\cdot C_n^j\times (3^{-n+i})^j\right)-1\right]\\ &=\left[\sum_{j=0}^n (-1)^j\cdot f_{0,j}\right]+\sum_{i=1}^n (-1)^i\cdot f_{i,0}+(-1)^i\cdot C_n^i\times 3^{n^2-n\times i+1}\times\left[(-3^{-n+i}+1)^n-1\right] \end{aligned} \]
由此便可 \(O(n\log n)\) 计算。担心超时可以把所有 \(3^{-n+i}\) 和 \(3^{n\times i}\) 线性预处理出来，复杂度不会变就是了。
这里解释一下最后一步的二项式定理，非常遗憾地发现 \(-1\) 和 \(3^{-n+i}\) 都是 \(j\) 次的，没办法把二者相加减做二项式定理；但由于次数相同，这提示我们可以把 \(-1\) 乘到 \(3^{-n+i}\) 里去，给每一项配上 \(1^{n-k}\) 就可以做 \(-3^{n-i}\)（注意不是 \((-3)^{n-i}\)） 和 \(1\) 的二项式定理。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
long long n;
std::cin >> n;
std::vector<long long> fac(n + 1), inv(n + 1), invn(n + 1), invi(n + 1), powi(n + 1), pown(n + 1);
auto qkp = [&](long long x, long long y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
const long long pnn = qkp(3ll, n * n), pn = qkp(3ll, n);
fac[0] = inv[0] = invn[0] = invi[0] = powi[0] = pown[0] = 1ll;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
powi[i] = powi[i - 1] * 3 % mod;
pown[i] = pown[i - 1] * pn % mod;
}
inv[n] = qkp(fac[n], mod - 2);
invi[n] = qkp(powi[n], mod - 2);
invn[n] = qkp(pown[n], mod - 2);
for (int i = n - 1; i; --i) {
inv[i] = inv[i + 1] * (i + 1) % mod;
invi[i] = invi[i + 1] * 3 % mod;
invn[i] = invn[i + 1] * pn % mod;
}
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
long long g = 0ll;
auto f = [&](int i, int j) { // make sure (!i || !j)
if (i == 0 && j == 0)
return pnn;
else if (i == 0)
return C(n, j) * powi[j] % mod * pown[n - j] % mod;
return C(n, i) * powi[i] % mod * pown[n - i] % mod;
};
for (int j = 0, p = 1; j <= n; ++j, p = mod - p)
(g += p * f(0, j)) %= mod;
for (int i = 1, p = mod - 1; i <= n; ++i, p = mod - p)
(g += p * f(i, 0) % mod + p * C(n, i) % mod * pnn % mod * invn[i] % mod * 3 % mod * (qkp(mod - invi[n - i] + 1, n) + mod - 1) % mod) %= mod;
std::cout << (pnn + mod - g) % mod << '\n';
return 0;
}D - 去 M / NoM
https://www.luogu.com.cn/problem/P11316
假设 \(f(i)\) 为至少有 \(i\) 对不合法元素的方案数，则容斥得到答案 \(\sum\limits_{i=0}^n (-1)^i\cdot f(i)\)。考虑怎么计算 \(f(i)\)。
\(M\) 整除 \(dis(x, y) \iff (pos_x - pos_y)\bmod M=0\iff pos_x\equiv pos_y\pmod M\)。
考虑把关于 \(M\) 同余的位置放在一个组，也就是说需要让一对元素不能选同一组的位置。
考虑容斥，令 \(f(i)\) 表示至少有 \(i\) 对点选到一组的方案数，考虑怎么计算。假设我们要在第 \(k\) 组（size 为 \(s_k\)）中选出 \(x\) 对位置，实际上只需要选择 \(2x\) 个位置然后任意分配给这 \(x\) 对数，即 \(A_{s_k}^{2x}\)。设 \(dp_{i, j}\) 表示 DP 到第 \(i\) 个组，已经选了 \(j\) 对，那么有 \(dp_{i,j}=\sum\limits_{k=0}^jC_{n-(j - k)}^{j-k}\times dp_{i-1,j-k}\times A_{s_i}^{2k}\)。乍一看好像是 \(O(n^3)\) 的，但是别忘了 \(\sum s_i=2n\)，所以只有 \(O(n^2)\)。\(f(i)\) 即为 \(dp_{m,i}\times (2n-2i)!\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
std::vector<int> s(m + 1);
std::vector<long long> fac(2 * n + 1), inv(2 * n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= 2 * n; ++i)
++s[i % m + 1], fac[i] = fac[i - 1] * i % mod;
auto qkp = [](long long x, int y) {
auto res = 1ll;
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[2 * n] = qkp(fac[2 * n], mod - 2);
for (int i = 2 * n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto A = [&](int n, int m) {
return fac[n] * inv[n - m] % mod;
};
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
std::vector<std::vector<long long> > dp(m + 1, std::vector<long long> (n + 1));
dp[0][0] = 1ll;
for (int i = 1; i <= m; ++i)
for (int j = 0; j <= n; ++j) {
for (int k = 0; k <= j && 2 * k <= s[i]; ++k)
(dp[i][j] += C(n - (j - k), k) * dp[i - 1][j - k] % mod * A(s[i], 2 * k) % mod) %= mod;
// printf("s = %d, dp[%d][%d] = %lld\n", s[i], i, j, dp[i][j]);
}
long long res = 0ll;
for (int i = 0, p = 1; i <= n; ++i, p = mod - p)
(res += p * dp[m][i] % mod * fac[2 * n - 2 * i] % mod) %= mod;
std::cout << res << '\n';
return 0;
}E - 「KDOI-11」彩灯晚会
https://www.luogu.com.cn/problem/P11292
考虑 \({cnt_i}^2\) 的含义，即在所有颜色为 \(i\)、长度为 \(l\) 的链中有放回地选两次的方案数。
显然复杂度里是不能包含 \(k\) 的，所以放弃直接统计 \(cnt_i\) 的想法。显然每种颜色是等价的，考虑计算选择两条链可以给答案带来的贡献：答案的形式是个和式；对于两条同色链 \(p,q\)，假设颜色为 \(i\)，那么会对 \({cnt_i}^2\) 带来 \(k^{n-2l-|p\cap q|}\) 的贡献，对总答案带来 \(k^{n-2l-|p\cap q| + 1}\) 的贡献。
然而如果要枚举计算 \(|p\cap q|\) 就无法避免 \(O(n^5)\)，考虑更有潜力的方法：将问题转化为对于每个 \(x\)，求交集大小恰好为 \(x\) 的链对个数。然而「恰好」是不方便计算的——假如当前两链在 \(u\) 次重合，如果假设下一次在 \(v\) 次重合，就需要保证在 \(u,v\) 之间不能重合——这并不好操作。二项式反演将恰好转化为至少，则限制减弱。
令 \(f_{u,c,l_1,l_2}\) 表示 \(p,q\) 当前在 \(u\) 处重合，视野内的 \(p,q\) 长度为 \(l_1,l_2\)，至少已经重合了 \(c\) 次的方案数。预处理出走到 \(u\) 步数为 \(l_1,l_2\) 的方案数为初始值。枚举可能的后续重合点 \(v\)（满足 \(v\) 的拓扑序 \(>u\)）有 \(f_{v,c+1,l_1',l_2'}\gets f_{v,c+1,l_1',l_2'} + f_{u,c,l_1,l_2}\)。预处理出 \(u\to v\) 长度为 \(\Delta\) 的方案数（这是 \(O(n^3l)\) 的）优化转移，在算出 \(nex_{u,l}\) 表示从 \(u\) 出发走 \(l\) 步的方案数处理答案，则 \(F(i)=\sum_{u,l_1,l_2}f_{u,l_1,l_2}\cdot nex_{u,l-l_1}\cdot nex_{u,l-l_2}\)，枚举 \(u,c,l_1,l_2,v,l_1',l_2'\)，就可以达到优秀的 \(O(n^2l^5+n^3l)\)！简直是令人震撼
给出第一个优化：发现 \(l_1\) 和 \(l_2\) 的转移彼此不干扰，考虑建立一个临时数组 \(g\)，先从 \(f_u,c\) 转移 \(l_1\) 到 \(g\)，再从 \(g\) 转移 \(l_2\) 到 \(f_{v,c+1}\)，则复杂度降为 \(O(n^2l^4+n^3l)\)，仍不足以通过。
DP 过程上的优化已经万策尽，考虑从式子本身消元减少 DP 维度入手。令 \(h(i)\) 表示交集大小恰好恰好为 \(i\) 的方案数，则此时答案式为 \(\sum\limits_{i=0}^l k^{n-2l+i+1}\times h(i)\)。又 \(F(i)=\sum\limits_{j=i}^lC_j^i\cdot h(j)\)，二项式反演得：
\[ \begin{aligned} res&=\sum\limits_{i=0}^lk^{n-2l+i+1}\cdot \sum_{j=i}^l(-1)^{j-i}\cdot C_j^i\cdot F(j)\\ &=k^{n-2l+1}\cdot\sum_{j=0}^l \sum_{i=0}^j k^i\cdot (-1)^{j-i}\cdot C_j^i\cdot F(j)\\ &=k^{n-2l+1}\cdot \sum_{j=0}^l (k-1)^j\cdot F(j) \end{aligned} \]
注意这里利用了二项式反演的系数可以和交换求和顺序后的 \(i\) 次项（或 \(j-i\) 次项，参见 Sky Full of Stars 中最后一步的处理）组成二项式定理的特点，以便基于式子结构尽可能消元。
那么此时答案式已经和 \(c\) 无关，可以丢掉 \(c\) 这一维，和 \(c\) 有关的计算已经在转移时处理了。则 \(f_{v,l_1',l_2'}=\sum f_{u,l_1,l_2}\times (k-1)\)，复杂度降为 \(O(n^2l^3+n^3l)\)。
记得还要算上 \(F(0)\)，即任选一条合法链的方案数平方。
// 兄弟你好香
// 兄弟你是依托打分，我踏马吃吃吃吃吃
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("party3.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
using arr = std::vector<long long>;
using arrr = std::vector<arr>;
using arrrr = std::vector<arrr>;
int n, k, l, m;
std::cin >> n, std::cin >> n >> k >> l >> m;
std::vector<int> deg(n + 1), id;
std::vector<std::vector<std::pair<int, int> > > g(n + 1);
for (int x, y, c; m--; ) {
std::cin >> x >> y >> c;
++deg[y], g[x].emplace_back(y, c);
}
arrrr to(n + 1, arrr(n + 1, arr(l + 1)));
arrr pre(n + 1, arr(l + 1)), nex(n + 1, arr(l + 1));
{
std::queue<int> q;
for (int i = 1; i <= n; ++i)
if (!deg[i])
q.push(i);
for (int u; !q.empty(); ) {
u = q.front(), q.pop();
to[u][u][0] = 1ll, id.push_back(u);
for (auto i : id)
for (int j = 0; j <= l; ++j) {
(pre[u][j] += to[i][u][j]) %= mod;
// printf("to[%d][%d][%d] = %lld\n", i, u, j, to[i][u][j]);
}
// for (int j = 0; j <= l; ++j)
// printf("pre[%d][%d] = %lld\n", u, j, pre[u][j]);
for (auto [v, c] : g[u]) {
for (auto i : id)
for (int j = 1; j <= l; ++j)
(to[i][v][j] += to[i][u][j - 1] * c) %= mod;
if (!--deg[v])
q.push(v);
}
}
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
for (int i = 0; i <= l; ++i)
(nex[u][i] += to[u][v][i]) %= mod;
}
arrrr f(n + 1, arrr(l + 1, arr(l + 1)));
{
for (int i = 1; i <= n; ++i)
for (int l1 = 1; l1 <= l; ++l1)
for (int l2 = 1; l2 <= l; ++l2)
f[i][l1][l2] = pre[i][l1 - 1] * pre[i][l2 - 1] % mod * (k - 1) % mod;
for (auto i = 0; i < n; ++i) {
int u = id[i];
// for (int l1 = 1; l1 <= l; ++l1)
// for (int l2 = 1; l2 <= l; ++l2)
// printf("f[%d][%d][%d] = %lld\n", u, l1, l2, f[u][l1][l2]);
for (auto j = i + 1; j < n; ++j) {
arrr g(l + 1, arr(l + 1));
int v = id[j];
for (int l1 = 1; l1 < l; ++l1)
for (int _l1 = l1 + 1; _l1 <= l; ++_l1) {
auto K = to[u][v][_l1 - l1];
if (K)
for (int l2 = 1; l2 < l; ++l2)
(g[_l1][l2] += f[u][l1][l2] * K) %= mod;
}
for (int _l1 = 2; _l1 <= l; ++_l1)
for (int l2 = 1; l2 < l; ++l2)
if (g[_l1][l2])
for (int _l2 = l2 + 1; _l2 <= l; ++_l2)
(f[v][_l1][_l2] += g[_l1][l2] * to[u][v][_l2 - l2] % mod * (k - 1)) %= mod;
}
}
}
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto res(0ll);
for (int u = 1; u <= n; ++u)
for (int v = 1; v <= n; ++v)
(res += to[u][v][l - 1]) %= mod;
(res *= res) %= mod;
for (int u = 1; u <= n; ++u)
for (int l1 = 1; l1 <= l; ++l1)
for (int l2 = 1; l2 <= l; ++l2)
(res += f[u][l1][l2] * nex[u][l - l1] % mod * nex[u][l - l2] % mod) %= mod;
res = res % mod * (qkp(k, n + 1) * qkp(qkp(k, 2 * l), mod - 2) % mod) % mod;
std::cout << res << '\n';
return 0;
}G - 小星星
https://www.luogu.com.cn/problem/P3349
首先考虑比较暴力的做法，那么有 \(f_{i,j,S}\) 表示在 \(i\) 这个子树里面选了集合 \(S\)，且 \(i\) 的颜色为 \(j\) 的方案数，维数里之所以有 \(j\) 是为了满足连边限制。
然后树上子集 DP，发现是 \(O(n^4\cdot 2^n)\) 的，
CF785D Anton and School - 2
https://codeforces.com/problemset/problem/785/D
容易想到枚举每个 ( 作为分界点的情况，那么钦定当前枚举的 ( 是要选的。对于当前 (，若其左边（不含）的 ( 有 \(n\) 个而右边的 ) 有 \(m\) 个，枚举除了当前 ( 还要选 \(i\) 个 (，那么答案为 \(\sum_{i=0}C_n^{i-1}\cdot C_m^i\)。
发现这个形式可以范德蒙德卷积：\(\sum_{i=0}C_n^{i-1}\cdot C_m^i=\sum_{i=0}C_n^{n-i+1}\cdot C_m^i=C_{n+m}^{n+1}\)。
关于怎么记忆范德蒙德卷积，发现上下相加，也可以从组合意义记忆：在 \(n\) 个球中选出 \(k-i\) 个球，再从 \(m\) 个球中选出 \(i\) 个球的总方案就是从 \(n+m\) 个球中直接选出 \(k\) 个球的方案。
注意判断右侧没有 ) 的时候贡献为 \(0\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
std::string s;
std::cin >> s;
int n = s.length();
s = " " + s;
std::vector<int> cnt1(n + 1), cnt2(n + 1);
std::vector<long long> fac(n + 1), inv(n + 1);
fac[0] = inv[0] = 1ll;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
cnt1[i] = cnt1[i - 1] + (s[i] == '(');
}
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
cnt2[n] = (s[n] == ')');
for (int i = n - 1; i; --i) {
cnt2[i] = cnt2[i + 1] + (s[i] == ')');
inv[i] = inv[i + 1] * (i + 1) % mod;
}
long long res = 0ll;
auto C = [&](int n, int m) {
if (n < m)
return 0ll;
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
for (int i = 1; i <= n; ++i)
if (s[i] == '(')
(res += C(cnt1[i] + cnt2[i] - 1, cnt1[i])) %= mod;
std::cout << res << '\n';
return 0;
}CF1332E Height All the Same
https://codeforces.com/problemset/problem/1332/E
容易发现第一个操作是用来改变两个数奇偶性的；而第二个操作能在全图奇偶性相同的任何情况下达成要求。
注意到如果我们想同时仅改变任意两个数的奇偶性，可以在棋盘上任找一条路径一路使用操作一。只要某种奇偶性的元素个数共有偶数个，就能通过若干次操作一把它们全部变成另一种奇偶性。
令 \(K_1\) 为 \(L\sim R\) 中奇数的个数，\(K_2\) 为偶数，那么有：
\[ res=\sum_{i=0}^{nm} C_{nm}^i\times {K_1}^i\cdot {K_2}^{nm-i}\cdot [i\bmod 2=0] \]
我们发现这个东西和二项式定理简直像得不能再像了！但多了一个系数导致没办法省略枚举过程。如果进行变形呢？
\[ res=(K_1+K_2)^{nm}-\sum_{i=0}^{nm} C_{nm}^i\times {K_1}^i\cdot {K_2}^{nm-i}\cdot [i\bmod 2=1] \]
似乎依然没有出路！但这里有个神奇的操作：
\[ res=(-K_1+K_2)^{nm}+\sum_{i=0}^{nm} C_{nm}^i\times {K_1}^i\cdot {K_2}^i\cdot [i\bmod 2=1] \]
二式相加就可以消元，得到 \(2\cdot res=(K_1+K_2)^{nm}+(K_1-K_2)^{nm}\)。这启示我们二项式定理中的符号和奇偶性的深切联系。
如果你使用费马小定理对次数进行了处理，你可能需要注意次数可能为 \(\text{mod} -1\) 的倍数。
#include <bits/stdc++.h>
const int mod = 998244353;
const int inv2 = 499122177;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
long long n, m, l, r, k1, k2;
std::cin >> n >> m >> l >> r, k1 = (r - l + 1) / 2, k2 = (r - l + 1) - k1;
auto qkp = [](long long x, long long y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
if (n * m % 2)
std::cout << qkp(r - l + 1, n * m) << '\n';
else
std::cout << (qkp(r - l + 1, n * m) + qkp((k1 + mod - k2) % mod, n * m)) % mod * inv2 % mod << '\n';
return 0;
}A - 交错序列
https://www.luogu.com.cn/problem/P4456
容易想到把答案用二项式定理拆开：
\[ \begin{aligned} res&=\sum_y f_y\cdot y^b\cdot (n-y)^a\\ &=\sum_y f_y\cdot y^b\cdot \sum_{i=0}^a C_a^i\cdot n^i\cdot(-y)^{a-i}\\ &=\sum_y\sum_{i=0}^a f_y\cdot C_a^i\cdot n^i\cdot(-1)^{a-i}\cdot y^{a+b-i}\\ &=\sum_{i=0}^a C_a^i\cdot n^i\cdot(-1)^{a-i}\cdot \sum_y f_y\cdot y^{a+b-i}\\ \end{aligned} \]
然后发现后面那个 sigma 不太有办法求。一个比较优雅的方法是把 \(y^{a+b-i}\) 直接作为系数而非下标塞到 \(f\) 里去，即令 \(f_{i}\) 表示 \(\forall \,y\)，\(\sum y^i\) 之和。
具体地，令 \(dp_{n,i,0/1}\) 表示当前 DP 到第 \(n\) 位，要求幂次为 \(i\)，最后一位为 \(0/1\) 的答案。则显然有 \(dp_{n,i,0}=dp_{n-1,i,0}+dp_{n-1,i,1}\)。对于 \(dp_{n,i,1}\)，因为此时 \(\forall\, k,k\gets k+1\)，则 \((k+1)^i=\sum\limits_{j=0}^i C_i^j \cdot k^j\) 即 \(dp_{n,i,1}=\sum\limits_{j=0}^i C_i^j\cdot dp_{n-1,j,0}\)。发现 \(i,j\) 的范围是 \(90\)，很恐怖的事情是这是可以矩阵的。
就像我们都知道的那样，矩阵在加完之后再取模就会快很多……
#include <bits/stdc++.h>
int mod;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, a, b;
std::cin >> n >> a >> b >> mod;
std::vector<std::vector<long long> > C(a + b + 1, std::vector<long long>(a + b + 1));
for (int i = 0; i <= a + b; ++i) {
C[i][0] = 1ll;
for (int j = 1; j <= i; ++j)
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
}
struct mat {
int n, m;
std::vector<std::vector<long long> > a;
mat(int n, int m, bool flag = 0): n(n), m(m), a(n, std::vector<long long> (m)) {
if (flag)
for (int i = 0; i < n; ++i)
a[i][i] = 1ll;
return;
}
mat operator* (const mat &q) const {
mat res(n, q.m);
for (int i = 0; i < n; ++i)
for (int k = 0; k < q.m; ++k) {
for (int j = 0; j < m; ++j)
res.a[i][k] += a[i][j] * q.a[j][k];
res.a[i][k] %= mod;
}
return res;
}
mat operator^ (int q) const {
mat res(n, n, 1), x(*this);
for (; q; x = x * x, q >>= 1)
if (q & 1)
res = res * x;
return res;
}
} f(1, 2 * (a + b + 1)), op(2 * (a + b + 1), 2 * (a + b + 1));
auto fun = [&](int i, int j) {
return i + j * (a + b + 1);
};
f.a[0][fun(0, 0)] = 1ll;
for (int i = 0; i <= a + b; ++i)
op.a[fun(i, 0)][fun(i, 0)] = op.a[fun(i, 1)][fun(i, 0)] = 1ll;
for (int i = 0; i <= a + b; ++i)
for (int j = 0; j <= i; ++j)
op.a[fun(j, 0)][fun(i, 1)] = C[i][j];
f = f * (op ^ n);
// for (int i = 0; i <= n; ++i) {
// if (i)
// f = f * op;
// for (int j = 0; j <= a + b; ++j)
// printf("f[%d][%d] = %lld / %lld\n", i, j, f.a[0][fun(j, 0)], f.a[0][fun(j, 1)]);
// }
auto res = 0ll;
for (int i = 0; i <= a; ++i) {
static auto p(1ll), k((a % 2) ? mod - 1ll : 1ll);
(res += C[a][i] * p % mod * k % mod * (f.a[0][fun(a + b - i, 0)] + f.a[0][fun(a + b - i, 1)]) % mod) %= mod;
(p *= n) %= mod, k = mod - k;
}
std::cout << res << '\n';
return 0;
}B - Different Subsets For All Tuples
https://www.luogu.com.cn/problem/CF660E
首先你可能需要知道，如果已知一个序列，如何得到答案？
令 \(f_i\) 表示在 \(i\) 处取一个子序列的末尾，枚举上一个元素 \(x\)，找到 \(i\) 之前最靠后的一个 \(a_j=x\)，那么有 \(f_i=\sum f_j\)，换言之需要保证 \((j,i)\) 范围内没有 \(x\) 出现。
此时序列未知，令 \(f_{i, x}\) 表示在 \(i\) 处取一个子序列末尾，且 \(i\) 的值为 \(x\)；按照贡献的视角来看待，每个可以和 \(i\) 组成新子序列的方案可以带来 \(m^{i-1}\) 的贡献（因为 \(a_i\) 已经固定为 \(x\)，其他位置可以任选），那么有 \(f_{i,x}=m^i\times \sum_{j<i,y}f_{j,y}\times (m-1)^{i-j-1}\)。
然后就惊讶地发现式子和 \(x\) 这一维没有关系了。所以直接带上系数得到：
\[ \begin{aligned} f_i&=m^i\times \sum_{j<i} f_j\times (m-1)^{i-j-1}\times m\\ &=m^i\times (m-1)^{i-1}\times m\cdot \sum_{j<i} f_j\times (m-1)^{-j} \end{aligned} \]
前缀和优化一下就可以快速求了。最终的答案就是 \(res=m^n+\sum f_i\times (m-1)^{n-i}\)。
#include <bits/stdc++.h>
const int mod = 1e9 + 7;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m;
std::cin >> n >> m;
if (m == 1)
std::cout << (n + 1) << '\n';
else {
std::vector<long long> f(n + 1), s(n + 1), pm1(n + 1);
pm1[0] = 1ll;
for (int i = 1; i <= n; ++i)
pm1[i] = pm1[i - 1] * (m - 1) % mod;
auto qkp = [](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
auto res(qkp(m, n));
const auto invm = qkp(m - 1, mod - 2);
for (int i = 1; i <= n; ++i) {
static long long p(m), inv(invm);
f[i] = (p + pm1[i - 1] * m % mod * s[i - 1] % mod) % mod;
s[i] = (s[i - 1] + f[i] * inv % mod) % mod;
(res += f[i] * pm1[n - i] % mod) %= mod;
(p *= m) %= mod, (inv *= invm) %= mod;
}
std::cout << res << '\n';
}
return 0;
}G - Gardens
https://atcoder.jp/contests/abc235/tasks/abc235_g
如果没有『每个人必须有一个元素』这个限制，就可以随便做了。现在加上了这个限制，很容易想到用没得到的人来容斥。钦定至少有 \(i\) 个人没拿到，得到答案为 \(\sum\limits_{i=0}^n (-1)^i\cdot C_n^i\cdot \left(\sum\limits_{j=0}^a C_i^j\right)\cdot \left(\sum\limits_{j=0}^b C_i^j\right)\cdot \left(\sum\limits_{j=0}^c C_i^j\right)\)。
怎么算 \(\sum\limits_{j=0}^a C_i^j\) 呢？当 \(a> i\) 时，二项式是好求的；当 \(a\le i\) 时呢？看到这个式子很容易带到杨辉三角里去，也就是求一行的前 \(a\) 个数。注意到可以用上一行的前 \(a\) 个数 \(O(1)\) 得到（假设第 \(j-1\) 行前 \(a\) 个数之和为 \(f_a(j-1)\)）：\(f_a(j)=f_a(j-1)\times 2-C_{j-1,a}\)。你需要意识到，由于上一行也是答案中要求的，所以可以使用递推解决问题。在组合计数中，递推 / DP 无论是在化简式子还是求容斥 / 二项式反演里具体某一限制下的方案数都是很有用的，在需要优化复杂度时，可以从递推 / DP、恒等式、前缀和、预处理等方法入手考虑。
#include <bits/stdc++.h>
const int mod = 998244353;
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen(".in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, a, b, c;
std::cin >> n >> a >> b >> c;
std::vector<long long> fac(n + 1), inv(n + 1), fa(n + 1), fb(n + 1), fc(n + 1), pow2(n + 1);
fac[0] = inv[0] = pow2[0] = 1ll;
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i % mod;
pow2[i] = pow2[i - 1] * 2 % mod;
}
auto qkp = [&](long long x, int y) {
auto res(1ll);
for (; y; (x *= x) %= mod, y >>= 1)
if (y & 1)
(res *= x) %= mod;
return res;
};
inv[n] = qkp(fac[n], mod - 2);
for (int i = n - 1; i; --i)
inv[i] = inv[i + 1] * (i + 1) % mod;
auto C = [&](int n, int m) {
return fac[n] * inv[n - m] % mod * inv[m] % mod;
};
for (int i = 0; i <= a; ++i)
(fa[a] += C(a, i)) %= mod;
for (int i = a + 1; i <= n; ++i)
fa[i] = (2 * fa[i - 1] % mod + mod - C(i - 1, a)) % mod;
for (int i = 0; i <= b; ++i)
(fb[b] += C(b, i)) %= mod;
for (int i = b + 1; i <= n; ++i)
fb[i] = (2 * fb[i - 1] % mod + mod - C(i - 1, b)) % mod;
for (int i = 0; i <= c; ++i)
(fc[c] += C(c, i)) %= mod;
for (int i = c + 1; i <= n; ++i)
fc[i] = (2 * fc[i - 1] % mod + mod - C(i - 1, c)) % mod;
auto res(0ll);
for (int i = n, p = 1; ~i; --i, p = mod - p)
(res += p * C(n, i) % mod * (i >= a ? fa[i] : pow2[i]) % mod * (i >= b ? fb[i] : pow2[i]) % mod * (i >= c ? fc[i] : pow2[i]) % mod) %= mod;
std::cout << res << '\n';
return 0;
}