天天看點
傳回

容斥原理訓練 (16.04.10)

這又是一篇訓練系列的博文，主題是容斥原理。

題目：

UVA 10325 A - The Lottery

poj 3904 Sky Code

uvalive 7040 color

hdu 4059 The Boss on Mars

H - Visible Trees

UVA 10325 A - The Lottery

​​https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1266​​​

大意：給出一堆數字A，求在1-N内不被A中任意一個數字整除的個數。

分析：看到第二個樣例，瞬間覺得不簡單。假設這樣一個例子：N=25, A=(6,8)

6：6、12、18、24

8：8、16、24

那麼既能被6整除又能被8整除的數（最小數）難道是 6*8=48：0 嗎？

顯然這是不對的，既能被6整除又能被8整除的最小正整數該是24——最大公約數

多寫寫樣例測試自己的程式很重要！！

poj 3904 Sky Code

​​http://poj.org/problem?id=3904​​​

大意：求得在n個數字中最大公約數是1的四元組的個數

分析：正着求解是肯定不行的，逆向求解——容斥原理。用所有的素因子去求解所有的倍數，如果有四個數字的最大公約數是大于1的，那麼一定存在素因子的組合是最大公約數的因子。是以對每一個數字素因子分解，記錄每個因子，統計每個因子在這n個數中出現的次數和其素因子的組合個數。然後容斥，求出所有的非1四元組個數，最後總數減去它即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N=10010;
LL record[N],sum[N];
LL calc(LL n){
    return 1LL*n*(n-1)*(n-2)*(n-3)/4/3/2;
}
LL fac[N],top;
void solve(LL n){
    top=0;
    for(LL i=2;i*i<=n;i++){
        if(n%i==0){
            fac[top++]=i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) fac[top++]=n;
}
int main(int argc, char *argv[]) {
    LL n,w;
    while(~scanf("%lld",&n)){
        memset(record,0,sizeof(record));
        memset(sum,0,sizeof(sum));
        LL maxs=0;
        for(LL i=0;i<n;i++){
            scanf("%lld",&w);
            solve(w);
            for(LL j=1;j<(1<<top);j++){
                LL g=0,s=1;
                for(LL k=0;k<top;k++){
                    if(j&(1<<k)) {
                        g++;
                        s=s*fac[k];
                    }
                }
                sum[s]=g;
                maxs=maxs>s?maxs:s;
                record[s]++;
            }
        }
        LL ans=calc(n),temp=0;
        for(LL i=1;i<=maxs;i++){
             if(sum[i]>0){
                 if(sum[i]&1) temp=temp+calc(record[i]);
                 else temp=temp-calc(record[i]);
             }
        }
        ans=ans-temp;
        printf("%lld\n",ans);
    }
    return 0;
}

uvalive 7040 color

​​https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5052​​​

大意：N個物品排成一列，現在有m種顔色，從中選出k種顔色。要求相鄰物品顔色不同地塗色。

分析：首先從m種顔色中選出k種顔色，Ckm

兩兩不同的塗色：第一個物品塗色k種選擇,，第二個物品塗色k-1種選擇，第三個物品塗色k-1種選擇……是以，得到Ckmk(k−1)n−1，但是這樣的結果還包含了隻用2種顔色塗色，隻用3種顔色塗色，隻用4種顔色塗色……用k-1種顔色塗色。是以，我們需要除去這些不相幹的情況。是以在選出k種顔色，Ckm後，要再考慮Ciki(i−1)n−1 的情況，同時Ciki(i−1)n−1又涉及到新的子集問題（我們不能直接Ckmk(k−1)n−1−CkmCk−1k(k−1)(k−2)n−1 因為有選擇的步驟Cmn ),什麼能解決這種樹葉的投影類問題呢？容斥原理。

設f(i)=Ciki(i−1)n−1

如k=5時，C5m(f(1)−f(2)+f(3)−f(4)+f(5))

k=4時，C4m(−f(1)+f(2)−f(3)+f(4))

即，括号裡一定是 f(n)−f(n−1)+f(n−2)−f(n−3)⋯f(1)

