UVa 11481 (计数) Arrange the Numbers

时间:2021-11-15 07:33:59

居然没有往错排公式那去想,真是太弱了。

先在前m个数中挑出k个位置不变的数,有C(m, k)种方案,然后枚举后面n-m个位置不变的数的个数i,剩下的n-k-i个数就是错排了。

所以这里要递推一个组合数和错排数。

顺便再复习一下错排递推公式,Dn = (n-1)(Dn-1 + Dn-2),D0 = 1,D1 = 0.

这里强调一下D0的值,我之前就是因为直接从D1和D2开始递推的结果WA

 #include <cstdio>
typedef long long LL; const int maxn = + ;
const LL M = ;
LL c[maxn][maxn], d[maxn]; inline LL mul(LL a, LL b) { return (a * b) % M; } void init()
{
for(int i = ; i < maxn; i++) c[i][] = c[i][i] = ;
for(int i = ; i < maxn; i++)
for(int j = ; j < i; j++)
c[i][j] = (c[i-][j] + c[i-][j-]) % M;
d[] = ; d[] = ; d[] = ;
for(int i = ; i < maxn; i++) d[i] = mul(i-, (d[i-] + d[i-]) % M);
} int main()
{
//freopen("in.txt", "r", stdin); init();
int T; scanf("%d", &T);
for(int kase = ; kase <= T; kase++)
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
LL ans = ;
for(int i = ; i <= n - m; i++)
ans = (ans + mul(c[n-m][i], d[n-k-i])) % M;
ans = (ans * c[m][k]) % M;
printf("Case %d: %lld\n", kase, ans);
} return ;
}

代码君