教育网站建设方案模板,0元建站平台,短视频营销,运维系统Problem Descrption
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜#xff0c;第一次猜#xff1a;R是公主#xff0c;P是草儿#xff0c;G是月野兔#xff1b;第二次猜…Problem Descrption
今年暑假杭电ACM集训队第一次组成女生队,其中有一队叫RPG,但做为集训队成员之一的野骆驼竟然不知道RPG三个人具体是谁谁。RPG给他机会让他猜猜第一次猜R是公主P是草儿G是月野兔第二次猜R是草儿P是月野兔G是公主第三次猜R是草儿P是公主G是月野兔......可怜的野骆驼第六次终于把RPG分清楚了。由于RPG的带动做ACM的女生越来越多我们的野骆驼想都知道她们可现在有N多人他要猜的次数可就多了为了不为难野骆驼女生们只要求他答对一半或以上就算过关请问有多少组答案能使他顺利过关。
Input
输入的数据里有多个case,每个case包括一个n代表有几个女生n25, n 0输入结束。
Output
1
1
Sample Input
1
2
0
Sample Output
1
1
问题链接http://acm.hdu.edu.cn/showproblem.php?pid2068
问题分析根据错列排序的思想
错排简单点说就是给n个节点它们原来的位置为i 然后让你把它们从新排列使得它们都不在它们原来的位置上。 错排递归公式f(i) (i - 1) * (f(i - 1) f(i - 2)); i 4 (f(0) 0, f(1) 0, f(2) 1, f(3) 2); AC代码
#includeiostream
using namespace std;
long int c(int n,int m)
{long int i,t11,t21;for(in;in-m1;i--)t1*i;for(i1;im;i)t2*i;return t1/t2;
}int main()
{int i,k,r;long int a[15],cr,n;a[0]0;a[1]0;a[2]1;for(k3;k15;k)a[k](k-1)*(a[k-1]a[k-2]);while(scanf(%I64d,n)n){rn/2;cr0;for(i2;ir;i)crc(n,i)*a[i];//小于n/2的人的错排的和即为所求if(n1||n2)printf(1\n);else printf(%I64d\n,cr1);}return 0;
}
