zcmimi's blog
avatar
zcmimi
2019-12-01

容斥

容斥原理

  • 求具有n个属性之一(并集)的元素的个数

  • 求不具有n个属性中任何一个(交集)的元素的个数

两个集合的并集

|A \bigcup B| = |A|+|B|-|A \bigcap B|

三个集合的并集

\begin{aligned} |A \bigcup B \bigcup C| &=\quad|A|+|B|+|C|\\ &\quad-|A \bigcap B|-|A \bigcap C|-|B \bigcap C|\\ &\quad+|A\bigcap B \bigcap C| \end{aligned}

多个集合的并集

又称多步容斥

\begin{aligned} &\quad|A_1 \bigcup A_2 \bigcup ... \bigcup A_n|\\ &=\sum_{i=1}^n|A_i|\\ &- \sum_{i=1}^{n-1} \sum_{j=i+1}^n|A_i \bigcap A_j|\\ &+ \sum_{i=1}^{n-2} \sum_{j=i+1}^{n-1}\sum_{k=j+1}^{n}|A_i \bigcap A_j \bigcap A_k|\\ &- ...\\ &+(-1)^{n-1}|A_1 \bigcap A_2 \bigcap ... \bigcap A_n| \end{aligned}

De Morgan定理

A,BU的子集,则

(\overline A表示A的补集)

\overline{A\bigcup B} = \overline A\bigcap \overline B

\overline{A\bigcap B}=\overline A \bigcup \overline B

A_1,A_2,…A_nU的子集,则

\overline{A_1\bigcup A_2 \bigcup ... \bigcup A_n} = \overline{A_1} \bigcap \overline{A_2} \bigcap ... \bigcap \overline A_n

\overline{A_1\bigcap A_2 \bigcap ... \bigcap A_n} = \overline{A_1} \bigcup \overline{A_2} \bigcup ... \bigcup \overline A_n

Example 1:

给定集合N和具有性质i的集合A_1,A_2,...,A_n

多步容斥变形:

\begin{aligned} &\quad|\overline{A_1}\bigcap \overline{A_2}\bigcap...\bigcap \overline{A_n}|\\ &=N\\ &-\sum|A_i|\\ &+\sum|A_i\bigcap A_j|\\ &-\sum|A_i\bigcap A_j \bigcap A_k|\\ &+...\\ &+(-1)^n |A_1\bigcap A_2 \bigcap ... \bigcap A_n| \end{aligned}

补集的补集就是原集:

\begin{aligned} &\quad|A_1\bigcap A_2\bigcap...\bigcap A_n|\\ &=N\\ &-\sum|\overline{A_i}|\\ &+\sum|\overline{A_i} \bigcap \overline{A_j}|\\ &-\sum|\overline{A_i} \bigcap \overline{A_j} \bigcap \overline{A_k}|\\ &+...\\ &+(-1)^n |\overline{A_1}\bigcap \overline{A_2} \bigcap ... \bigcap \overline{A_n}| \end{aligned}

Example 2:

a,b,c,d,e,f六个字母的全排列中不允许出现acedf图象的排列数

N为总排列数,Aace出现的排列数,Bdf出现的排列数

\begin{aligned} ans &=|\overline A \bigcap \overline B|\\ &=|N|-|A|-|B|+|A\bigcap B|\\ &=6!-4!-5!+3!=582 \end{aligned}

Example 3:

4x,3y,2z的全排列中,求不出现xxxx,yyy,zz图象的排列数.

N为总排列集合,出现xxxx的排列集合为A,出现yyyB,出现zzC

\begin{aligned} ans &=\quad|N|\\ &\quad-(|A|+|B|+|C|)\\ &\quad+(|A\bigcap B|+|A\bigcap C|+|B\bigcap C|)\\ &\quad-|A\bigcap B\bigcap C|\\ &=1260-(60+105+280)+(12+20+30)-6=871 \end{aligned}

