反演及容斥散讲

先上容斥原理公式:

|\cup_{i=1}^nS_i|=\sum_{i=1}^n|S_i| – \sum_{0 < i < j \leq n} |S_i \cap S_j| + … +(-1)^{n+1}|S_1 \cap S_2 \cap S_3 … \cap S_n|

小学生容斥

首先来一道题: 求n个元素的错排!

  • 假设 fx 表示至少有 x 个在原来的位置上(有重复)
  • gx 表示恰好有 x 个在原来的位置上

易得

ans=n!-\sum_{i=1}^ng(i)

而且f (i) (有重复的) = \binom n i(n-i)!
但是我们也可以发现即使f有算重的情况, 那么与g有关式子(yy一下):

f(x) = \sum_{k=x}^n \binom k x g(k)

而且二项式定理有如下式子:

\sum_{i=1}^n (-1) ^ i \binom n i = [n = 0]

那么我们考虑其实 ans 也可表示如下

ans = n! – f(1) + f(2) – f(3)… + (-1) ^ n f(n)

证明考虑展开利用上式公式即可!

这, 就是小学生容斥

中学生反演

如: 二项式反演… 雾
f(n)表示n个元素随便站的方案, g(n)表示n元素的错排, 即都不在原来位置!
有如下式子:

f(n)=\sum_{i=0}^n\binom n i g(i)

那么二项式反演所求的就是在较低的n级别的复杂度内求解问题!

g(n)=\sum_{m=0}^n[n=m] \binom{n} {m} g(m) … \ nothing\ special\\
use \ \sum_{i=0}^n(-1)^i \binom n i = [n=0]\\
then\ get\ g(n)=\sum_{m=0}^n\sum_{k=0}^{n-m} (-1) ^{k} \binom{n – m} k \binom n m g(m) … \ nothing\ common\\

我们不难发现C_n^mC_{n-m}^k=C_n^kC_{n-k}^m 带入式子有:

g(n)=\sum_{m=0}^n\sum_{k=0}^{n-m} (-1)^k \binom{n – k} m \binom n k g(m) \\
have \ g(n)=\sum_{k=0}^n(-1)^k\binom n k \sum_{m=0}^{n-k} \binom {n – k} m g(m)\\
∴g(n)=\sum_{k=0}^n(-1)^k \binom n k f(n-k) \\

复杂度也是\Theta(n)

小结:

对于求恰好什么什么的, 然后知道大于什么什么的函数怎么求, 就可以用小学生容斥了, 二项式反演可能更加套路一点, 背背板子好了!
个人感觉二项式反演更好一点, 虽然不好推QAQ!

穿插题: Counting swaps (ICPC)

题意自己看去…

考虑我们对于每一个位置i, 向a[i]连边, 那么我们会得到一张图(含自环), 不难发现其实这幅图中都是”环”,
而题目所求的就是通过交换操作, 使得最后所有的点都是自环, 即1~n的排列!

我们首先可以用数学归纳法证明长度为n的环最少需要操作(n-1)次! (证明略去)

考虑环长为n的方法数 F(n)

引理:

对于一个多元可重集S

\{a_1 x_1, a_2x_2…,a_kx_k\}

从中选择r(r \leq a_i)个元素组成另一个可重集的方案数就是C_{r+k-1}^{k-1} 考虑隔板法: x_1+x_2+…+x_k=r的方案就好了
如:

变成了…

不难发现, 将这个○拆掉共有:

T_{(x, y)} = \begin{cases}
\frac n 2 & x = y, n \mod 2 \equiv 0 \\
n & otherwise
\end{cases}

那么对于F(n), 第一步一定是拆成n = x + y形式, 对它进行递归, 然后考虑两个圆有(x-1) + (y – 1) 步要分配, 就好比是两种相同元素进行可重集排列数操作, 即考虑乘法原理和可重集排列数和加法原理可知方案为

F_n=\sum_{x+y=n} F_x \cdot F_y\cdot T(x, y)\cdot C_{n – 2}^{x – 1}

那么根据上面的思路, 那么答案就是:

ans=F(l_1)\cdot F(l_2) … \cdot F(l_n) \frac{(n-k)!}{(l_1 – 1) ! (l_2 – 1)! …(l_n – 1) !}

然后推好啦, 但是其实好像F(n)的规律可以直接oeis一下就好了… 即F(n)=n^{n-2}
然后处理一下阶乘逆元之类的就可以在\Theta(nlog_2n) 处理出来了!

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 100050;
const LL MOD = 1e9 + 9;

int T, n, cnt, a[N];
LL fac[N] = {1}, inv[N];

vector<int> G[N];
bitset<N> vis;

