计数题反演总结

Arahc 11.0
  2022-01-19 08:00 2022-01-19 08:00 创建   2023-03-19 07:30:40 2023-03-19 07:30:40 更新    2.4k 字  13 分钟  

这里记录一下三种数数题或者数学题里可能会遇到的反演。欧拉反演和莫比乌斯反演在我的解析数论博客里面，斯特林反演在斯特林数博客里。欢迎大家围观。

反演的本质其实就是，给出两个函数的关系 AA 如何算出 BB，现在要推出 BB 怎么算出 AA。

二项式反演

这是一种比较套路的反演。若 f,gf,g 满足：

f(x)=∑i=0n(ni)gif(x) = \sum_{i=0}^n \binom{n}{i} g_i

则有：

gn=∑i=0n(−1)n−i(ni)fig_n = \sum_{i=0}^n (-1)^{n-i}\binom{n}{i} f_i

Luogu4859 已经没有什么好害怕的了

给定两个长为 nn 的序列 a,ba,b，求有多少种两两匹配的方案，使得 ai>bja_i>b_j 的配对数恰好比 bi>ajb_i>a_j 的配对数多 kk。

n≤2000n\leq 2000。

题解

不难发现所求为 ai>bja_i>b_j 对数为 n+k2\frac{n+k}{2}。设 fif_i 表示至少有 ii 对，gig_i 表示恰好选 ii 对，则：

fk=∑i=kn(ik)gif_k = \sum_{i=k}^n \binom{i}{k} g_i

二项式反演：

gk=∑i=kn(−1)i−k(ik)fig_k = \sum_{i=k}^n (-1)^{i-k}\binom{i}{k} f_i

ff 的转移很简单，设 hi,jh_{i,j} 表示前 ii 个 aa 选了 jj 组 ax>bya_x>b_y 的配对：

hi,j←hi−1,j+(li−j+1)fi−1,j−1h_{i,j} \gets h_{i-1,j} + (l_i-j+1)f_{i-1,j-1}

其中 lil_i 为从小到大排序后满足 bj<aib_j<a_i 的最大的 jj。

则 fi=hn,i(n−1)!f_i = h_{n,i}(n-1)!。直接 DP 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=2002,mod=1000000009;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

int f[max_n],dp[max_n][max_n],ans;
int n,k,a[max_n],b[max_n],l[max_n],fac[max_n],inv[max_n];