错排问题

求整数1,2,…,n的全排列中所有i都不在第i个位置上的排列的个数,i=1,2,…,n

A_ii在位置i上的所有排列

\begin{aligned} ans &=|\overline A_1\bigcap \overline A_2 \bigcap ...\bigcap \overline A_n|\\ &=\quad|N|\\ &\quad-(|A_1|+|A_2|+...+|A_n|)\\ &\quad+(|A_1\bigcap A_2|+...+|A_{n-1}\bigcap A_n|)\\ &\quad-\ ...\\ &\quad+ (-1)^n |A_1\bigcap A_2\bigcap ... \bigcap A_n|\\ &=n!- {n\choose 1}\cdot (n-1)! + {n\choose 2}\cdot (n-2)! - ...\ + (-1)^n {n\choose n}\\ &=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}) = D_n\\ \end{aligned}

D_n=n!\sum_{i=0}^n \frac{(-1)^i}{i!}

递推法:

f_x表示错了x

  1. 把第n个数放在[1,n-1]中的某个位置,有n-1种可能

  2. 放第k(k\not=n)个元素

    • 放在位置n,剩余的n-2个元素有f_{n-2}种方法

    • 不放位置n,那么相当于剩下n-1个元素有f_{n-1}种方法

初始:f_1=0,f_2=1

f_n=(n-1)(f_{n-1}+f_{n-2})

HDU 1465 不容易系列之一

第二类斯特林数

n个不同的球放进m个相同的盒子,保证盒子非空,求方案数.

容斥法:

S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i

枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式

由于盒子相同,所以除以m!

递推法

S(n,m)=S(n-1,m-1)+mS(n-1,m)

相当于考虑现在要放的求是否单独在一个盒子里:

  1. 不占一盒:

    其余n-1个球放到m-1个盒子里

  2. 放到某个有球的盒子里:

    m个盒子可放(m种可能),其余n-1个球放到m个盒子里

广义容斥原理

  • 求恰好具有m个属性的元素的个数

\alpha(m)

给定集合N和性质A_1,A_2,...,A_n,令\alpha(0)=|N|

\displaystyle \alpha(1) = \sum|A_i|\\ \alpha(2) = \sum|A_i\bigcap A_j|\\ \alpha(3) = \sum|A_i\bigcap A_j\bigcap A_k|\\ ...\\ \alpha(n) = |A_1\bigcap A_2\bigcap ...\bigcap A_n|\\

\alpha(m)计数了具有m+k个性质的元素{m+k}\choose m

\beta(m)

给定集合N和性质A_1,A_2,...,A_n,令\beta(m)表示N中恰好有m个性质的元素个数,则

\Beta(m)=\alpha(m)-{m+1 \choose m}a(m+1)+{m+2\choose m}\alpha(m+2)-...+(-1)^{n-m}{n\choose m}\alpha(n)

证明:请看下面的二项式反演

推论:\beta(0)=\alpha(0)-\alpha(1)+\alpha(2)-...+(-1)^n\alpha(n)

我们可以发现这个和接下来的二项式反演非常像,如果无法理解可以强行记一下,因为这个非常对称,很好记

