【算法】杜教筛&二项式反演&莫比乌斯反演

在此之前,狄利克雷卷积
(f·g)(n) = \sum_{d|n}f(d)g(\frac{n}{d})
积性函数嘛……虽然看起来像是完全积性函数……记住就好了。
但是一般我们并不真的直接这么看,我们会想办法把d|n变成\lfloor \frac{n}{d} \rfloor
然后再扯两个比较常见的,狄利克雷卷积结果
\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e
\sum_{d|n}\phi(d) = n = (\phi · 1) = id
接下来,开始杜教筛。

杜教筛

假如有一个积性函数f(i),现在我们要求它的前缀和,即\sum_{i=1}^{n}f(i)
杜教筛的目的是,通过将原有的函数卷上别的函数,得到一个比较好算的狄利克雷卷积形式,加速运算。
我们先写一个普通形式

\sum_{i=1}^{n}\sum_{d|i}g(d)f(\frac{i}{d})

然后交换求和顺序,将d提前

\begin{aligned} \sum_{d=1}^{n}g(d)\sum_{d|i}f(\frac{i}{d}) &= \sum_{d=1}^{n}g(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}f(i)\\ &= \sum_{d=1}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor) \end{aligned}

这里我把i的含义换成了\frac{i}{d}
那么

g(1)S(n) = \sum_{i=1}^{m}(f·g)(i)-\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)

假如\sum_{i=1}^{m}(f·g)(i)这个式子可以在一个较为快速的时间里面计算,那么我们就可以递归地套数论分块计算\sum_{d=2}^{n}g(d)S(\lfloor \frac{n}{d} \rfloor)这个式子。
假如f(i)=\mu(i),那么根据之前的一个狄利克雷卷积结果

\sum_{d|n}\mu(d) = [n=1] = (\mu · 1) = e

g(i)换成1(i)

\sum_{i=1}^{m}(f·g)(i)=1

这实际上是对于[i=1]求了个前缀和。
所以最后的公式就是

S(n)=1-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

\mu(i)换成\phi(i),那么利用第二个结论

\sum_{d|n}\phi(d) = n = (\phi · 1) = id

g(i)=1(i)这个不动,但是前面发生了改变

S(n)=\frac{n(n-1)}{2}-\sum_{d=2}^{n}S(\lfloor \frac{n}{d} \rfloor)

杜教筛可以通过处理n较小的部分加速运算,这样做的复杂度大概会到n^{\frac{2}{3}}这样的级别左右。

二项式反演

二项式反演一共有两个形式

f(n) = \sum_{i=0}^{n} (-1)^i C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^i C_n^i f(i)

f(n) = \sum_{i=0}^{n} C_n^i g(i) \Leftrightarrow g(n)=\sum_{i=0}^n (-1)^{n-i} C_n^i f(i)

只推一下第一个吧

\begin{aligned} g(n) &= \sum_{i=0}^n(-1)^iC_n^i\sum_{j=0}^{i}(-1)^jC_i^jg(j)\\ &= \sum_{j=0}^ng(j)\sum_{i=j}^nC_n^iC_j^i(-1)^{i+j} \end{aligned}

\begin{aligned} g(n) &= \sum_{j=0}^{n}C_n^jg(j)\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i+2j}\\ &= \sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}\sum_{i=0}^{n-j}C_{n-j}^{n-i}(-1)^{i} \end{aligned}

到这里其实已经很明显了,后面部分是二项式定理的展开,也就说

g(n)=\sum_{j=0}^{n}C_n^jg(j)(1-1)^{n-j}

只有j=n的时候这个式子才不为0,也就说g(n)=g(n),得证。
[BZOJ 2839]集合计数
g(k)表示目前有交集的元素个数为k并且符合条件的方案数,f(k)表示重合元素至少有k个符合条件的方案数。
那么,f(k)=C_n^k(2^{2^{n-k}}-1)
这个2^{2^{n-k}}-1,幂次上的2^{n-k}是考虑固定之后所有的集合,下面的2表示每个集合选不选,这个时候一定要选择一个集合。
但是这样会存在重复的情况,比如你选定了2,3这两个元素被重合,但事实上重合的部分是2,3,4,这个时候就会产生错误的计算了。
因此你要减去k+1个元素被选定的情况,然而你发现k+2的情况被多选择了,因此最后写出来是这样的
g(k)=\sum_{i=k}^{n}(-1)^{i-k}C_i^kf(i)
然后O(n)算就好了……我也不知道为什么qb的老师会放在二项式反演。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#define ri register int
#define pi acos(-1.0)

using namespace std;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && (t = (h = buf) + fread(buf, 1, 100000, stdin), h == t) ? EOF : *h ++;
}

typedef long long lo;

inline void re(int &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

inline void re(lo &x)
{
    x = 0;
    char a; bool b = 0;
    while(!isdigit(a = getchar()))
        b = a == '-';
    while(isdigit(a))
        x = x * 10 + a - '0', a = getchar();
    if(b == 1)
        x = - x;
}

const lo mo = 1000000007;

lo n, k, ans, fac[1000010], inv[1000010];

inline lo ksm(lo x, lo K, lo Mo)
{
    lo rt = 1, a = x;
    while(K)
        rt = rt * ((K & 1) ? a : 1) % Mo, a = a * a % Mo, K >>= 1;
    return rt;
}

int main()
{
    re(n), re(k);
    fac[1] = inv[1] = fac[0] = inv[0] = 1;
    for(ri i = 2; i <= n; i ++)
        fac[i] = fac[i - 1] * i % mo;
    inv[n] = ksm(fac[n], mo - 2, mo);
    for(ri i = n - 1; i > 1; i --)
        inv[i] = inv[i + 1] * (i + 1) % mo;
    for(ri i = k; i <= n; i ++)
    {
        lo tmp = fac[n] * inv[i] % mo * inv[n - i] % mo * (((ksm(2, ksm(2, (n - i), mo - 1), mo) - 1) % mo + mo) % mo) % mo;
        tmp = tmp * fac[i] % mo * inv[k] % mo * inv[i - k] % mo;
        if((i - k) & 1)
            ans = ((ans - tmp) % mo + mo) % mo;
        else
            ans = (ans + tmp) % mo;
    }
    printf("%lld", ans);
}

发表评论

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