inline int C(int n,int m){
    if(n<0 || m<0 || n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}

signed main(){
	n=read(),k=read();
	if((n+k)&1){
	    write(0);
	    return 0;
	}
	k=(n+k)/2;
	for(register int i=1;i<=n;++i)
	    a[i]=read();
	for(register int i=1;i<=n;++i)
	    b[i]=read();
	sort(a+1,a+1+n),sort(b+1,b+1+n);
	fac[0]=1;
    for(register int i=1;i<=n;++i)
        fac[i]=fac[i-1]*i%mod;
    inv[n]=mi(fac[n]);
    for(register int i=n-1;i>=0;--i)
        inv[i]=inv[i+1]*(i+1)%mod;
	for(register int i=1,j=0;i<=n;++i){
	    while(j<n && b[j+1]<a[i]) ++j;
	    l[i]=j;
	}
	dp[0][0]=1;
	for(register int i=1;i<=n;++i)
	    for(register int j=0;j<=i;++j){
	        dp[i][j]=dp[i-1][j];
	        if(j && l[i]-j+1>0)
	            dp[i][j]+=(l[i]-j+1)*dp[i-1][j-1]%mod,dp[i][j]%=mod;
	    }
	for(register int i=0;i<=n;++i)
	    f[i]=dp[n][i]*fac[n-i]%mod;
	for(register int i=k;i<=n;++i)
	    ans+=((i-k)&1?-1:1)*C(i,k)*f[i]%mod,
	    ans=(ans+mod)%mod;
	write(ans);
	return 0;
}

单位根反演

单位根反演就是把整除判断的东西转化为单位根的幂。

[n∣k]=1n∑i=0n−1ωnik[n\mid k] = \frac{1}{n}\sum_{i=0}^{n-1} \omega_n^{ik}

记住式子就可以做了。当然单位根也不一定必须用虚数的那个单位根，例如在取模意义下可能可以用原根。

当然可能还有一个辅助单位根反演的式子：

⌊ik⌋=−1+∑j=0i[k∣j]\left\lfloor\frac{i}{k}\right\rfloor = -1 + \sum_{j=0}^i [k\mid j]

把这个辅助式子用单位根反演展开为：

⌊ik⌋=−1+∑j=0i1k∑d=0k−1ωkdj\left\lfloor\frac{i}{k}\right\rfloor = -1 + \sum_{j=0}^i \frac{1}{k} \sum_{d=0}^{k-1} \omega_{k}^{dj}

Luogu5591 小猪佩奇学数学

求下面式子对 998244353998244353 取模的结果：

∑i=0npi(ni)⌊ik⌋\sum_{i=0}^n p^i\binom{n}{i}\left\lfloor\frac{i}{k}\right\rfloor

n,p<998244353,k∈{2w∣0≤w≤20}n,p<998244353,k\in\{2^w|0\leq w\leq 20\}。

题解

先直接单位根反演，然后拆开括号用二项式定理：

ans=∑i=0npi(ni)(−1+∑j=0i1k∑d=0k−1ωkdj)=1k∑i=0npi(ni)∑j=0i∑d=0k−1ωkdj−(p+1)n=1k∑d=0k−1∑i=0npi(ni)∑j=0i(ωkd)j−(p+1)n\begin{aligned}ans &= \sum_{i=0}^n p^i \binom{n}{i} \left( -1+\sum_{j=0}^i\frac{1}{k}\sum_{d=0}^{k-1} \omega_k^{dj} \right) \\&= \frac{1}{k} \sum_{i=0}^n p^i\binom{n}{i} \sum_{j=0}^i\sum_{d=0}^{k-1} \omega_k^{dj} - (p+1)^n \\&= \frac{1}{k} \sum_{d=0}^{k-1}\sum_{i=0}^n p^i\binom{n}{i} \sum_{j=0}^i (\omega_k^d)^j - (p+1)^n\end{aligned}

这是等比数列求和的形式：

ans=1k∑d=0k−1∑i=0npi(ni)ωkdi+d−1ωkd−1−(p+1)n=1k∑d=0k−1∑i=0n(ni)(pωkd)i−(p+1)nωkd−1−(p+1)n=1k∑d=0k−1ωkd(pωkd+1)n−(p+1)nωkd−1−(p+1)n\begin{aligned}ans &= \frac{1}{k} \sum_{d=0}^{k-1}\sum_{i=0}^n p^i\binom{n}{i} \frac{\omega_k^{di+d}-1}{\omega_k^d-1} - (p+1)^n \\&= \frac{1}{k} \sum_{d=0}^{k-1} \frac{\sum_{i=0}^n \binom{n}{i}(p\omega_k^d)^i - (p+1)^n}{\omega_k^d-1} -(p+1)^n \\&= \frac{1}{k} \sum_{d=0}^{k-1} \frac{\omega_k^d (p\omega_k^d+1)^n - (p+1)^n}{\omega_k^d-1} -(p+1)^n \\\end{aligned}

ω\omega 取模数的原根 33。复杂度 nlog⁡nn\log n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=2000006,mod=998244353,G=3;
inline int read(){
	int x=0;bool w=0;char c=getchar();
	while(c<'0' || c>'9') w|=c=='-',c=getchar();
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w?-x:x;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;a%=mod;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

int n,p,k,ans,w[max_n];

signed main(){
	n=read(),p=read(),k=read();
	w[0]=1,w[1]=mi(G,(mod-1)/k);
	for(register int i=2;i<=k;++i)
	    w[i]=w[1]*w[i-1]%mod;
	ans=(n*p%mod*mi(p+1,n-1)%mod+mi(p+1,n))%mod;
	for(register int d=1;d<k;++d){
	    ans+=(w[d]*mi(p*w[d]+1,n)-mi(p+1,n))%mod*mi(w[d]-1)%mod,
	    ans%=mod;
	}
	write((ans*mi(k)-mi(p+1,n))%mod);
	return 0;
}

子集反演

在了解子集反演之前，先考虑子集卷积：

f(S)=∑T⊂Sg(T)h(S−T)f(S) = \sum_{T\subset S} g(T)h(S-T)

其中 f,g,hf,g,h 是作用在集合上的函数。记为 f=ghf=gh。子集卷积可以用 FWT 解决。

然后考虑子集反演，若存在：

f(S)=∑T⊂Sg(T)f(S) = \sum_{T\subset S} g(T)

则：

g(S)=∑T⊂S(−1)∣S−T∣f(T)g(S) = \sum_{T\subset S} (-1)^{\left|S-T\right|} f(T)

用 FWT 的或卷积就可以把它卷过来。

SP13106 KOSARE

nn 个箱子和 mm 种物品，每个箱子里有若干种物品。求选出一些箱子使得每种物品都有的方案数。

n≤106,m≤20n\leq 10^6,m\leq 20。

题解

设 f(S)f(S) 表示集合为 SS 的子集的箱子个数，F(S)F(S) 为取到的物品集合为 SS 的子集的方案数。显然 F(S)=2f(S)−1F(S) = 2^{f(S)}-1。

求解 f(S)f(S) 是一个高维前缀和的过程。考虑求答案，即恰好为一个集合 SS 的方案数。子集反演即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=2000006,mod=1000000007;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res*=a,res%=mod;
        a*=a,a%=mod,p>>=1;
    }
    return res;
}

int n,m,S,f[max_n],F[max_n],ans;

inline void OR(int *f,int x=1){
    for(register int k=1,l=2;l<=S;l<<=1,k<<=1)
        for(register int i=0;i<S;i+=l)
            for(register int j=0;j<k;++j)
                f[i+j+k]+=f[i+j]*x%mod,
                f[i+j+k]=(f[i+j+k]+mod)%mod;
}

signed main(){
    n=read(),m=read(),S=(1<<m);
    for(register int i=1;i<=n;++i){
        int k=read(),st=0;
        for(register int i=1;i<=k;++i){
            int p=read()-1;
            st|=(1<<p);
        }
        ++f[st];
    }
    OR(f);
    for(register int i=0;i<S;++i)
        F[i]=mi(2,f[i])-1;
    OR(F,-1);
    write(F[S-1]);
    return 0;
}
  • 标题: 计数题反演总结
  • 作者: Arahc
  • 创建于 : 2022-01-19 08:00:00
  • 更新于 : 2023-03-19 07:30:40
  • 链接: https://arahc.github.io/2022/01/19/【笔记】计数题反演总结/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
计数题反演总结
  1. 二项式反演
  2. 单位根反演
  3. 子集反演