组合计数 - XSC062 的博客

组合计数

2025-04-07

容斥原理数学排列组合二项式定理二项式反演

毅毅：统计不是数学（断章取义 ed）。~~故删掉了数学标签。~~ 其实并没有。

#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;
}

查看代码

言论

料得年年断肠处，明月夜，短松冈。

来自「江城子·乙卯正月二十日夜记梦」

网格图路径计数

杂题选谈

#A. 二分图染色

#B. 七选五

#D. 硬币购物

#E. Distinct Multiples

#F. Permutation

#H. ~K Perm Counting

#A - Positions in Permutations

#D - All Pairs Similarity P

#E - Prefix XORs

#B - The Top Scorer

#C - Sky Full of Stars

#D - 去 M / NoM

#E - 「KDOI-11」彩灯晚会

#G - 小星星

#CF785D Anton and School - 2

#CF1332E Height All the Same

#A - 交错序列

#B - Different Subsets For All Tuples

言论