相關(guān)概念?

離散數(shù)學(xué)中的容斥原理是一種使用集合運(yùn)算的技巧，通常用于計算兩個或更多集合的并集或交集的大小。以下是一些與容斥原理相關(guān)的常見概念和公式。

概念：

1. 集合：由元素組成的對象，通常用大寫字母表示，如A、B、C等。

2. 元素：集合中的單個對象，通常用小寫字母表示，如a、b、c等。

3. 包含關(guān)系：如果一個集合A的所有元素都在另一個集合B中，那么稱A是B的子集（或包含于B），用A?B表示。

4. 交集：兩個集合A和B的交集是由同時屬于A和B的元素組成的集合，用A∩B表示。

5. 并集：兩個集合A和B的并集是由屬于A或B（或同時屬于A和B）的元素組成的集合，用A∪B表示。

6. 補(bǔ)集：集合A的補(bǔ)集是由不屬于A的元素組成的集合，用Ac表示。

公式：

1. 容斥原理公式：對于兩個集合A和B，有：

|A ∪ B| = |A| + |B| - |A ∩ B|

其中，|A|表示集合A的元素個數(shù)，|A∪B|表示集合A和B的并集的元素個數(shù)，|A∩B|表示集合A和B的交集的元素個數(shù)。

2. 三個集合的容斥原理公式：對于三個集合A、B和C，有：

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

其中，|A|表示集合A的元素個數(shù)，|A∪B∪C|表示集合A、B和C的并集的元素個數(shù)，|A∩B|表示集合A和B的交集的元素個數(shù)，以此類推。

1.?(程序題)錯排

在n個字母的全排列中，使得每個字母都不在原來位置的排列數(shù)是多少？請使用錯位排列的遞推公式來計算本題。

Input

輸入數(shù)據(jù)有多組，每組有1個正整數(shù)n(1<=n<=10),代表字母的個數(shù)。

Output

在一行內(nèi)輸出這n個字母都不在原來位置的方法數(shù)。

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個元素的錯位排列的個數(shù)。

公式的含義是，將第n個元素固定在某個位置上，那么剩下的n-1個元素的錯位排列個數(shù)為D(n-1)；將第n個元素固定在其他位置上，那么剩下的n-1個元素的錯位排列個數(shù)為D(n-2)。所以，將這兩種情況相加，并乘以(n-1)，即可得到n個元素的錯位排列個數(shù)。

根據(jù)這個公式，可以通過遞推的方式計算錯位排列的個數(shù)。初始條件為D(1) = 0, D(2) = 1。

?2.?(程序題)歐拉函數(shù)值

對于一個正整數(shù)n，求出它的歐拉函數(shù)值，其中1<n<=100000000

Input

輸入數(shù)據(jù)有多組，每組數(shù)據(jù)一行，有1個正整數(shù)為n。

Output

輸出n的歐拉函數(shù)的值

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;
}

?歐拉函數(shù)，也稱為φ函數(shù)，表示小于等于n且與n互質(zhì)的正整數(shù)的個數(shù)。其中，互質(zhì)的定義是兩個數(shù)的最大公約數(shù)為1。

歐拉函數(shù)的公式為：

φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)

其中，n是正整數(shù)，p1, p2, ..., pk是n的所有質(zhì)因數(shù)。這個公式的意義是，將n分解為質(zhì)因數(shù)的乘積，然后對于每個質(zhì)因數(shù)pi，將n中所有包含pi的因子都去掉，剩下的因子個數(shù)就是與n互質(zhì)的正整數(shù)個數(shù)。最后將所有質(zhì)因數(shù)的貢獻(xiàn)相乘，就得到了歐拉函數(shù)的值。

例如，對于n=10，它的質(zhì)因數(shù)分解為10=2×5，因此有：

φ(10) = 10 × (1 - 1/2) × (1 - 1/5) = 4

即小于等于10且與10互質(zhì)的正整數(shù)個數(shù)為4，它們是1、3、7、9。

?3.?(程序題)考新郎

國慶期間,省城HZ剛剛舉行了一場盛大的集體婚禮,為了使婚禮進(jìn)行的豐富一些,司儀臨時想出了有一個有意思的節(jié)目,叫做"考新郎",具體的操作是這樣的:首先,給每位新娘打扮得幾乎一模一樣,并蓋上大大的紅蓋頭隨機(jī)坐成一排;然后,讓各位新郎尋找自己的新娘.每人只準(zhǔn)找一個,并且不允許多人找一個.最后,揭開蓋頭,如果找錯了對象就要當(dāng)眾跪搓衣板...看來做新郎也不是容易的事情...假設(shè)一共有N對新婚夫婦,其中有M個新郎找錯了新娘,求發(fā)生這種情況一共有多少種可能.

Input

輸入數(shù)據(jù)的第一行是一個整數(shù)C,表示測試實(shí)例的個數(shù)，然后是C行數(shù)據(jù)，每行包含兩個整數(shù)N和M(1<M<=N<=40)。

Output

對于每個測試實(shí)例，請輸出一共有多少種發(fā)生這種情況的可能，每個實(shí)例的輸出占一行。

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;elsea[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;
}

利用容斥原理，我們可以將問題轉(zhuǎn)化為求解有多少種情況滿足至少有一個新郎找錯的情況，然后再減去有兩個新郎找錯的情況，再加上有三個新郎找錯的情況，依此類推，直到加上有M個新郎找錯的情況。?

首先，考慮只有一個新郎找錯的情況。假設(shè)第i個新郎找錯了新娘，那么他有N-1種選擇，剩下的N-1對夫婦中有M-1對新郎找錯。所以，只有一個新郎找錯的情況一共有C(N-1,1) * C(N-1, M-1)種可能。

然后，考慮有兩個新郎找錯的情況。假設(shè)第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)種可能。

最后，我們將所有情況累加起來，就可以得到發(fā)生這種情況的總數(shù)。

?