省选前的反演抢救计划

RT，熟悉的标题

表示开始抢救的时候关于反演的那一套已经快忘完了

然而沙茶博主做反演题的过程基本就是：看题->xjb推->推不动->看题解

主要是莫比乌斯反演，有空就再搞搞二项式反演

同样不建议......

我佛了

---

莫比乌斯反演那一套理论.jpg

同时涉及一些数论相关？

万恶之源：

狄利克雷卷积函数：$(f×g)(n)=sum_{d|n}f(d)g(frac{n}{d})$。

基本结论

1 x 1 = d，证明：定义

φ x 1 = id，证明：若n为质数，则id。其他情况用积性函数证明。

μ x id = φ，证明：上面那个东西莫比乌斯反演一下

μ x 1 = ε，证明：考虑每个质数选几个，用二项式定理确定系数，带进去后发现和为0。

ε × 1 = 1，证明：每个数为1的因数只有1，显然

元函数e和谁卷得出来的都是那个函数

整除的性质

$leftlfloor frac{n}{a*b} ight floor=leftlfloor frac{leftlfloor frac{n}{a} ight floor}{b}  ight floor$，向上取整同理

莫比乌斯反演定理

$g(n)=sum_{d|n}f(d)->f(n)=sum_{d|n}μ(frac{n}{d})g(d)$

常用技巧

1.数论分块

大部分时候从本质上降低复杂度的是数论分块

注意有限制时被限制的部分不能放进分块里

2.gcd

①枚举gcd

②gcd和lcm的关系，其实反演里所有的lcm归根结底都是gcd

③d|gcd(a,b)当且仅当d|a&&d|b，gcd(a*b,c)==1当且仅当$gcd(a,c)==1&&gcd(b,c)==1$

④设$f(d)=sum_{d==gcd(i,j)}$，$g(n)=sum_{d|gcd(i,j)}$，那么$g(d)=leftlfloorfrac{n}{d} ight floorleftlfloorfrac{m}{d} ight floor$

3.交换求和号

基本技能，字面意思

4.枚举整体/前提枚举/改变枚举对象

前面的是一个套路的东西,比如枚举一个乘积或者枚举一个下取整除法

中间那个那个经常提μ或者题目给的一个函数，还有注意前提时指数的变化

(前提枚举->向前提取枚举的某一项)

后者灵活用就好(指xjb用)

5.xjb使用基本结论和莫反定理，哦，还有一些函数的本质定义以及数论中的其他小知识

当别的技巧都没有用的时候，总可以用更基本的东西试一试

6.特别的一些技巧

对于除式，可以考虑分子分母分开算

对于带着逻辑运算符的式子，可以考虑按逻辑运算来拆开算

有时候可能需要线性筛预处理积性函数

常见的(反演)结果

1D GCD

$sumlimits_{i=1}^{n}gcd(i,n)=sumlimits_{i=1}^{n}sum_{d|gcd(i,n)}φ(d)=sum_{d|n}φ(d)frac{n}{d}$

2D GCD

$sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}gcd(i,j)=sumlimits_{d=1}^{min(n,m)}φ(d)leftlfloorfrac{n}{d} ight floor leftlfloorfrac{m}{d} ight floor$

GCD=k

$sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)==k]=sumlimits_{i=1}^{min(n,m)}[k|i]μ(frac{i}{k})leftlfloorfrac{n}{i} ight floorleftlfloorfrac{m}{i} ight floor=sumlimits_{i=1}^{min(leftlfloorfrac{n}{k} ight floor,leftlfloorfrac{m}{k} ight floor)}μ(i)leftlfloorfrac{n}{ik} ight floorleftlfloorfrac{m}{ik} ight floor$

1D LCM

$sumlimits_{i=1}^nlcm(i,n)=sumlimits_{i=1}^nnfrac{i}{gcd(i,n)}$

枚举$gcd(i,n)$

$sum_{d|n}frac{sum i[gcd(i,n)==d]}{d}=sum_{d|n}sum_{j=1}^{frac{n}{d}}j=$自行等差数列求和

2D 互质数对乘积和

$sumlimits_{i=1}^n i^2φ(i)$

---

题

题！实践！推式子！

我反正是复习的时候把写过的反演题又推了一遍，没写过题解的就放这里了

一些之前做过的题(混进来一个二项式反演)，修了好多原来naive的锅

