LOJ2034「SDOI2016」排列计数 排列组合

问题描述

求有多少种长度为 $ n $ 的序列 $ A $，满足以下条件：

• $ 1 sim n $ 这 $ n $ 个数在序列中各出现了一次；
• 若第 $ i $ 个数 $ A_i $ 的值为 $ i $，则称 $ i $ 是稳定的。序列恰好有 $ m $ 个数是稳定的。

满足条件的序列可能很多，序列数对 $ 10 ^ 9 + 7 $ 取模。

---

题解

错排记数

(n) 封信装进 (n) 个信封，全部装错了，方案数。

[d_i=(i-1) imes (d_{i-1}+d_{i-2}) ]

边界： (d_1=0,d_2=1,d_3=2) 。

---

首先处理 (m) 个相同的位置，显然方案数为 (C_n^m)

所以答案为 (C_n^m imes d_{n-m} mod 10^9+7) 。

---

(mathrm{Code})

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

const int maxn = 1000000 + 7;
const int maxm = 2000000 + 7;
const int mod = 1000000007;

int T;
int n, m;

LL f[maxn], inv[maxn];
LL d[maxn];

LL fpow(LL x, int p) {
	LL res = 1ll;
	while(p) {
		if(p & 1) res = res * x % mod;
		x = x * x % mod, p >>= 1;
	}
	return res;
}

template < typename Tp >
void read(Tp &x) {
	x = 0;char ch = 1;int fh = 1;
	while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if(ch == '-') fh = -1, ch=getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	x *= fh;
}

void Init(void) {
	scanf("%d", &T);
}

void Preprocess(void) {
	f[0] = 1ll, d[2] = 1, d[3] = 2;
	for(int i = 1; i <= 1000000; i++) {
		f[i] = f[i - 1] * i % mod;
		inv[i] = fpow(f[i], mod - 2);
		if(i >= 4) d[i] = (i - 1) * (d[i - 1] + d[i - 2]) % mod;
	}
}

void Work(void) {
	Preprocess();
	while(T--) {
		scanf("%d%d", &n, &m);
		if(n - m == 1) puts("0");
		else if(m == n) puts("1");
		else if(m == 0) printf("%lld
", d[n]);
		else printf("%lld
", f[n] * inv[m] % mod * inv[n - m] % mod * d[n - m] % mod);
	}
}

int main() {
	Init();
	Work();
	return 0;
}