Omkar and Akmar 题解

题意：有一个 \(n\) 个点的环，以及两个人。每个人可以向环中任意一个位置放置一个 \(A\) 或者 \(B\)，但是相邻的位置不能相同，不能行动者输。问最终的局面有多少种。

一个结论是：后手必胜。

证明：最终肯定不可能出现两个连续的空格，否则一定可以在其中一个上填 \(A\) 或 \(B\)。所以最多只有一个空格，而这个空格两边填的字母一定是不一样的，否则一定可以在这填一个和它两边不一样的字母。所以如果把所有空格去掉之后，一定是 \(ABABAB\dots\)(\(k\) 个 \(AB\)) 的形式。步数一定为偶数，所以后手必胜。

问题转化成了有多少种在环上放空格的方式，使得每两个空格都不相邻。可以先断环为链，然后分类讨论，假设当前要选 \(i\) 个空格(必须满足 \(n-i\) 为偶数)。如果链的第一个位置为空格，则后面 \(n-1\) 个要选出 \(i-1\) 个空格且首尾不能选，方案数 \(C^{i-1}_{n-i-1}\)(插空法)。如果链的第一个位置不为空格，则后面 \(n-1\) 个要选出 \(i\) 个空格且首尾可以选，方案数 \(C^{i}_{n-i}\)(插空法)。注意还要乘以 \(2\times(n-i)!\)，\(2\) 表示可以从 \(A\) 开始也可以从 \(B\) 开始，\((n-i)!\) 表示每个人每次选择位置的顺序。

枚举 \(i\)，累计答案即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e6 + 10;
const int mod = 1e9 + 7;
int n,inv[MAXN],fac[MAXN],invfac[MAXN],ans;	
inline int C(int n,int m){if(n >= m && n >= 0 && m >= 0)return fac[n] * invfac[n - m] % mod * invfac[m] % mod;else return 0;}
signed main()
{
	cin >> n;
	fac[0] = inv[0] = invfac[0] = 1;
	fac[1] = inv[1] = invfac[1] = 1;
	for(int i = 2;i <= 2 * n;i++) 
	{
		fac[i] = (fac[i - 1] * i) % mod;
		inv[i] = (inv[mod % i] * (mod - mod / i)) % mod;
		invfac[i] = (invfac[i - 1] * inv[i]) % mod;
	}  
	for(int i = 0;i <= n;i++) 
		if((n - i) % 2 == 0) ans = (ans + ((2 * fac[n - i]) % mod * (C(n - i - 1,i - 1) + C(n - i,i))) % mod) % mod;
	cout << ans;
	return 0;
}