组合数学第二发错排问题 hdu 2049 + hdu 2068

错排问题是说N个元素对应N个位置上，但是元素编号与位置编号各不对应的方法数，即错排数，用 M ( N ) 表示。

对应公式 M ( N ) = ( N - 1 ) * [ M ( N - 1 ) + M ( N - 2 ) ] 。

N - 1表示第N个元素可以选择1 ~ N - 1 共 N - 1 个位置，假设第N个元素放在了第K个位置。

接下来分两种情况。

1）把第K个元素放在了位置N，此时，剩下的 N - 2 个元素进行错排，错排数为 M ( N - 2 ) 。

2）不把第K个元素放在位置N，即把位置N视为元素K的对应位置，将N - 1 个元素进行错排，错排数为 M ( N - 1 )。

hdu 2049 不容易系列之(4) 考新郎

国庆期间,省城HZ刚刚举行了一场盛大的集体婚礼,为了使婚礼进行的丰富一些,司仪临时想出了有一个有意思的节目,叫做"考新郎",具体的操作是这样的:

首先,给每位新娘打扮得几乎一模一样,并盖上大大的红盖头随机坐成一排;
然后,让各位新郎寻找自己的新娘.每人只准找一个,并且不允许多人找一个.
最后,揭开盖头,如果找错了对象就要当众跪搓衣板...

看来做新郎也不是容易的事情...

假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.

Input

输入数据的第一行是一个整数C,表示测试实例的个数，然后是C行数据，每行包含两个整数N和M(1

Output

对于每个测试实例，请输出一共有多少种发生这种情况的可能，每个实例的输出占一行。

Sample Input

2
2 2
3 2

Sample Output

1
3

排列组合问题，C ( n , m ) * M ( m ) 即从n个元素中找出m个元素并对这m个元素进行错排。

#include
   
    
#include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #define PI acos(-1.0) #define maxn 160 #define INF 1<<25 typedef long long ll; using namespace std; __int64 num[25]; __int64 jiecheng[25]; __int64 init() { num[0]=1; num[1]=0; num[2]=1; for(int i=3;i<=20;i++) { num[i]=(i-1)*(num[i-2]+num[i-1]); } } __int64 init2() { __int64 aa=1; jiecheng[0]=1; for(int i=1;i<=20;i++) { aa*=i; jiecheng[i]=aa; } } int main() { init(); init2(); int tot; scanf("%d",&tot); int ii,jj; for(int i=0;i
              
               
 
               
 
                
               hdu 2068 RPG的错排 
                今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜，第一次猜：R是公主，P是草儿，G是月野兔；第二次猜：R是草儿，P是月野兔，G是公主；第三次猜：R是草儿，P是公主，G是月野兔；......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动，做ACM的女生越来越多，我们的野骆驼想都知道她们，可现在有N多人，他要猜的次数可就多了，为了不为难野骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。 
                Input 输入的数据里有多个case,每个case包括一个n，代表有几个女生，（n<=25）, n = 0输入结束。 
                Output 
               1
1 
                Sample Input 
               1
2
0 
                Sample Output 
               1
1 
               
 正确排列元素数量大于等于总元素数量的一半的结果算为一种情况，求总情况数。 C ( n , n / 2 ) * M ( n / 2 ) + C ( n , n / 2 + 1 ) * M ( n / 2 - 1 ) + . . . + C ( n , n ) 。 
                
               中间担心会超过long long 范围做了一点点小的处理。 
               
               #include
                
                 
#include
                 
                   #include
                  
                    #include
                   
                     #include
                     #include
                     
                       #include
                      
                        #include
                       
                         #include
                        
                          #include
                         
                           #include
                          
                            #define PI acos(-1.0) #define maxn 160 #define INF 1<<25 typedef long long ll; using namespace std; __int64 num[25]; __int64 jiecheng[25]; __int64 init() { num[0]=1; num[1]=0; num[2]=1; for(int i=3;i<=20;i++) { num[i]=(i-1)*(num[i-2]+num[i-1]); } } __int64 init2() { __int64 aa=1; jiecheng[0]=1; for(int i=1;i<=20;i++) { aa*=i; jiecheng[i]=aa; } } int main() { init(); init2(); int tot; while(scanf("%d",&tot)) { if(tot==0) break; __int64 ans=0; __int64 rec=1; int ii=tot/2; if(tot%2) ii++; for(int i=ii;i<=tot;i++) { rec=1; for(int j=i+1;j<=tot;j++) rec*=j; rec/=jiecheng[tot-i]; rec*=num[tot-i]; ans+=rec; } printf("%I64d\n",ans); } }

组合数学第二发 错排问题 hdu 2049 + hdu 2068