国家集训队 Crash的数字表格 

求$sumlimits_{i=1}^nsumlimits_{j=1}^mlcm(i,j)$，单次询问

(加强版是多次询问，再推一推用线性筛积性函数可以做到$O(n+Tsqrt n)$，一定写)

这题用到的技巧很多，适合熟悉莫反

— —所有的lcm归根结底都是gcd

$sumlimits_{i=1}^nsumlimits_{j=1}^mlcm(i,j)$

$sumlimits_{i=1}^nsumlimits_{j=1}^mfrac{i*j}{gcd(i,j)}$

枚举+前提gcd，下设$n<=m$

$sumlimits_{d=1}^nsumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)==d]frac{i*j}{d}$

$sumlimits_{d=1}^n dsumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}sumlimits_{j=1}^{leftlfloorfrac{m}{d} ight floor}[gcd(i,j)==1]i*j$

先算后半段，开始xjb使用基本结论(μx1=ε)

$=...sumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}sumlimits_{j=1}^{leftlfloorfrac{m}{d} ight floor}sum_{t|gcd(i,j)}μ(t)i*j$

向前提$μ$

$=...sumlimits_{t=1}^{n}μ(t)sumlimits_{t|i}^{leftlfloorfrac{n}{d} ight floor}sumlimits_{t|j}^{leftlfloorfrac{m}{d} ight floor}i*j$

为了丢掉整除的限制，我们枚举除过$t$的结果，在前面用$t^2$补上

$=...sumlimits_{t=1}^nμ(t)t^2sumlimits_{i=1}^{leftlfloorfrac{n}{dt} ight floor}sumlimits_{j=1}^{leftlfloorfrac{m}{dt} ight floor}i*j$

对于$leftlfloorfrac{n}{dt} ight floor$这后面的东西可以$O(1)$算，所以可以数论分块+等差数列求和解决，再把后半段整个拿出来数论分块，就可以做到$O(n)$了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e7+70,mod=20101009;
int n,m,cnt,pri[N],npr[N],mul[N],sum[N];
void Add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
void Pre(int a,int b)
{
    int lim=min(a,b);
    npr[1]=true,mul[1]=1;
    for(int i=2;i<=lim;i++)
    {
        if(!npr[i]) pri[++cnt]=i,mul[i]=-1;
        for(int j=1,t;j<=cnt&&(t=i*pri[j])<=lim;j++)
        {
            npr[t]=true;
            if(i%pri[j]==0) break;
            else mul[t]=-mul[i];
        }
    }
    for(int i=1;i<=lim;i++)
        sum[i]=(sum[i-1]+1ll*i*i%mod*(mul[i]+mod)%mod)%mod;
}
int Calc(int a,int b)
{
    return 1ll*a*(a+1)/2%mod*(1ll*b*(b+1)/2%mod)%mod;
}
int G(int a,int b)
{
    int ret=0,lim=min(a,b);
    for(int i=1,j;i<=lim;i=j+1)
    {
        j=min(a/(a/i),b/(b/i));
        Add(ret,1ll*Calc(a/i,b/j)*(sum[j]-sum[i-1]+mod)%mod);
    }
    return ret;
}
int F(int a,int b)
{
    int ret=0,lim=min(a,b);
    for(int i=1,j;i<=lim;i=j+1)
    {
        j=min(a/(a/i),b/(b/i));
        Add(ret,1ll*(i+j)*(j-i+1)/2%mod*G(a/i,b/i)%mod);
    }
    return ret;
}
int main()
{
    scanf("%d%d",&n,&m),Pre(n,m);
    printf("%d",F(n,m));
    return 0;
}

BZOJ 4407 于神之怒加强版

求$sumlimits_{i=1}^nsumlimits_{j=1}^m gcd(i,j)^k(mod$ $1e9+7)$

枚举gcd

$sumlimits_{d=1}^nd^ksumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)==d]$

$sumlimits_{d=1}^nd^ksumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}μ(i)leftlfloorfrac{n}{id} ight floorleftlfloorfrac{m}{id} ight floor$

因为多次询问，现在的复杂度还不够

枚举id并前提

$sumlimits_{k=1}^{n}leftlfloorfrac{n}{k} ight floorleftlfloorfrac{n}{k} ight floorsum_{d|k}μ(frac{k}{d})d^k$

