HDU 2068
题目:
今年暑假杭电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
我将AC代码li'd/*/行的C(n,i)改成C(n,n-i)就WA了。。。
求教求教!!!
AC代码:
#include<iostream>
using namespace std;
long long C(int m, int n) {//求出从m个人选出n个的组合数
long long num1 = 1, num2 = 1;
for (int i = 1;i <= n;i++) {
num1 *= i;
num2 *= (m - i + 1);
}
if (n == 0)return 1;
else return num2/num1;
}
int main() {
int n;
long long x[100];
x[0] = 1;
x[1] = 0;
x[2] = 1;
for (int i = 3;i <= 25;i++) {//错排公式
x[i] = (i - 1)*(x[i - 1] + x[i - 2]);
}
while (cin >> n&&n!=0) {
long long sum = 0;
int i;
if (n % 2 == 0)i = n / 2;
else i = (n - 1) / 2;
for (i;i >= 0;i--) {//累加求出出错人数在一半或一半以下的情况
/*/sum += C(n, i)*x[i];
}
cout << sum << endl;
}
return 0;
}
我将/*/行的C(n,i)改成C(n,n-i)就WA了。。。
求教求教!!!