首页 > 代码库 > D、Homework of PE 容斥原理

D、Homework of PE 容斥原理

2024-09-17 07:00:28   219人阅读

终于想懂了这个容斥，

华工4月23号校赛，
考虑总的所有情况，设1---n里面含有质数的个数为all，需要固定m个质数。那么有

totSum = C(all, m) * (n - m)!，就是在all个质数里面，任意选m个出来固定，剩下的全排。

但是算多了，因为还有一些质数（不在那m个之内）也会被固定，

而且，考虑样例

5 1，

1 2 3 4 5

技术分享

 


这个时候，先考虑任选m个出来固定，题目就是任选1个出来固定。剩下的全排

比如固定了2，剩下的全排，会产生，只固定了2，固定了2、3，固定了2、5，固定了2、3、5

比如固定了3，剩下的全排，会产生，只固定了3，固定了2、3，固定了3、5，固定了2、3、5

比如固定了5，剩下的全排，会产生，只固定了5，固定了2、5，固定了3、5，固定了2、3、5

那么只有第一列相加的才是正确答案。后面的要减去。

减去固定了两个的时候，

这个时候前面一个已经固定了，再枚举一个来固定，就是固定2个。所以固定（3， 2）和（2， 3）是不同的方案。

固定了（2， 3）时，会有，只固定2、3和固定了2、3、5

固定了（3， 2）时，会有，只固定3、2和固定了3、2、5

.....

等等。

减去这些后，会发现结果是ans - 3 * (固定了2、3、5)，加回来就是了。

就是一个容斥，以后容斥要实打实写出来，毕竟不是大神。

哭~~~~

比赛没想到。刚才也想了很久，光想是不行的。要模拟。

技术分享 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>

bool check(int val) {
    int en = (int)sqrt(val);
    for (int i = 2; i <= en; ++i) {
        if (val % i == 0) return false;
    }
    return true;
}
const int MOD = 1e9 + 7;
LL fac[222];
LL quick_pow(LL a, LL b, LL MOD) {  //求解 ab % MOD的值
    LL base = a % MOD;
    LL ans = 1; //相乘，所以这里是1
    while (b) {
        if (b & 1) { //用quick_mul防止Miller_Rabin那里溢出。
            ans = ans * base % MOD;
//            ans = quick_mul(ans, base, MOD); //如果这里是很大的数据，就要用quick_mul
        }
        base = base * base % MOD;
//        base = quick_mul(base, base, MOD);    //notice。每次的base是自己base倍
        b >>= 1;
    }
    return ans;
}

LL C(LL n, LL m, LL MOD) {
    if (n < m) return 0; //防止sb地在循环，在lucas的时候
    if (n == m) return 1 % MOD;
    LL ans1 = 1;
    LL ans2 = 1;
    LL mx = max(n - m, m); //这个也是必要的。能约就约最大的那个
    LL mi = n - mx;
    for (int i = 1; i <= mi; ++i) {
        ans1 = ans1 * (mx + i) %MOD;
        ans2 = ans2 * i % MOD;
    }
    return (ans1 * quick_pow(ans2, MOD - 2, MOD) % MOD); //这里放到最后进行,不然会很慢
}
int n, m;
void work() {
    fac[0] = 1;
    for (int i = 1; i <= 200; ++i) {
        fac[i] = fac[i - 1] * i % MOD;
    }
    int all = 0;
    for (int i = 2; i <= n; ++i) {
        all += check(i);
    }
    LL ans = C(all, m, MOD) * fac[n - m] % MOD;
//    cout << ans << endl;
    for (int i = 1; i <= all - m; ++i) {
        if (i & 1) {
            ans = (ans + MOD - C(all, m, MOD) * C(all - m, i, MOD) * fac[n - (m + i)] % MOD) % MOD;
        } else ans = (ans + C(all, m, MOD) * C(all - m, i, MOD) * fac[n - (m + i)] % MOD) % MOD;
    }
    cout << ans % MOD << endl;
}

int main() {
    freopen("data.txt", "r", stdin);
freopen("DataMy.txt", "w", stdout);
    while (~scanf("%d%d", &n, &m))
        work();
    return 0;
}
View Code

 

D、Homework of PE 容斥原理


联系
我们