首页 > 代码库 > HDU 2068 RPG的错排

HDU 2068 RPG的错排

2024-07-12 09:25:31   221人阅读

要求答对一半或以上就算过关，请问有多少组答案能使他顺利过关。

逆向思维，求答错一半或以下的组数

1，错排

错排公式的由来

　　pala提出的问题: 十本不同的书放在书架上。现重新摆放，使每本书都不在原来放的位置。有几种摆法？
　　这个问题推广一下，就是错排问题: n个有序的元素应有n！种不同的排列。如若一个排列式的所有的元素都不在原来的位置上，则称这个排列为错排。
递推的方法推导错排公式

　　当n个编号元素放在n个编号位置,元素编号与位置编号各不对应的方法数用M(n)表示,那么M(n-1)就表示n-1个编号元素放在n-1个编号位置,各不对应的方法数,其它类推.
　　第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
　　第二步,放编号为k的元素,这时有两种情况.1,把它放到位置n,那么,对于剩下的n-2个元素,就有M(n-2)种方法;2,不把它放到位置n,这时,对于这n-1个元素,有M(n-1)种方法;
　　综上得到
　　M(n)=(n-1)[M(n-2)+M(n-1)]
　　特殊地，M(1)=0,M(2)=1

2，组合

答对 i 个人，即答错 n - i 个人，共有C(n, n - i) * M[n - i] 组答案

其中C(n, n - i) 就是从 n 个人选出 n - i 个人的组合数

代码如下：

 

#include<stdio.h>#include<iostream>using namespace std;__int64 f[15] = {1, 0};void init(){    for(int i = 2; i <= 14; i ++)        f[i] = (i - 1) * (f[i - 1] + f[i - 2]);//i 个人全错排的组数}__int64 C(int n, int m){    __int64 s = 1;    for(int i = 1; i <= m; i ++)        s = s * (n - i + 1) / i;//乘后立即除，防止溢出，但不可写成s *= (n - i + 1) / i,(n - i + 1) / i 这个表达式有可能不能整除    return s;                               //导致结果变小}int main(){    init();    int n;    while(~scanf("%d", &n), n)    {        __int64 sum = 0;        for(int i = 0; i <= n / 2; i ++) //组合，从n个人选i个让她们错排，则是猜对了n - i个MM，i从0到n/2，求的是猜对n到n/2个MM的组数            sum += C(n, i) * f[i];        cout <<sum <<endl;    }    return 0;}
View Code


联系
我们