[GCJKickstart2018RoundH] C. Let Me Count The Ways（容斥）

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://codejam.withgoogle.com/codejam/contest/3324486/dashboard#s=p2&a=2

一共有$2n$个座位排成一排，现在有m对人去坐，每对人之间有顺序。每对人均不可以相邻，问一共有多少种坐法？

考虑用总的排列数减去每对人都相邻的情况，于是我们发现后者的排列是可以容斥的。

设$f(k)$表示$k$对人均坐在一起的排列数，那么答案就是：
$$
\sum_{k=0}^m(-1)^kf(k)
$$
$f(k)$也比较容易算，可以由下面几个部分组合起来：

  1. $m$对中任取$k$对：$C(m,k)$
  2. 每对人有顺序，那么所有可能的排列就是$2^k$
  3. 在$2n​$个位置里面挑$k​$对位置，将两个相邻位置看成一个座位，那么相当于$2n-k​$个位置的排列，那么总计一共有$(2n-k)!​$种排列。

于是$f(k)=C(m,k)2^k(2n-k)!$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const LL mod =(LL) 1e9+7;
const int maxn = 8100001;
LL f[maxn];
LL n, m;

void init() {
  f[0] = f[1] = 1;
  for(int i = 2; i < maxn; i++) f[i] = (f[i-1] * i) % mod;
}
LL mul(LL x, LL n) {
  LL ret = 1;
  while(n) {
    if(n & 1) ret = (ret * x) % mod;
    n >>= 1;
    x = (x * x) % mod;
  }
  return ret;
}
LL exgcd(LL a, LL b, LL &x, LL &y) {
  if(b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  else {
    LL ret = exgcd(b, a%b, x, y);
    LL tmp = x;
    x = y;
    y = tmp - a / b * y;
    return ret;
  }
}
LL inv(LL a) {
  LL x, y;
  exgcd(a, mod, x, y);
  return (x % mod + mod) % mod;
}
LL C(LL x, LL y) {
  return f[x] * inv(f[x-y]) % mod * inv(f[y]) % mod;
}


LL gao() {
	LL ret = 0;
	for(LL k = 0; k <= m; k++) {
		if(k % 2 == 0) {
			ret += (f[2*n-i]*C(m,i)%mod)*mul(2LL,i)%mod;
			ret %= mod;
		}
		else {
			ret -= (f[2*n-i]*C(m,i)%mod)*mul(2LL,i)%mod;
			ret += mod;
			ret %= mod;
		}
	}
	if(ret < 0) ret += mod;
	return ret % mod;
}

signed main() {
	// freopen("in", "r", stdin);
  // freopen("out", "w", stdout);
	init();
  int T, _ = 1;
  scanf("%d", &T);
  while(T--) {
  	cin >> n >> m;
  	cerr << "Case #" << _ << " Done." << endl;
  	printf("Case #%d: %lld\n", _++, gao());
  }
	return 0;
}