新浪博客怎么给自己网站做链接,wordpress壁纸,可以做ppt的网站,中国软文网相关概念 离散数学中的容斥原理是一种使用集合运算的技巧#xff0c;通常用于计算两个或更多集合的并集或交集的大小。以下是一些与容斥原理相关的常见概念和公式。 概念#xff1a; 1. 集合#xff1a;由元素组成的对象#xff0c;通常用大写字母表示#xff0c;如A、B、…相关概念 离散数学中的容斥原理是一种使用集合运算的技巧通常用于计算两个或更多集合的并集或交集的大小。以下是一些与容斥原理相关的常见概念和公式。 概念 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(1n10),代表字母的个数。 Output 在一行内输出这n个字母都不在原来位置的方法数。 Sample Input 2 Sample Output 1 #include iostreamusing 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求出它的欧拉函数值其中1n100000000 Input 输入数据有多组每组数据一行有1个正整数为n。 Output 输出n的欧拉函数的值 Sample Input 5 100 Sample Output 4 40 #include iostreamusing 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互质的正整数个数。最后将所有质因数的贡献相乘就得到了欧拉函数的值。 例如对于n10它的质因数分解为102×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(1MN40)。 Output 对于每个测试实例请输出一共有多少种发生这种情况的可能每个实例的输出占一行。 Sample Input 2 2 2 3 2 Sample Output 1 3 #include iostreamusing namespace std;long long jiecheng(int n){int x1,i;while(n!0){xx*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];}}cinn;for(j0;jn;j){cinNM;sum0;flag1;for(i2;iM;i){xjiecheng(M)/jiecheng(i);sumsumflag*x;flagflag*(-1);}resultsum*a[N][M];coutresultendl;}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)种可能。 最后我们将所有情况累加起来就可以得到发生这种情况的总数。