后面这个东西可以用 线性筛那一套.jpg

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e6+50,mod=1e9+7;
int n,k,t1,t2,nm,cnt,ans;
int pri[N],npr[N],pwe[N],sum[N];
 
void Add(int &x,int y){x+=y; if(x>=mod) x-=mod;}
int Qpow(int x,int k)
{
    if(k==1) return x;
    int tmp=Qpow(x,k/2);
    return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
 
void Pre()
{
    int lim=5e6;
    npr[1]=true,sum[1]=1;
    for(int i=2;i<=lim;i++)
    {
        if(!npr[i]) 
        {
            pri[++cnt]=i,pwe[cnt]=Qpow(i,k);
            sum[i]=(pwe[cnt]-1+mod)%mod;
        }
        for(int j=1,t;j<=cnt&&(t=i*pri[j])<=lim;j++)
        {
            npr[t]=true;
            if(i%pri[j]==0) {sum[t]=1ll*sum[i]*pwe[j]%mod; break;}
            else sum[t]=1ll*sum[i]*sum[pri[j]]%mod;
        }
    }
    for(int i=2;i<=lim;i++)
        Add(sum[i],sum[i-1]);
}
int main()
{
    scanf("%d%d",&n,&k),Pre();
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&t1,&t2);
        ans=0,nm=min(t1,t2);
        for(int l=1,r;l<=nm;l=r+1)
        {
            r=min(t1/(t1/l),t2/(t2/l));
            Add(ans,1ll*(t1/l)*(t2/l)%mod*(sum[r]-sum[l-1]+mod)%mod);
        }
        printf("%d
",ans);
    }
    return 0;
}

洛谷 4917 天守阁的地板

求$prodlimits_{i=1}^nprodlimits_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}$，多次询问

事车万题，wsl

还是那句话，所有的lcm归根结底都是gcd

$prodlimits_{i=1}^nprodlimits_{j=1}^nfrac{lcm(i,j)}{gcd(i,j)}$

$=prodlimits_{i=1}^nprodlimits_{j=1}^nfrac{i*j}{gcd(i,j)^2}$

仍然枚举gcd？这次不啦，分子分母分开算

分子：

$=prodlimits_{i=1}^nprodlimits_{j=1}^ni*j$

$=n!^{2n}$

大 成 功

分母：

$=prodlimits_{i=1}^nprodlimits_{j=1}^ngcd(i,j)^2$

这里又来枚举gcd了，类似SDOI2017那样，我们枚举gcd用指数进行贡献，这里我们只写指数了

$=...2*(sumlimits_{i=1}^nsumlimits_{j=1}^n[gcd(i,j)==d])$

注意这里还是指数呢，我们前面还有一个数论分块的$O(sqrt n)$等着呢，所以要做到$O(1)$

$=...2*(sumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}sumlimits_{j=1}^{leftlfloorfrac{n}{d} ight floor}[gcd(i,j)==1])$

$=...2*((sumlimits_{i=1}^{leftlfloorfrac{n}{d} ight floor}φ(i))*2-1)$

