这个题目的大概意思是：给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)
基本上就这样了。详情看代码
#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;
}
|
