2018全国多校算法寒假练习赛(三) G

Link

https://www.nowcoder.net/acm/contest/75/G

type: 容斥定理,1~n整数倍定理

题意

给你一个n(1~1e18 long long 范围内),问你1~n中不为2,5,1,,13倍数的数有多少个.

题解

1.我忘了一个定理:

设求: 1~n之间有多少个数是给定的x的倍数?

答案为 n/x

有了以上那个定理就好求了,设条件 A 为1~n中2的倍数,B 为1~n中5的倍数,C,D.
则答案就是:

|(~A)∩(~B)∩(~C)∩(~D)|

标准容斥,情况只有2^4-1=15种,写代码吧

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve(LL N){
    LL ans=N;
    LL k[4]={2,5,11,13};
    for(int seq=1;seq<16;++seq){
        LL reg=1;
        int d=0;
        if(seq&1) reg*=k[0],d++;
        if(seq&2) reg*=k[1],d++;
        if(seq&4) reg*=k[2],d++;
        if(seq&8) reg*=k[3],d++;
        if(d&1) ans-=(N/reg);
        else ans+=(N/reg);
    }
    printf("%lld\n",ans);
}

int main(){
    LL n;
    while(cin>>n){
        solve(n);
    }
    return 0;
}

UVa 11806

Link

https://vjudge.net/problem/UVA-11806

Type:

组合数学,排列预处理,容斥原理,减法取模公式

题意

给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,

问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解

我们可以将问题转化为:

全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为

C((m-2)*(n-2),k).

我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,D为下边没有石子.

则(我们设~A为非A集合):

ans=|(~A)∩(~B)∩(~C)∩(~D)|

可以发现就是容斥原理
至于每个集合的计算,在图中就相当于少了一行或一列,
即:

C(row*column,k)

因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示

0000
0001
0010

我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0

答案为全部的和.

Code

/*
Link: https://vjudge.net/problem/UVA-11806
Type: 组合数学,排列预处理,容斥原理,减法取模公式
题意: 给你一个M*N(M行N列)的棋盘和k个相同的石子,每个格子最多放一个石子,
问最上边,最左边,最下边,最右边都有石子的种数为多少?

题解:
我们可以将问题转化为:
全集|S|-至少有一条边上没有棋子的种类个数.
并且我们可以发现,当四条边上都没有棋子时的种类个数为
C((m-2)*(n-2),k).
我们设A最左边没有石子,B为上边没有石子,C为右边没有石子,
D为下边没有石子.
则(我们设~A为非A集合):
ans=|(~A)∩(~B)∩(~C)∩(~D)|
可以发现就是容斥原理
至于每个几何的计算,在图中就相当于少了一行或一列,
即:
C(row*column,k)
因为有: Sigma(i=1~4) C(4,i) = 2^4 = 16 种可能
即 可以用四位2进制表示
0000
0001
0010
我们设四位如下排列: (最左(减列),最上(减行),最右(减列),最下(减行))
等全部情况,在容斥中,其中1为奇数个时符号位是-,偶数是0
答案为全部的和.
*/
#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7;
int T;

const int MAXK=500;
int C[MAXK+10][MAXK+10];
void init(){
    memset(C,0,sizeof(C));
    C[0][0]=1;
    for(int i=0;i<=MAXK;++i){
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;++j){
            //组合的一个递推公式
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
}

int main(){
    init();
    cin>>T;
    for(int kase=1;kase<=T;++kase){
        int n,m,k;
        cin>>n>>m>>k;
        int sum=0;
        for(int i=0;i<16;++i){
            int nn=n,mm=m;
            int b=0;
            if(i&1){mm--;b++;}
            if(i&2){nn--;b++;}
            if(i&4){mm--;b++;}
            if(i&8){nn--;b++;}
            //奇数-偶数+
            if(b&1) sum=(sum+mod-C[nn*mm][k])%mod;
            else sum=(sum+C[nn*mm][k])%mod;
        }
        cout<<"Case "<<kase<<": "<<sum<<endl;
    }
    return 0;
}

CSU 1803

类型: 容斥,唯一分解定理
题目连接: :earth_americas:CSU-1803

题解: 由素分可以得到

2016=2*2*2*2*2*3*3*7 所以我们可以判断出 a 中有多少2016的因子,然后算出b中与a至少互补的因子个数,利用容斥原理计算出最后的结果.

github: :moon:1803.cpp

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long LL;
LL arr[10][10][10];
LL a,b;
int main(){
    ///2016=2*2*2*2*2*3*3*7

    while(~scanf("%lld%lld",&a,&b)){
        memset(arr,0,sizeof(arr));
        for(int i=0;i<6;++i)
            for(int j=0;j<3;++j)
                for(int t=0;t<2;++t)
                    arr[i][j][t]=a/(int)(pow(2,i)*pow(3,j)*pow(7,t));
        LL ans=0;
        for(int i=0;i<6;++i)
            for(int j=0;j<3;++j)
                for(int t=0;t<2;++t)
                    ans+=(arr[i][j][t]-arr[i+1][j][t]-arr[i][j+1][t]-arr[i][j][t+1]+arr[i+1][j+1][t]+arr[i+1][j][t+1]+arr[i][j+1][t+1]-arr[i+1][j+1][t+1])*(b/(int)(pow(2,5-i)*pow(3,2-j)*pow(7,1-t)));
        printf("%lld\n",ans);
    }
    return 0;
}