题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1095
题意：
给你包含1~n的排列，初始位置1,2,3...,n，问你刚好固定前m个数中的k个数的位置，问你有多少中排列方案。(比如5 3 2有1 4 3 2 5这种方案，1和3固定了)
思路：
前m个取k个就是C(m, k)个方案。然后就是类似错排的思想，设dp[i]为i个数在初始位置各不相同。其中的组合数用逆元算出。
ans = dp[m - k] * C(n - m, 0) + dp[m - k + 1] * C(n - m, 1) .. dp[n - k] * C(n - m, n - m)，这个式子表示取后面n-m个数的某些数 与 前面的m - k个数形成错排，剩下的数位置不变。
最后就是ans * C(m, k)
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL mod = 1e9 + , dp[];
LL f[];
LL fpow(LL a, LL n) {
LL ans = ;
while(n) {
if(n & )
ans = ans * a % mod;
a = a * a % mod;
n >>= ;
}
return ans;
}
int main()
{
dp[] = ;
dp[] = , dp[] = ;
f[] = f[] = , f[] = ;
for(LL i = ; i <= ; ++i) {
dp[i] = (dp[i - ] + dp[i - ]) % mod * (LL)(i - ) % mod;
f[i] = f[i - ] * (LL)i % mod;
}
int n, m, k, t;
scanf("%d", &t);
for(int ca = ; ca <= t; ++ca) {
scanf("%d %d %d", &n, &m, &k);
if(n == m && m - k == ) {
printf("Case %d: 0\n", ca);
continue;
}
LL ans = f[m] * fpow(f[k]*f[m - k]%mod, mod - ) % mod;
int temp = m - k, temp2 = n - m;
LL res = ;
for(int i = temp; i <= temp2 + temp; ++i) {
res = (res + dp[i] * f[temp2] % mod * fpow(f[i - temp]*f[temp2 - i + temp] % mod, mod - ) % mod) % mod;
}
printf("Case %d: %lld\n", ca, ans * res % mod);
}
return ;
}