NEFU离散数学实验2-容斥原理

怼烎@ 2024-04-17 13:36 77阅读 0赞

#### 相关概念 ####

> 离散数学中的容斥原理是一种使用集合运算的技巧，通常用于计算两个或更多集合的并集或交集的大小。以下是一些与容斥原理相关的常见概念和公式。
> 
> 概念：
> 
> 1. 集合：由元素组成的对象，通常用大写字母表示，如A、B、C等。
> 
> 2. 元素：集合中的单个对象，通常用小写字母表示，如a、b、c等。
> 
> 3. 包含关系：如果一个集合A的所有元素都在另一个集合B中，那么称A是B的子集（或包含于B），用A⊆B表示。
> 
> 4. 交集：两个集合A和B的交集是由同时属于A和B的元素组成的集合，用A∩B表示。
> 
> 5. 并集：两个集合A和B的并集是由属于A或B（或同时属于A和B）的元素组成的集合，用A∪B表示。
> 
> 6. 补集：集合A的补集是由不属于A的元素组成的集合，用Ac表示。
> 
> 公式：
> 
> 1. 容斥原理公式：对于两个集合A和B，有：
> 
> |A ∪ B| = |A| + |B| - |A ∩ B|
> 
> 其中，|A|表示集合A的元素个数，|A∪B|表示集合A和B的并集的元素个数，|A∩B|表示集合A和B的交集的元素个数。
> 
> 2. 三个集合的容斥原理公式：对于三个集合A、B和C，有：
> 
> |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|
> 
> 其中，|A|表示集合A的元素个数，|A∪B∪C|表示集合A、B和C的并集的元素个数，|A∩B|表示集合A和B的交集的元素个数，以此类推。

#### 1. (程序题)错排 ####

> 在n个字母的全排列中，使得每个字母都不在原来位置的排列数是多少？请使用错位排列的递推公式来计算本题。
> 
> Input
> 
> 输入数据有多组，每组有1个正整数n(1<=n<=10),代表字母的个数。
> 
> Output
> 
> 在一行内输出这n个字母都不在原来位置的方法数。
> 
> Sample Input
> 
> 2
> 
> Sample Output
> 
> 1

#include <iostream>
    
    using namespace std;
    
    long long jiecheng(int n)
    {
        long long x = 1;
        for (int i = 2; i <= n; i++)
        {
            x *= i;
        }
        return x;
    }
    
    int main()
    {
        int n;
        while (cin >> n)
        {
            long long sum = 0;
            for (int i = 2; i <= n; i++)
            {
                long long x = jiecheng(n) / jiecheng(i);
                sum += (i % 2 == 0) ? x : -x;
            }
            cout << sum << endl;
        }
        return 0;
    }

> 错位排列的递推公式是：
> 
> D(n) = (n-1) \* (D(n-1) + D(n-2))
> 
> 其中，D(n)表示n个元素的错位排列的个数。
> 
> 公式的含义是，将第n个元素固定在某个位置上，那么剩下的n-1个元素的错位排列个数为D(n-1)；将第n个元素固定在其他位置上，那么剩下的n-1个元素的错位排列个数为D(n-2)。所以，将这两种情况相加，并乘以(n-1)，即可得到n个元素的错位排列个数。
> 
> 根据这个公式，可以通过递推的方式计算错位排列的个数。初始条件为D(1) = 0, D(2) = 1。

#### 2. (程序题)欧拉函数值 ####

> 对于一个正整数n，求出它的欧拉函数值，其中1<n<=100000000
> 
> Input
> 
> 输入数据有多组，每组数据一行，有1个正整数为n。
> 
> Output
> 
> 输出n的欧拉函数的值
> 
> Sample Input
> 
> 5
> 
> 100
> 
> Sample Output
> 
> 4
> 
> 40

#include <iostream>
    
    using namespace std;
    
    int eulerPhi(int n) {
        int result = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                while (n % i == 0)
                    n /= i;
                result -= result / i;
            }
        }
        if (n > 1)
            result -= result / n;
        return result;
    }
    
    int main() {
        int n;
        while (cin >> n) {
            int phi = eulerPhi(n);
            cout << phi << endl;
        }
        return 0;
    }

> 欧拉函数，也称为φ函数，表示小于等于n且与n互质的正整数的个数。其中，互质的定义是两个数的最大公约数为1。
> 
> 欧拉函数的公式为：
> 
> φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)
> 
> 其中，n是正整数，p1, p2, ..., pk是n的所有质因数。这个公式的意义是，将n分解为质因数的乘积，然后对于每个质因数pi，将n中所有包含pi的因子都去掉，剩下的因子个数就是与n互质的正整数个数。最后将所有质因数的贡献相乘，就得到了欧拉函数的值。
> 
> 例如，对于n=10，它的质因数分解为10=2×5，因此有：
> 
> φ(10) = 10 × (1 - 1/2) × (1 - 1/5) = 4
> 
> 即小于等于10且与10互质的正整数个数为4，它们是1、3、7、9。

#### 3. (程序题)考新郎 ####

> 国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.最后,揭开盖头,如果找错了对象就要当众跪搓衣板...看来做新郎也不是容易的事情...假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
> 
> Input
> 
> 输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1<M<=N<=40)。
> 
> Output
> 
> 对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。
> 
> Sample Input
> 
> 2
> 
> 2 2
> 
> 3 2
> 
> Sample Output
> 
> 1
> 
> 3

#include <iostream>
    
    using namespace std;
    
    long long jiecheng(int n){
    
        int x=1,i;
    
        while(n!=0){
    
            x=x*n;
    
            n--;
    
        }
    
        return x;
    
    }
    
    
    int main()
    
    {
        long long n,sum,flag,i,x,result,N,M,j;
    
        long long a[45][45]={0};
    
        a[1][1]=a[1][0]=1;
    
        for (i = 2; i < 41; i++){
    
            for (j = 0; j <= i; j++){
    
                if (j == 0)
    
                    a[i][j] = 1;
    
                else
    
                    a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
    
            }
    
        }
    
        cin>>n;
    
        for(j=0;j<n;j++){
    
            cin>>N>>M;
    
            sum=0;
    
            flag=1;
    
            for(i=2;i<=M;i++){
    
                x=jiecheng(M)/jiecheng(i);
    
                sum=sum+flag*x;
    
                flag=flag*(-1);
    
            }
            result=sum*a[N][M];
    
            cout<<result<<endl;
        }
        return 0;
    }

> 利用容斥原理，我们可以将问题转化为求解有多少种情况满足至少有一个新郎找错的情况，然后再减去有两个新郎找错的情况，再加上有三个新郎找错的情况，依此类推，直到加上有M个新郎找错的情况。
> 
> 首先，考虑只有一个新郎找错的情况。假设第i个新郎找错了新娘，那么他有N-1种选择，剩下的N-1对夫妇中有M-1对新郎找错。所以，只有一个新郎找错的情况一共有C(N-1,1) \* C(N-1, M-1)种可能。
> 
> 然后，考虑有两个新郎找错的情况。假设第i个新郎和第j个新郎找错了新娘，那么他们有N-2种选择，剩下的N-2对夫妇中有M-2对新郎找错。所以，有两个新郎找错的情况一共有C(N-2,2) \* C(N-2, M-2)种可能。
> 
> 依此类推，我们可以得到有k个新郎找错的情况一共有C(N-k,k) \* C(N-k, M-k)种可能。
> 
> 最后，我们将所有情况累加起来，就可以得到发生这种情况的总数。