void dfs(int x)
{
  vis[x] = true;
  G[cnt].push_back(x);
  if(vis[a[x]]) return ;
  dfs(a[x]);
}
LL Pow(LL a, LL b)
{
  if(b < 0) return 1;
  LL res = 1;
  while(b)
  {
    if(b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
void init(int n = 1e5)
{
  for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
  inv[n] = Pow(fac[n], MOD - 2);
  for(int i = n - 1; i; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
  inv[0] = 1; 
}
LL calc(LL x) { return Pow(x, x - 2); }
int main()
{
  init();
  scanf("%d", &T);
  for(int _ = 1; _ <= T; _++)
  {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    for(int i = 1; i <= n; i++) G[i].clear();
    vis.reset();
    cnt = 0;
    for(int i = 1; i <= n; i++)
      if(!vis[i]) 
      {
        ++cnt;
        dfs(i);
      }
    LL ans = 1;
    for(int i = 1; i <= cnt; i++)
      ans = ans * calc((LL)G[i].size()) % MOD;
    ans = ans * fac[n - cnt] % MOD;
    for(int i = 1; i <= cnt; i++)
      ans = ans * inv[(int)G[i].size() - 1] % MOD;
    printf("%lld\n", ans);
  }
  return 0;
}

回归容斥…

利用之前的内容, 我们深度结合一下多重集排列数与容斥之间的关系…
考虑这样的一个问题: 从multiset

S=\{a_1 x_1, a_2x_2…,a_kx_k\}

取出r(r \leq \sum_{i=1}^n a_i) 的方案数, 那么就有一些限制了, 不能用上面的公式快速解决!
但是我们利用容斥原理可以得到答案:

ans=C_{r+k-1}^{k-1}-\sum_{i=1}^kC_{(r+k-a_i-2)}^{k-1}+\sum_{0 < i < j \leq n} C_{(r+k-a_i-a_j-3)}^{k-1}…+(-1)^kC_{r+k-\sum_{j=1}^n a_j – (k + 1)}

一些容斥例题…

T1. CF 451E Devu and Flowers

emmm… 就是求上面内容的裸题, 但是这个数据比较大!
(n \leq 50, s \leq 10^{14}, f_i \leq 10^{12}) 对 (1e9 + 7) 取模!
但是注意到k只有20左右, 那么我们其实算组合数的时候就可以”暴力”就好了!

Code:

注意会报精哦, 如 1e12 * 1e9 炸long long啊!

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;

const int N = 25;
const LL MOD = 1e9 + 7;

int k;
LL ans = 0, s, f[N], fac[N] = {1}, inv[N] = {1};

#define R register 

LL Pow(LL a, LL b)
{
  LL res = 1;
  while(b)
  {
    if(b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
void init()
{
  for(int i = 1; i <= 20; i++) fac[i] = fac[i - 1] * i % MOD;
  inv[20] = Pow(fac[20], MOD - 2);
  for(int i = 19; i; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
inline LL calc(LL n, LL m)
{
  if(n < m || n < 0 || m < 0) return 0;
  LL up = 1;
  for(LL i = n; i > n - m; i --) up = i % MOD * up % MOD;
  return up * inv[m] % MOD;
}
int main()
{
  init();
  scanf("%d%lld", &k, &s);
  for(int i = 0; i < k; i++) scanf("%lld", f + i);
  int up = (1 << k);
  for(R int i = up - 1; ~i; --i)
  {
    LL minus = 0;
    int cnt = 0;
    for(R int j = 0; j < k; j++) 
      if(i >> j & 1)
      {
        cnt ++;
        minus += f[j];
      }
    if(cnt & 1) ans = (ans - calc(s + k - 1 - cnt - minus, k - 1)) % MOD;
    else ans = (ans + calc(s + k - 1 - minus - cnt, k - 1)) % MOD;
  }
  printf("%lld\n", (ans % MOD + MOD) % MOD);
  return 0;
}

T2. HDU 5201 The Monkey King

题意:

有n个桃子m只猴子,第一只猴子的桃子要严格大于其他猴子,问一共有几种方案 .

分析:

emmm… 一直在想\Theta(m)的做法, 结果没有仔细留意时限, 其实\Theta(nlogn)的也是可以的…

那么我们只要套上一发容斥公式就好了, 枚举一下猴王选了多少的桃子, 有多少的猴子要>=猴王桃数的就好了…

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double db;

const LL MOD = 1e9 + 7;
const int N = 2e5 + 50;

int T, n, m;
LL ans, fac[N] = {1}, inv[N] = {1};

LL Pow(LL a, LL b)
{
  LL res = 1;
  while(b)
  {
    if(b & 1) res = res * a % MOD;
    a = a * a % MOD;
    b >>= 1;
  }
  return res;
}
void init(int n = 2e5)
{
  for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
  inv[n] = Pow(fac[n], MOD - 2);
  for(int i = n - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
inline LL calc(LL n, LL m)
{
  return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
int main()
{
  init();
  scanf("%d", &T);
  for(int _ = 1; _ <= T; ++_)
  {
    scanf("%d%d", &n, &m);
    ans = calc(n + m - 1, m - 1);
    for(int i = 1; i < m; i++)
    {
      LL sy = (i & 1) ? -1 : 1;
      for(int x = 0; x <= n; ++x)
      {
        if(n < (i + 1) * x) break;
        ans = (ans + sy * calc(m - 1, i) * calc(n - (i + 1) * x + m - 2, m - 2)) % MOD;
      }
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
  }
  return 0;
}

T3: No Name

emmm… 我要安利道题目: 无名题…


问, 给一个n×m的矩形, 每个格子可以用k种颜色涂改, 问最后没有一行或一列是完全同色的方案数, 对998244353取模!

这题感觉非常妙啊

分析:

一眼看出是容斥然后爆零

根据容斥系数的关系, 我们先假设f(i,j)表示有i行与j列的方案数不难发现:

f(i,j) = \begin{cases}
1 & j = 0\ and\ i = 0\\
k^i & j = 0 \\
k^j & i = 0 \\
k & i \neq 0 \ and \ j \neq 0
\end{cases}

那么我们根据容斥系数可以得出:

ans=\sum_{i=0}^n \sum_{j=0}^m(-1)^{i+j}\binom n i \binom m j f(i, j) k^{(n-i)(m-j)}

对于i=0或j=0的暴力计算, 剩下i>0 和 j > 0 然后对它进行移项可以有:

ans=\sum_{i=0}^n \sum_{j=0}^m(-1)^{i+j}\binom n i \binom m j f(i, j) k^{(n-i)(m-j)}\\
=k(即f(i,j))\sum_{i = 0} ^ n (-1)^i \binom n i \sum_{j=0}^m \binom m j (-1)^j (k^{(n-i)})^{m-j}\\
考虑二项式定理(a+b)^n, 再此a=-1,b=k^{(n-i)},有\\
ans=k\sum_{i=1}^n(-1)^i \binom n i \{(k^{n-i} – 1) ^m – (k^{n-i})^m \}\\

然后就ok了!

Code:

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define R register 

const LL MOD = 998244353;
const int N = 1e6 + 50;
LL ans, n, m, k, fac[N] = {1}, inv[N] = {1};

inline LL Pow(LL a, LL b)
{
    LL res = 1;
    while(b) { if(b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; }
    return res;
}
inline LL C(LL n, LL m)
{
    if(n < 0 || m < 0 || n < m) return 0;
    return fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}
void init(int n = 1e6)
{
    for(int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % MOD;
    inv[n] = Pow(fac[n], MOD - 2);
    for(int i = n - 1; i; --i) inv[i] = inv[i + 1] * (i + 1) % MOD;
}
inline LL calc(LL a, LL b, LL c)
{
    return Pow(a, b * c);
}

int main()
{
    init();
    scanf("%lld%lld%lld", &n, &m, &k);
    if(n > m) swap(n, m);
    ans = calc(k, n, m) % MOD;
    for(R int i = 1; i <= n; i++)
    {
        LL res = C(n, i) * Pow(k, i) % MOD * calc(k, n - i, m) % MOD;
        LL sy = (i & 1) ? -1 : 1;
        (ans += sy * res) %= MOD;
    }
    for(R int j = 1; j <= m; j++)
    {
        LL res = C(m, j) * Pow(k, j) % MOD * calc(k, n, m - j) % MOD;
        LL sy = (j & 1) ? -1 : 1;
        (ans += sy * res) %= MOD;
    }
    for(R int i = 1; i <= n; i++)
    {
        LL res = Pow(Pow(k, n - i) - 1, m) - calc(k, n - i, m);
        LL sy = (i & 1) ? -1 : 1;
        res = res * sy * C(n, i) % MOD * k % MOD;
        ans = (ans + res) % MOD;
    }
    printf("%lld\n", (ans % MOD + MOD) % MOD);
    return 0;
}

个人总结:

再次, 对于容斥系数的一些小结:

ques: 为什么一般容斥方程是这样的: ans = (-1)^i f[i] (i = [0, n])?
Prove:
其实文章一开始的错排(容斥法)有说明, 那么我来对其进行一次总结, 就像刚刚的T3一样, 为什么是(-1)^{i+j}, 因为我们设g(x,y)表示刚刚好有x行,y列同色的情况, 那么有:

f(i,j)=C_x^iC_y^j g(x, y) (x>=i,y>=j)

那么式子里的f搞来搞去, 我们会发现g(x,y)的贡献:
\sum_{i=0}^x\sum_{j=0}^y(-1)^iC_x^i(-1)^jC_y^jg(x,y)
只有x=0,y=0是才会有贡献哦

一句话, 就是利用:

\sum_{i=1}^n (-1) ^ i \binom n i = [n = 0]

这个式子!!!

容斥模型:

1.无序化有序
2.对于一些状态, 我们希望得到|A_1 \cap A_2\cap A_3…\cap A_n|于是我们就可以枚举出限制, 如至少超出p个限制的方案, 对它们乘上一个容斥系数即可
3.补集转换
4.对于一种方案数, 可以试着考虑用总方案数-非法方案数, 而且这个非法方案可以考虑枚举不合法的位置, 然后考虑它们之间是否有交集,再考虑是否容斥!
5.最毒瘤的当属dp+容斥, 如期望:

E(x)=\sum_{k=1}^{\infty} k \cdot Pr[X=k] = \sum_{i=0}^{\infty} Pr[X > k]

这样我们对于每一个X都可以被枚举到恰好K遍.
然后可以在题目里套个等比数列求和之类的…

3 Replies to “反演及容斥散讲”

发表评论

电子邮件地址不会被公开。 必填项已用*标注