[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

using namespace std;

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

void () {
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("out", "w", stdout);
init();
int T, _ = 1;
scanf("%d", &T);
while(T--) {
cin >> n >> m;
cerr << "Case #" << _ << " Done." << endl;
printf("Case #%d: %lldn", _++, gao());
}
return 0;
}