题目链接:11481 - Arrange the Numbers
题意:序列1-n,进行重排,问最后前m个中有k个仍然位置不变的情况数 思路:之前写过UVA 580, n个数重排,要求每个位置都不同的情况的题目,递推式为dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2]) 利用这个,这题只要: k个位置C(m, k) * sum(C[n - m][i] (后面n-m个选出i个对应正确匹配) * dp[n - k - i](其余位置全都错排)} 这便是总情况数 代码:
#include <stdio.h>
#include <string.h>
const long long MOD = 1000000007;
const int N = 1005;
int t, n, m, k;
long long dp[N], C[N][N];
void init() {
dp[0] = 1; dp[1] = 0; dp[2] = 1;
for (int i = 3; i <= 1000; i++)
dp[i] = (i - 1) * ((dp[i - 2] + dp[i - 1]) % MOD) % MOD;
for (int i = 0; i <= 1000; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
}
}
int main() {
int cas = 0;
init();
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
long long ans = 0;
for (int i = 0; i <= n - m; i++)
ans = (ans + C[n - m][i] * dp[n - k - i] % MOD) % MOD;
printf("Case %d: %lld\n", ++cas, ans * C[m][k] % MOD);
}
return 0;
}