FZU2282（组合数+错排）

题目大意：一共n个数（1~n），问A[i] == i的个数大于等于k的方案数。

解题思路：其实就是大于等于k个人筛掉后剩下的人进行错排的问题。选k~n个人对应得要乘上组合数，由于n比较大，k相对较小，可以打表数组肯定mle，于是可以反过来想：总得排列数是Ann，扣除小于k的方案就能够得到答案，由于所有打表都进行取模，最后还要防止变成负数！求组合数取模的问题也可以用卢卡斯定理方法求得。

Code：

#include <stdio.h>
#include <string.h>
const int maxn = (int)1e4+5;
const int mod = (int)1e9+7;
typedef long long LL;

LL dp[maxn],n,k,sum, A[maxn];
LL c[maxn][105];

int main() {
	int T;
	dp[0] = 0;
	dp[1] = 0;
	dp[2] = 1;
	for (int i = 3; i < maxn; i++) {
		dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) % mod;
	}
	A[1] = 1;
	for (int i = 2; i < maxn; i++) {
		A[i] = (A[i-1] * i) % mod;
	}
	for (int i = 0; i < maxn; i++) {
		int k = i > 100 ? 100 : i;
		c[i][0] = 1;
		for (int j = 1; j <= k; j++) {
			c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
		}
	}

	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &k);
		sum = 0;
		for (int i = 0; i < k; i++) {
			sum = (sum + dp[n-i] * c[n][i]) % mod;
		}
		sum = (A[n] - sum + mod) % mod; //由于mod的原因可能会变成负数
		printf("%d\n", sum);
	}
	return 0;
}