[排列组合]HDU 2049 考新郎


考察“错排公式”

#include<stdio.h>
__int64 f(int n)
{//求阶乘
    int i;
    __int64 sum=1;
    for(i=1;i<=n;i++)
        sum*=i;
    return sum;
}
__int64 C(int n,int m)
{//求组合数
    return f(n)/(f(m)*f(n-m));
}
int main ()
{
    int n,i,a,b;
    __int64 t[21]={0,0,1};
    for (i=3;i<=20;i++)
	{
        t[i] = (i-1)*(t[i-1] + t[i-2]);
		//错排公式  当有i对新人的时候, 全排错的组合数等于 (i-1) * (i-1对新人全排错的组合数+ i-2对新人全排错的组合数)
    }
    while (scanf("%d",&n) != EOF)
	{
        for (i=0;i<n;i++)
		{
            scanf("%d%d",&a,&b);
            printf("%I64dn",C(a,b)*t[b]);
        }
    }
	return 0;
}

发表评论