对指数数论分块，预处理阶乘和逆元，$O(Tsqrt n log n)$完事了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define o 1ll
using namespace std;
const int N=1e6+60,mod=19260817;
int n,rd,cnt,pri[N],npr[N],phi[N],fac[N],inv[N];
int Qpow(int x,int k)
{
    if(k==1) return x;
    int tmp=Qpow(x,k/2);
    return k%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod;
}
void Pre()
{
    int lim=1e6;
    fac[0]=inv[0]=1; 
    for(int i=1;i<=lim;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[lim]=Qpow(fac[lim],mod-2);
    for(int i=lim-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
    npr[1]=true,phi[1]=1;
    for(int i=2;i<=lim;i++)
    {
        if(!npr[i]) pri[++cnt]=i,phi[i]=i-1;
        for(int j=1,t;j<=cnt&&(t=i*pri[j])<=lim;j++)
        {
            npr[t]=true,phi[t]=phi[i]*pri[j];
            if(i%pri[j]==0) break;
            else phi[t]-=phi[i];
        }
    }
    for(int i=1;i<=lim;i++) phi[i]=(phi[i]+phi[i-1])%(mod-1);
}
int main()
{
    scanf("%d",&n),Pre();
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&rd);
        int fz=Qpow(fac[rd],2*rd),fm=1;
        for(int l=1,r,m;l<=rd;l=r+1)
        {
            r=rd/(rd/l),m=o*fac[r]*inv[l-1]%mod;
            fm=o*fm*Qpow(m,phi[rd/l]*2-1)%mod;
        }
        printf("%lld
",o*fz*Qpow(o*fm*fm%mod,mod-2)%mod);
    }
    return 0;
}

NOI 2016 循环之美 84pts部分分代码

前排提示：这篇题解写的比较欢(沙)乐(茶)，原因你下面就知道了

正解太神仙了，所以......

咕！

但是84pts的暴力真的很良心啊=。=(想起了同是NOI2016的优秀的拆分......)

运用我们小学学到的有趣小知识(√)/大力推一推(×)/打表+猜想(？)

我们发现一个数纯循环当且仅当分子分母互质且分母与进制数互质

一定要证明?

咕！

所以我们又来推式子了

(在写下这句话的时候，沙茶博主已经看+推了一下午+一晚上的莫反式子了，所以......)

$sumlimits_{i=1}^nsumlimits_{j=1}^m[gcd(i,j)==1&&gcd(j,k)==1]$

又来枚举gcd了......吗？

枚举个毛线鸭，带着&&怎么枚举鸭

再咕就只剩24pts了，还是算了

下设n<=m

那看来我们只能把两边分开了

$=sumlimits_{j=1}^m[gcd(j,k)==1]sumlimits_{i=1}^n[gcd(i,j)==1]$

后面使用基本结论

$=sumlimits_{j=1}^m[gcd(j,k)==1]sumlimits_{i=1}^nsum_{d|n}μ(d)$

算$d$的贡献

$=sumlimits_{j=1}^m[gcd(j,k)==1]sum_{d|j}μ(d)leftlfloorfrac{n}{d} ight floor$

前提μ，然后前面的那个就降到n了

$sumlimits_{d=1}^nμ(d)leftlfloorfrac{n}{d} ight floorsumlimits_{j=1}^m[d|j&&gcd(j,k)==1]$

$sumlimits_{d=1}^nμ(d)leftlfloorfrac{n}{d} ight floorsumlimits_{j=1}^{leftlfloorfrac{m}{d} ight floor}[gcd(j*d,k)==1]$

$sumlimits_{d=1}^n[gcd(d,k)==1]μ(d)leftlfloorfrac{n}{d} ight floorsumlimits_{j=1}^{leftlfloorfrac{m}{d} ight floor}[gcd(j,k)==1]$

然后我们发现前面这个东西套的太多了，只能$O(n)$(其实是$O(nlog n)$，因为还有gcd)算，所以我们必须$O(1)$得到后面的东西，然而m太大了无法承受

 

不咕

如果你稍微想一想或者把表打出来看一看，显然后面这个玩意是以k为循环节的

然后就愉快的拿到了84pts

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e7+70;
int n,m,k,lim,cnt; long long ans;
int pri[N],npr[N],mul[N],fuc[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void Pre()
{
    register int i,j,t;
    npr[1]=true,mul[1]=1,lim=min(n,m);
    for(i=2;i<=lim;i++)
    {
        if(!npr[i]) pri[++cnt]=i,mul[i]=-1;
        for(j=1;j<=cnt&&(t=i*pri[j])<=lim;j++)
        {
            npr[t]=true;
            if(i%pri[j]==0) break;
            else mul[t]=-mul[i]; 
        }
    }
    for(i=1;i<=k;i++) fuc[i]=fuc[i-1]+(gcd(i,k)==1);
}
int main()
{
    register int i;
    scanf("%d%d%d",&n,&m,&k),Pre();
    for(i=1;i<=lim;i++)
        if(gcd(i,k)==1)
            ans+=1ll*mul[i]*(n/i)*((m/i/k)*fuc[k]+fuc[m/i%k]);
    printf("%lld",ans);
    return 0;
}

关于杜教筛相关的莫反，他咕了

---

二项式反演

至少 反演出 恰好

设前者为f(n)，后者为g(n)，则有$f(n)=sumlimits_{i=0}^nC_n^ig(i)<->g(n)=sumlimits_{i=0}^n(-1)^iC_n^if(i)$

至多 反演出 恰好

设前者为f(n)，后者为g(n)，则有$f(n)=sumlimits_{i=0}^nC_n^ig(i)<->g(n)=sumlimits_{i=0}^n (-1)^{n-i}C_n^if(i)$