Consider this sequence {1, 2, 3, . . . , N}, as a initial sequence of first N natural numbers. You can
earrange this sequence in many ways. There will be N! different arrangements. You have to calculate
the number of arrangement of first N natural numbers, where in first M (M ≤ N) positions, exactly
K (K ≤ M) numbers are in its initial position.
Example:
For, N = 5, M = 3, K = 2
You should count this arrangement {1, 4, 3, 2, 5}, here in first 3 positions 1 is in 1-st position and
3 in 3-rd position. So exactly 2 of its first 3 are in there initial position.
But you should not count this {1, 2, 3, 4, 5}.
Input
The first line of input is an integer T (T ≤ 1000) that indicates the number of test cases. Next T line
contains 3 integers each, N (1 ≤ N ≤ 1000), M, and K.
Output
For each case, output the case number, followed by the answer modulo 1000000007. Look at the sample
for clarification.
Sample Input
1
5 3 2
Sample Output
Case 1: 12
题意：给你 n,m,k, 表示a[i] = 1,2....,n 经过变换后-> 前m个数中只有任意 k个数满足 i = a[i]问你方案数
题解：我们 先在前m个数中任意选k个数是满足不变的 即 C(m,k);
再枚举后n-m个中有多少个数的位置是不变的，C(n−m,x),这样就有n−k−x个数为乱序排列。
对于y个数乱序排序，我们考虑dp做法，假设已经 求出 y-1，y-2个数的乱序排序数，那么 dp[y] = (y-1)*(dp[y-1]+dp[y-2]);（详见上一题）
//meek///#include<bits/stdc++.h>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<bitset>
#include<vector>
#include <queue>
#include <map>
#include <set>
#include <stack>
using namespace std ;
#define mem(a) memset(a,0,sizeof(a))
#define pb push_back
#define fi first
#define se second
#define MP make_pair
typedef long long ll; const int N = +;
const int M = ;
const int inf = 0x3f3f3f3f;
const ll MOD = ; int n, m, k;
ll dp[N], c[N][N];
void init () {
for (int i = ; i < N; i++) {
c[i][] = c[i][i] = ;
for (int j = ; j < i; j++)
c[i][j] = (c[i-][j-] + c[i-][j]) % MOD;
}
dp[] = ;
dp[] = ;
dp[] = ;
for (ll i = ; i < N; i++)
dp[i] = ((dp[i-] + dp[i-]) % MOD * (i-)) % MOD;
} ll solve () {
ll ans = ;
int t = n - m;
for(int i = ;i <= n-m; i++) ans += (c[t][i]*dp[n-k-i]), ans %= MOD;
return (ans * c[m][k]) % MOD;
}
int main () {
init();
int cas = , T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d", &n, &m, &k);
printf("Case %d: %lld\n", cas++, solve());
}
return ;
}
代码