学步园

这个题目的大概意思是：给n个座位。每个座位都有对应的人。问：至少前k个座位都坐错的种数。

直接求至少前k个座位都坐错的话有点难求。。

直接求总数-反例

把问题转换为：求至多有前k个座位坐对的总数。

假设有n=7 k=3

我们求前1个座位坐对的总数为：

C(3,1)*A(6,6)

但是考虑到这样的话会把1 3 1 2 2 3给算重

要减去1 2 1 3 2 3的总数。就是要减去C(3,2)*A(5,5)

但是减去的话又会多减去2 3的情况所以又要加上C(3,3)*A(4,4)

然后我们看一下

C(3,1)*A(6,6)-C(3,2)*A(5,5)+C(3,3)*A(4,4)

基本上就这样了。详情看代码

//First Edit Time:	2014-07-15 19:15
//Last Edit Time:	2014-07-15 19:35
//Filename:E.cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL c[20][20];
LL a[20];
int main()
{
    a[0]=1;
    a[1]=1;
    c[1][0]=c[1][1]=1;
    for(int i=2;i<=17;i++)
    {
        a[i]=a[i-1]*i;
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int cas,n,k;
        scanf("%d%d%d",&cas,&n,&k);
        if(k==0)
        {
            printf("%d %lld\n",cas,a[n]);
            continue;
        }
        LL  ans=0;
        for(int i=1;i<=k;i++)
        {
            if(i&1) ans+=(c[k][i])*a[n-i];
            else ans-=(c[k][i])*a[n-i];
        }
        printf("%d %lld\n",cas,a[n]-ans);
    }
    return 0;
}