题目链接:http://codeforces.com/problemset/problem/888/D
题意:
给定n,k,问你有多少种1到n的排列,满足至少有n-k个a[i] == i。
(4 <= n <= 1000, 1 <= k <= 4)
题解:
转换题意:
给定n,k,问你有多少种1到n的排列,满足最多有k个a[i] != i。
D(i)表示1到i的排列的错排方案数。
那么ans = ∑(C(n,i) * D(i)) + 1,其中i∈[2,k]。
ps:
错排递推式:D(n) = (n-1) * (D(i-1)+D(i-2))
错排通项式:D(n) = n! * ∑(((-1)^i) / i!),其中i∈[2,n]
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h> using namespace std; long long n,k;
long long ans=; int main()
{
cin>>n>>k;
if(k>=) ans+=n*(n-)/;
if(k>=) ans+=*n*(n-)*(n-)/;
if(k>=) ans+=*n*(n-)*(n-)*(n-)/;
cout<<ans<<endl;
}