HDU 1465:不容易系列之一

点击打开题目链接

题目意思就是：

有n个位置，n个物品，求把n个物品都放错位置的方案数，1<n<=20.

首先2个物品，都放错位置只有一种方法，ans[2] = 1;

而3个物品，随便摆放有  3*2*1 种方法，其中减去有放的对的方式，就是都放错的方法。

3个物品全放对只有一种方法，有一个放对，C（3，1）*ans[2]，如果有两本全放对了，则所有物品都放对了。

这里C（m,n）代表数学中的从m件物品中挑选n件的方案数。

则4个物品随便放有4*3*2*1= 24种方法。

ans[4] = 24 - 1 - C（4，1）*ans[3] - C(4,2)*ans[2]

ans[5] = 120 - 1 - C(5,1)*ans[4] - C(5,2)*ans[3] - C(5.3)*ans[2]

而C(m,n) = C(m-1,n-1) + C(m-1,n);

则可以利用之前算出的组合数，来算出新的组合数。

而且这个题目需要打表，提前把所有答案都求出来，因为提问的n只是从1~20.按照航电的套路，后台一定会

搞很多重复的数据来反复测来让你超时，打表就不会入坑。其次数组用long long，用int求到10的时候，答案就会超限。

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int n;
long long ans[25];
long long m[25][25];    ///m[i][j]代表的是从i中物品中挑选j个的方案数。
void create_table()
{
    ans[2] = 1;   ///两个物品都放错有一种方法。
    memset(m,0,sizeof(m));  ///整个数组刷成m
    m[2][0] = 1;
    m[2][1] = 2;
    m[2][2] = 1;
    long long mul = 2;
    for(int i = 3; i <= 21; i++)
    {
        mul = mul*i;
        long long temp = mul;
        m[i][0] = 1;
        for(int j = 1; j <= i; j++)
            m[i][j] = m[i-1][j-1]+m[i-1][j];
        temp--;
        for(int j = 1; j <= i-2; j++)
            temp = temp - m[i][j]*ans[i-j];
        ans[i] = temp;
    }
}
int main()
{
    create_table();
    int n;
    while(~scanf("%d",&n))
    {
        printf("%lld\n",ans[n]);
    }
    return 0;
}