#include "stdio.h"
int main()
{
   int i,j,k,m,n;
   __int64 d[21];
   __int64 c[21][21];
   d[1]=0;
   d[2]=1;
   for (i=3;i<21;i++)
   
       d[i]=(i-1)*(d[i-1]+d[i-2]);
   for ( i = 0;i < 21;i++)     
   {
      
       c[i][0] = 1;
      
       c[i][1] = i;
      
   }
   
   for ( i = 2;i < 21;i++)
      
       for ( j = 2 ; j <= i;j++)
           
           c[i][j] = c[i-1][j-1] + c[i-1][j];

   scanf("%d",&k);
   for (i=0;i<k;i++)
   {
       scanf("%d %d",&n,&m);
       printf("%I64d\n",c[n][m]*d[m]);
   }
  return 0;
}
原题在http://acm.hdu.

其实不需要采用自底向上的方法把情况都，说穿了很简单，就是在n对夫妇中选出m个错选的，在求其错排种类就行了
下面是我的代码，希望对你有帮助

#include <stdio.h>

int main ()
{
    int        c, m, n, i;
    __int64 x, y, temp, num;

    scanf ("%d", &c);
    while (c--)
    {
        scanf ("%d%d", &n, &m);
        num = 1;
        i = n - m;
        x = 0;
        y = 1;
//求组合数，从n中选出m个
        for (;n >= m + 1; n--)
            num *= n;
        for (;i >=1; i--)
            num /= i;

        if (m == 2)
            printf ("%I64d\n", num);
        else
        {
            for (i = 3; i <= m; i++)
            {
                temp = (i - 1) * y + (i - 1) * x;
                x     = y;
                y     = temp;
            }
            printf ("%I64d\n", num * y);
        }
    }

    return 0;
}

你的代码确实很明了，但是我就不明白，我自己的代码哪里出问题了，求解释····谢谢

很有意思的题目。下面的两段代码一段是用递归实现，主要是表现算法的原理。另一段是将递归展开的优化实现，提交的是这段。
其实递归的效率也足够满足这道题的要求。

#include<stdio.h>
long long f(int n, int m)
{
    if(n <= 0 || m <=0 || n < m) return 0;
    if(n == m)
    {
        if(m == 1) return 0;
        if(m == 2) return 1;
        return (f(m - 1, m - 1) + f(m - 2, m - 2)) * (m - 1);
    }
    return f(n - 1, m) * n / (n - m);
}
int main()
{
    int c, n, m;
    scanf("%d", &c);
    while(c--)
    {
        scanf("%d %d", &n, &m);
        printf("%I64d\n", f(n, m));
    }
    return 0;
}

#include<stdio.h>
long long F[21][21];
int main()
{
    int c, i, j;
    F[2][2] = 1;
    for(i = 3; i <= 20; i++)
    {
        for(j = 2; j < i; j++) F[i][j] = F[i - 1][j] * i / (i - j);
        F[i][i] = (F[i - 1][i - 1] + F[i - 2][i - 2]) * (i - 1);
    }
    scanf("%d", &c);
    while(c--)
    {
        scanf("%d %d", &i, &j);
        printf("%I64d\n", F[i][j]);
    }
    return 0;
}

你的c[21][21]没有完全初始化，此矩阵的右上部分没有初始化，所以。。。

不知道怎么的，初始化完了也不好使，也许是我的算法有问题吧，好纠结呀····

你的算法非常好，谢谢你····

程序确实不错，以前做题老用递归，结果各种超时，怕了，以后都没用递归。

刚试了一下楼主的代码，5楼说的没错，确实是因为数组没有初始化的原因，准确地说，是因为C[i][i+1]元素没有初始化为0。
其它没有问题。

回复 8楼 waterstar
递归相对于展开的效率较低，只是因为在递归时要进行CPU现场保护，参数及变量入栈，结果出栈这些额外的操作。这些不过增加线性的时间，在算法复杂度上是一样的。
我猜你之前用递归做题超时的主要原因还是在于重复计算。
就以这道题为例，f(n)值计算依赖于f(n-1)。也就是说在计算f(n)的时候需要先计算f(n-1)的值。
如果这个题目的测试实例只有1组，那么怎么做消耗的时间都是一样的。
但当有多组实例时，在计算f(n)的时候我已经计算过f(n-1)。如果保留了f(n-1)的值，则在下次计算f(n-1)的值直接查表即可给出结果。
在解空间有限的情况下，其实只需要做一次空间的初始化，之后的求解过程完全是查表，复杂度将为O(1)。
所以对于多组测试实例，这种做法是效率是相当可观的。
这一思想其实就是动态规划。

这个我知道，动态规划是自底向上的计算每一步得出的值，然后进行查表工作，和分治法最大的不同是不用重复解决同一个子问题，
事实上我觉得分治法应用范围更广些，不过估计就是用分治的原因，导致递归调用解决同一个子问题的次数过多，然后就超时了……