二项式反演

  1. 回顾Example 1

    考虑一种特殊情况:多个集合的交集大小只和集合的数目有关

    f_n表示n个补集的交集大小,g_n表示n个原集的大小

    f_n = \sum_{i=0}^n (-1)^i {n\choose i} g_i \\\Updownarrow\\ g_n = \sum_{i=0}^n (-1)^i {n\choose i}f_i

  2. f_i为至多具有i个属性的方案数,g_i表示恰好具有i个属性的方案数:

    f_n=\sum_{i=0}^n{n\choose i} g_i \\ \Updownarrow \\ g_n=\sum_{i=0}^n (-1)^{n-i} {n\choose i}f_i

    f_n表示先钦定n个属性,再统计至多具有这n个属性的方案数(也就是不能有这n个之外的,这n个任意),

    其中会包含重复的方案,因为一个方案可以有多种钦定情况.具体地,对于恰好选择i个,钦定情况数位{n\choose i} ,故g_if_n中被计算了{n\choose i}

  3. f_i为至少具有i个属性,g_i表示恰好具有i个属性的方案数的方案数:

    f_n = \sum_{i=n}^m g_i {i\choose n} \\ \Updownarrow \\ g_n=\sum_{i=n}^m(-1)^{i-n}{i\choose n}f_i

    注意:

    f_n表示先钦定n个属性,再统计至少具有这n个属性的方案数(也就是包含这n个属性,其余属性任意),

    其中会包含重复的方案,因为一个方案可以有多种钦定情况.具体地,对于恰好选择i个,钦定情况数位{i\choose n} ,故g_if_i中被计算了{i\choose n}

  4. tips:

    二项式反演(或广义容斥原理)可以用来解决一些恰好,至多,至少的计数问题

    可以通过容斥来完成恰好,至多,至少之间的互相转换

    是一个很好用的工具

  5. 证明

    至多:

    \begin{aligned} g_n &=\sum_{i=0}^n (-1)^{n-i}{n\choose i}f_i\\ &=\sum_{i=0}^n (-1)^{n-i} {n\choose i}\sum_{j=0}^i{i\choose j}g_j\\ &=\sum_{j=0}^n g_j\sum_{i=j}^n {n\choose i}{i \choose j}(-1)^{n-i}\\ &=\sum_{j=0}^n g_j\sum_{i=j}^n {n\choose j}{n-j \choose i-j}(-1)^{n-i}\\ &=\sum_{j=0}^n g_j\left[{n\choose j}\sum_{i=j}^n{n-j \choose i-j}(-1)^{n-i}\right]\\ &=\sum_{j=0}^n g_j\left[{n\choose j}\sum_{i=0}^{n-j}{n-j \choose i}(-1)^{n-j-i}\right]\\ &=\sum_{j=0}^n g_j\left[{n \choose j}(1-1)^{n-j}\right]\\ &=g_n \end{aligned}

例题

BZOJ 2839 集合计数

地址

题意:

一个有N个元素的集合有2^N个不同子集(包含空集),现在要在这2^N个集合中取出若干集合(至少一个),使得 它们的交集的元素个数为K,求取法的方案数,答案模1000000007

解法:

g_i表示交集个数至少为i的方案数

那么\displaystyle g_i = {n\choose i}(2^{2^{n-i}}-1)

先从n中选i个,然后其他可以随便取

那就是有2^{n-i}个集合可以取

然后又可以取至少1个集合

那么答案就是{n\choose i}(2^{2^{n-i}}-1)

f_i表示恰好为i

那么\displaystyle g_k=\sum_{i=k}^n f_i\cdot {i\choose k}

反演\displaystyle f_k=\sum_{i=k}^n g_i\cdot{i\choose k} (-1)^{i-k}

不能直接快速幂,因为指数不能\mod p,要用2^{2^i}=(2^{2^{i-1}})^2倒着枚举算

#define N 1000011
const int mod=1000000007;
int n,k,g[N],fac[N],inv[N];
int C(int a,int b){
    return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%mod;
        p>>=1;x=1ll*x*x%mod;
    }
    return ans;
}
int main(){
    in(n,k);
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=pw(fac[n],mod-2);
    for(int i=n-1;i>=1;--i)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;

    for(int i=0;i<=n;++i)
        g[i]=1ll*C(n,i)*(pw(2,(pw(2,n-i))-1+mod)%mod)%mod;

    int ans=0,b=2;
    for(int i=n;i>=k;--i){
        int t=1ll*C(n,i)%mod*C(i,k)%mod*(b-1)%mod;
        if((i-k)&1)ans=(ans-t+mod)%mod;
        else ans=(ans+t)%mod;
        b=1ll*b*b%mod;
    }
    printf("%d\n",ans);
}

