HDU_2068_RPG错排

时间：2023-03-08 15:45:14

Problem Description

今年暑假杭电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输入结束。

Sample Input

1

2

0

Sample Output

1

1

思路：

考虑到，答对一半以上。那么可以先抽出m/2个然后另外m/2个进行全部错误顺序的排列（错排）。当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用M(n）表示，那么M(n-1）就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.

第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；

第二步，放编号为k的元素，这时有两种情况⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有M(n-2）种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有M(n-1）种方法；

综上得到

M(n)=(n-1）[M(n-2）+M(n-1）]

特殊地，M⑴=0,M⑵=1

得到错排公式之后，应用于程序即可。分别得出m/2, m/2+1 … m对应的情况数之后，求和即可得到正确的结果。







 #include<iostream>

 using namespace std;

 __int64 F[]={};

 int C(__int64 n,__int64 m)

 {

          __int64 sum1=,sum2 =;

          for(__int64 i=n;i>=n-m+;--i)

                  sum1*=i;

          for(__int64 i=;i<=m;++i)

                  sum2*=i;

          return sum1/sum2;

 }

 int main()

 {

          F[]=;

          F[]=;

          for(__int64 i=;i<;++i)

                  F[i]=(F[i-]+F[i-])*(i-);

          __int64 n, m;

          __int64 sum;

          while(cin>>n,n)

          {

                  sum=;

                  m=n/;

                  for(__int64 i=;i<=m;++i)

                           sum=C(n,i)*F[i]+sum;

                  cout<<sum<<endl;

          }

          return ;

 }
  




RPG错排




下面通过这个递推关系推导通项公式：


为方便起见，设M(k)=k!N(k),(k=1,2，…，n)


则N⑴=0,N⑵=1/2


n>=3时，n!N(n)=(n-1）（n-1）！N(n-1）+(n-1）！N(n-2）


即 nN(n)=(n-1）N(n-1）+N(n-2）


于是有N(n)-N(n-1）=-[N(n-1）-N(n-2）]/n=(-1/n)[-1/(n-1）][-1/(n-2）]…（-1/3）[N⑵-N⑴]=(-1）^n/n!


因此


N(n-1）-N(n-2）=(-1）^(n-1）/(n-1）！


N⑵-N⑴=(-1）^2/2!


相加，可得


N(n)=(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!


因此


M(n)=n![(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!]


可以得到


错排公式为M(n)=n！（1/2!-1/3!+…..+(-1）^n/n!)
相关文章