注意：能預處理的預處理，不要造成不必要的多重循環，以免TLＥ。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL N=1e6+10,mod=1e9+7;
LL C1[N],C2[N],inv[N],p[N];
LL power(LL a,LL p){
    LL ans=1;
    while(p){
        if(p&1) ans=ans*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return ans;
}
void init(LL C[],LL n,LL m){
    C[0]=1;   C[1]=n;
    for(int i=2;i<=m;i++){
        //LL ni=power(i,mod-2);
        C[i]=C[i-1]*(n-i+1)%mod*inv[i]%mod;
    }
}
int main()
{
    for(int i=1;i<N;i++)  inv[i]=power(i,mod-2);  // 預處理，乘法變加法 for less time
    int t,ca=1;
    cin>>t;
    while(t--){
         LL n,m,k;
         scanf("%lld %lld %lld",&n,&m,&k);
         init(C1,m,k);
         init(C2,k,k);
         LL ans=C2[k]*k%mod*power(k-1,n-1)%mod;
         LL temp=0;
         for(int i=1;i<k;i++){
             p[i-1]=power(i-1,n-1);
         }
         for(int i=1;i<k;i++){
             //if(i&1) temp=(temp+C2[i]*i%mod*power(i-1,n-1))%mod;
             //else temp=(temp-C2[i]*i%mod*power(i-1,n-1)+mod)%mod;
             if(i&1) temp=(temp+C2[i]*i%mod*p[i-1]%mod)%mod;
             else temp=(temp-C2[i]*i%mod*p[i-1]%mod+mod)%mod;
         }
         if((k&1)==0)ans=(ans-temp+mod)%mod;
         else ans=(ans+temp)%mod;
         ans=ans*C1[k]%mod;
         printf("Case #%d: %lld\n",ca++,ans);
    }
    return 0;
}

hdu 4059 The Boss on Mars

​​http://acm.hdu.edu.cn/showproblem.php?pid=4059​​

大意： 求出 ∑x=1kx4 其中x和n互質

幾個常用的求和公式：

∑x=1nx2=n(n+1)(2n+1)6∑x=1nx3=n2(n+1)24∑x=1nx4=n(n+1)(2n+1)(3n2+3n−1)30

他們均能由牛頓二項展開式+列項相消推出。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const LL N=1e4+10,mod=1e9+7;
LL fac[N],top;
void solve(LL n){
    top=0;
    for(LL i=2;i*i<=n;i++){
        if(n%i==0){
            fac[top++]=i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) fac[top++]=n;
}
LL quick(LL a,LL p){
    LL ans=1;
    while(p){
        if(p&1) ans=ans*a%mod;
        a=a*a%mod;
        p>>=1;
    }
    return ans;
}
LL ni;
LL sum(LL n){
    return n*(n+1)%mod*(2*n%mod+1)%mod*(3*n*n%mod+3*n%mod-1)%mod*ni%mod;
}
int main()
{
    LL t,n;
    ni=quick(30,mod-2);
    cin>>t;
    while(t--){
        scanf("%I64d",&n);
        solve(n);
        LL ans=sum(n);
        LL t=0;
        for(LL i=1;i<(1<<top);i++){
            LL g=0,s=1;
            for(LL j=0;j<top;j++){
                if(i&(1<<j)){
                    g++;
                    s=s*fac[j]%mod;
                }
            }  // s*fac[j]*fac[j]%mod*fac[j]%mod*fac[j]%mod*sum(n/fac[j])%mod
            LL temp=s*s%mod*s%mod*s%mod*sum(n/s)%mod;
            if(g&1) t=(t+temp)%mod;
            else t=(t-temp+mod)%mod;
        }
        ans=(ans-t+mod)%mod;
        printf("%I64d\n",ans);
    }
    return 0;
}

hdu 2841 - Visible Trees 

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+10;
typedef long long LL;
LL phi[N];
void init(){
    for(LL i=1;i<N;i++) phi[i]=i;
    for(LL i=2;i<N;i++){
        if(phi[i]==i) {
            for(LL j=i;j<N;j+=i){
                phi[j]=phi[j]-phi[j]/i;
            }
        }
    }
}
LL fac[N/10],top;
void solve(LL n){
    top=0;
    for(LL i=2;i*i<=n;i++){
        if(n%i==0){
            fac[top++]=i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) fac[top++]=n;
}
int main()
{
    init();
    LL t,m,n;
    cin>>t;
    while(t--){
        scanf("%lld%lld",&m,&n);
        if(m>n){
            m=m^n;  n=m^n;  m=m^n;
        }
        LL ans=0;
        for(LL i=2;i<=m;i++){
            ans=ans+phi[i];
        }
        ans=ans<<1;
        ans++;
        for(LL i=m+1;i<=n;i++){
            solve(i);
            LL temp=0;
            for(LL j=1;j<(1<<top);j++){
                LL s=1,g=0;
                for(LL k=0;k<top;k++){
                    if(j&(1<<k)){
                        g++;
                        s=s*fac[k];
                    }
                }
                if(g&1) temp+=m/s;
                else temp-=m/s;
            }
            ans=ans+m-temp;
        }
        printf("%lld\n",ans);
    }
    return 0;
}
容斥 組合 i++ #include 整除
上一篇: 用usb安裝ubuntu server 10.04
下一篇: 在Ubuntu下安裝VMware Tools導緻滑鼠滾輪不能用的問題的解決方法

繼續閱讀