[JSOI2011]分特产

地址

题意

n个人和m种物品,第i种物品有a_i个,同种物品之间没有区别。现在要将这些物品分给这些人,使得每个人至少分到一个物品

题解

每个同学都必须至少分得一个

可以通过 恰好没有同学没有分得 来反演

f_i为钦定i个人没有分到,

钦定的方案数为{n\choose i},这时第j种物品分给n-i个人,使用隔板法,方案数为{n-i+a_j-1\choose n-i-1}

f_i={n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1}

g_i为恰好i个人没有分到,反演:

g_k=\sum_{i=k}^n(-1)^{i-k}{i \choose k}f_i

那么:

\begin{aligned} ans &=g_0\\ &=\sum_{i=0}^n(-1)^if_i\\ &=\sum_{i=0}^n(-1)^i{n\choose i}\prod_{j=1}^m{n-i+a_j-1\choose n-i-1} \end{aligned}

#include<bits/stdc++.h>
const int N=1001,P=1000000007;
int n,m,a[N],ans,c[N*2][N*2];
void mod(int&x){if(x>=P)x-=P;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<=2000;++i){
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;++j)
            mod(c[i][j]=c[i-1][j-1]+c[i-1][j]);
    }
    for(int i=1;i<=m;++i)scanf("%d",a+i);
    for(int i=0;i<=n;++i){
        long long res=c[n][i];
        for(int j=1;j<=m;++j)
            (res*=c[n-i+a[j]-1][n-i-1])%=P;
        if(i&1)mod(ans+=P-res);
        else mod(ans+=res);
    }
    printf("%d\n",ans);
}

已经没有什么好害怕的了

地址

题意:

给出n个数a_in个数b_i ,要求两两配对使得 a>b的对数减去a<b的对数等于k.

0\leq k\leq n\leq 2000,保证a,b 无相同元素.

题解:

先将b数组从小到大排序

设选中了xa > b,由总对数为n,由x-(n-x)=k,可以知道x=\frac{n+k}2

我们设f(i,j)为前ia中选中了ja > b的方案数

那么f(i,j)=f(i-1,j)+f(i-1,j-1)\times(l_i-j+1)

(l_i表示b中小于a_i的最后一个位置)

但是还有剩下的n-x

我们可以设g_i表示a>b对数\ge i的方案数

那么g_i = f(n,i) \times (n-i)!(相当于剩下的随便排列组合)

我们设f_i表示a>b对数恰好为i对的方案数

那么\displaystyle g_k = \sum_{i=k}^n f_i \times {i\choose k} (相当于从恰好i个方案中选k对出来)

经过二项式反演可以知道:

\displaystyle f(k)=\sum_{i=k}^n(-1)^{i-k}{i\choose k}g(i)

代码:

const int N=4011,mod=1000000009;
int n,k,f[N][N],a[N],b[N],l[N],fac[N],inv[N],g[N];
il int pw(int x,int p){
    int ans=1;
    while(p){
        if(p&1)ans=1ll*ans*x%mod;
        p>>=1;x=1ll*x*x%mod;
    }
    return ans;
}
int C(int a,int b){
    return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}
signed main(){
    in(n,k);
    if((n+k)&1){puts("0");return 0;};
    k=(n+k)>>1;
    for(int i=1;i<=n;++i)in(a[i]);
    for(int i=1;i<=n;++i)in(b[i]);
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;++i)
        fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=pw(fac[n],mod-2);
    for(int i=n-1;i>=0;--i)
        inv[i]=1ll*inv[i+1]*(i+1)%mod;
    sort(a+1,a+n+1);
    sort(b+1,b+n+1);
    int p=0;
    for(int i=1;i<=n;++i){
        while(p<n&&b[p+1]<a[i])++p;
        l[i]=p;
    }
    f[0][0]=1;
    for(int i=1;i<=n;++i){
        f[i][0]=1;
        for(int j=1;j<=i;++j)
            f[i][j]=(f[i-1][j]+1ll*f[i-1][j-1]*MAX(0,l[i]-j+1)%mod)%mod;
    }
    for(int i=0;i<=n;++i)
        g[i]=1ll*f[n][i]*fac[n-i]%mod;
    int ans=0;
    for(int i=k;i<=n;++i)
        if((i-k)&1)ans=(ans-1ll*C(i,k)*g[i]%mod+mod)%mod;
        else ans=(ans+1ll*C(i,k)*g[i]%mod)%mod;

    printf("%d\n",ans);
}

[HAOI2008]硬币购物

地址

题意:

硬币购物一共有4种硬币.面值分别为c1,c2,c3,c4.

某人去商店买东西,去了tot次.

每次带d_ic_i硬币,买s_i的价值的东西.

请问每次有多少种付款方法.

题解:

先考虑每种硬币可以用无数次

f_i表示金额为i有多少种方案

那么\displaystyle f_i = \sum_{j=1}^4 f_{i-c[j](i \ge c_j)}

我们再来考虑硬币使用次数有限制怎么办

不合法的情况有:

1超额

1,2超额

1,3超额

1,4超额

1,2,3超额

1,2,4超额

1,3,4超额

1,2,3,4超额

...

要注意的是在多种硬币限制的情况下可能会减去多次,或加上多次

比如1超额,2超额,(1,2同时超额被减去两次,这是就要加回来

(1,2,3)(1,2,4)又是多算的...

是不是更直观的了解了容斥?

为了方便,我们可以枚举二进制下状态来更加优美实现.

(当有奇数种不合法的时候减去,偶数种不合法时加上)

代码:

#define N 100011
int n,c[5],d[5],s;
ll f[N];
int main(){
    for(int i=1;i<=4;++i)in(c[i]);
    f[0]=1;
    for(int i=1;i<=4;++i)
        for(int j=c[i];j<=100000;++j)
            f[j]+=f[j-c[i]];

    in(n);
    while(n--){
        for(int i=1;i<=4;++i)in(d[i]);
        in(s);
        ll ans=f[s];
        for(int i=1;i<=15;++i){
            int t=s,sta=i,k=1;
            for(int j=1;j<=4;++j)
            if(sta&(1<<(j-1))){
                k=-k;
                t-=(d[j]+1)*c[j];
            }
            if(t>=0)ans+=1ll*f[t]*k;
        }
        out(ans,ln);
    }
}

[SDOI2009]Bill的挑战

地址

题意:

n个长度相同的字符串(由小写字母和?组成):S_1,S_2,...,S_n,

求这n个串中的刚好k个串匹配的字符串T的个数\pmod{1000003}

S_xT匹配,满足:

  1. |S_x|=|T|
  2. \forall S_x[i]=?||S_x[i]=T[i]

状压解法:

f[i][j]表示到了第i位,匹配的状态为j

代码:

#define N 111
#define mod 1000003
#define M(x) ((x>=mod)?(x)%=mod:x)
int mt[N][30];
ll f[N][1<<15];
char ch[N][N];
il void work(){
    clr(mt,0);
    clr(f,0);
    int n,k,len;
    in(n,k);
    for(int i=1;i<=n;++i)in(ch[i]);
    len=strlen(ch[1]);
    for(int i=0;i<=len-1;++i)
        for(char t='a';t<='z';++t)
            for(int j=1;j<=n;++j)
            if(ch[j][i]=='?'||ch[j][i]==t)
                mt[i][t-'a']|=(1<<(j-1));//更新比较当前位的影响
    f[0][(1<<n)-1]=1;
    for(int i=0;i<=len-1;++i)
        for(int j=0;j<(1<<n);++j)
        if(f[i][j])
            for(int t=0;t<=26;++t)
                M(f[i+1][j&mt[i][t]]+=f[i][j]);
    ll ans=0;
    for(int i=0;i<(1<<n);++i){
        int t=i,tt=0;
        while(t)tt+=(t&1),t>>=1;
        if(tt==k)M(ans+=f[len][i]);
    }
    out(ans,ln);
}
int main(){
    int T;in(T);
    while(T--)work();
    flush();
}

容斥解法:

看到恰好k个,我们就可以想到容斥套路

找出至少匹配k个的方案数g(k),设f(k)为恰好k个的方案数

然后还是按套路就可以了

g(n) = \sum_{i=k}^n {n\choose i}f(i) \\ \Updownarrow \\ f(n) = \sum_{i=k}^n {n\choose i}g(i) (-1)^{i-k}

问题转换为如何求至少匹配k个的方案数

我们可以使用dfs来统计,这样比起状压思维难度可能降低了许多,只需要枚举排列组合(当然枚举二进制状态也可以)

状压需要处理全部状态

dfs只需要统计kn的部分

最后统计的时间可忽略不计

状压:492ms

容斥: 100ms

容斥代码:

#define N 111
#define mod 1000003
char ch[N][N];
int len,n,k,cnt,c[N][N],up,tot=0,las,a[N];
void dfs(int x,int now){
    if(x==n+1){
        if(now!=up)return;
        ll lp=1;
        for(int j=1;j<=len;++j){
            las=-1;
            for(int i=1;i<=up;++i)
            if(ch[a[i]][j]!='?'){
                if(las==-1)
                    las=ch[a[i]][j]-'a';
                else if(las!=ch[a[i]][j]-'a')return;
            }
            if(las==-1)lp=(lp*26)%mod;
        }
        (tot+=lp)%=mod;
        return;
    }
    if(now<up){
        a[++cnt]=x;
        dfs(x+1,now+1);
        a[cnt--]=0;
    }
    if(n-x>=up-now)dfs(x+1,now);
}
ll g[N];
il void work(){
    clr(g,0);
    in(n,k);
    for(int i=1;i<=n;++i)in(ch[i]+1);
    len=strlen(ch[1]+1);
    for(int i=k;i<=n;++i)
        up=i;
        tot=0;
        dfs(1,0);
        g[i]=tot;
    }

    // 容斥部分:
    ll ans=0;
    for(int i=k;i<=n;++i)
        if((i-k)&1)ans=(ans-1ll*c[i][k]*g[i]%mod+mod)%mod;
        else ans=(ans+1ll*c[i][k]*g[i]%mod)%mod;
    out(ans,ln);
}
int main(){
    for(int i=0;i<=20;++i){
        c[i][0]=1;
        for(int j=1;j<=i;++j)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    int T;in(T);
    while(T--)work();
    flush();
}

其他有关容斥题目:

Emiya 家今天的饭

地址

题意:

给出一个矩阵,要求每行只能选一个节点,每列选的节点不能超过所有选的节点的一半,不能不选, 给出每个节点的选择方案数,求总方案数

解法:

考虑到限制是每列选择的不能超过一半,我们可以想到不合法的最多只有一列

我们可以用总方案数减去不符合的

\displaystyle s_i=\sum_{j=1}^m a_{ij}

总方案数:\displaystyle \prod_{i=1}^n (s_i+1) - 1

\because k=\frac {tot}2

所以我们有一个很妙的方法:

设选中目标行之外的权值+1,不选+0,选中目标行权值位+2

最后只要权值> n,那么目标行一定被选了超过\frac n2

f(i,k)表示总共选了i次(也就是选到第i行)权值为k的方案数

f(i,k) += f(i-1,k)\cdot(s_i-a_{ij})(当前行不选目标列

f(i,k+1) += f(i-1,k)(当前行完全不选

f(i,k+2) += f(i-1,k)\times a_{ij}(当前行选中目标列

\displaystyle ans = \prod_{i=1}^n (s_i+1) - 1 - \sum_{i=n+1}^{2n} f(n,i)

#include<bits/stdc++.h>
using namespace std;
#define N 111
typedef long long ll;
const int mod=998244353;
int a[N][2011],n,m;
ll f[N][2011],s[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]),
            s[i]=(s[i]+a[i][j])%mod;

    ll ans=1;
    for(int i=1;i<=n;++i)
        ans=(ans*(s[i]+1))%mod;

    --ans;
    for(int j=1;j<=m;++j){
        memset(f,0,sizeof f);
        f[0][0]=1;
        for(int i=1;i<=n;++i)
            for(int k=0;k<=n*2;++k){
                f[i][k]=(f[i][k]+f[i-1][k]*(s[i]-a[i][j]))%mod;
                f[i][k+1]=(f[i][k+1]+f[i-1][k])%mod;
                f[i][k+2]=(f[i][k+2]+f[i-1][k]*a[i][j])%mod;
            }
        for(int i=n+1;i<=n*2;++i)
            ans=(ans-f[n][i])%mod;
    }
    printf("%lld\n",(ans+mod)%mod);
}

LG 2567 [SCOI2010]幸运数字

地址

题意:

定义幸运号码为:由68组成的数字

定义近似幸运号码为:幸运号码的倍数

[l,r]之间幸运数字的个数(1\le l,r \le 10^9).

题解:

先预处理出所有幸运数字

当前要求的是[l,r]中的幸运数字

我们可以使用容斥,用[1,r]-[1,l-1]

假设当前幸运数字为x,[l,r]中是x的倍数的有\left \lfloor \frac rx \right \rfloor - \left \lfloor \frac lx \right \rfloor +1

[1,r],[1,l-1]中的幸运数字的倍数可能有交集

继续容斥:

1-2个的lcm+3个的lcm-...

剪枝:

  1. 可以发现,一个数是另一个合法倍数的倍数,那么这个数字相当于没用(因为被前面的统计过了),可以删掉

  2. 如果将幸运数字从大到小排序,搜索时可以更快突破边界

  3. 现在因为所有数都不满足是另外一个数的倍数,所以合并任意两个数的时候,lcm的最小情况就是乘上一个3,

    所以对于所有>r/3的合法数字,显然不能够和任何一个数合并了,所以这一部分可以拿出来直接提前算好

剩下的直接暴搜

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100011
int tot=0,t=0;
ll ans=0,l,r,a[N];
bool v[N];
inline void init(){
    int h=0;
    while(h<=tot){
        ll x=a[h++]*10;
        if(x+6<=r)a[++tot]=x+6;
        if(x+8<=r)a[++tot]=x+8;
    }
}
const int mod=1000000007;
inline bool chk(ll a,ll b){
    int A=a/mod,B=b/mod;
    if(A*B)return 1;
    return a*b>r;
}
void calc(int x,ll s,int k){
    if(x>tot){
        if(s!=1){
            if(k&1)ans+=r/s-l/s;
            else ans-=r/s-l/s;
        }
        return;
    }
    calc(x+1,s,k);
    ll d=a[x]/__gcd(s,a[x]);
    if(!chk(s,d))calc(x+1,s*d,k+1);
}
inline void work(){
    sort(a+1,a+tot+1);
    for(int i=1;i<=tot;++i)
        for(int j=1;j<i;++j)
        if(a[i]%a[j]==0){
            v[i]=1;
            break;
        }

    for(int i=1;i<=tot;++i)
    if(!v[i]){
        if(a[i]<=r/3)a[++t]=a[i];
        else ans+=r/a[i]-l/a[i];
    }
    tot=t;
    reverse(a+1,a+tot+1);
    calc(1,1,0);
    printf("%lld\n",ans);
}
int main(){
    cin>>l>>r;
    --l;
    init();//找出所有"幸运号码"
    work();
}
容斥与二项式反演
comment评论
Search
search