CF1536F Omkar and Akmar 题解

思路

首先最后的局面在两两字母间一定不会多于 \(1\) 个空格。考虑反证，假设有两个空格，那么有以下两种情况：\(\text{A}\_\_ \text{B}\)，\(\text{A}\_\_ \text{A}\)，也就是两边的字母不同，相同。对于第一种，在任意一个空格都可以填一个与他相邻字符不同的字符，对于第二种，填 \(\text{B}\) 即可。因此，最后两字母之间一定只有一个空格，并且空格隔开的两字符不同。那么把空格去掉之后，一定是形如 \(\text{ABAB\dots B}\) 这样 \(\text{A,B}\) 相间的一个排列，并且最后一个字符与第一个不同。那么这个序列长一定为偶数，也就是说最后一步一直都是由后手走，故后手必胜。因此每时每刻，任何人的任何操作都是最优策略。

那么我们就只需要考虑计数了。设最后局面有 \(i\) 个空格，满足 \(2 \mid n-i\)，考虑第 \(1\) 格的放置情况：

• 放空格，那么在后面 \(n-1\) 个位置中放 \(i-1\) 个空格，且两空格不相邻，首尾不能放（相当于只有 \(n-3\) 个空格），共 \(C_{n-i-1}^{i-1}\) 种放法。
• 不放空格，那么在 \(n-1\) 个位置中放 \(i\) 个空格，只需满足两两不相邻即可，共 \(C_{n-i}^{i}\) 种放法。

对于字符来说，顺序是任意的，并且 \(\text {A,B}\) 可以交换，那么这部分答案就是 \(2 \times (n-i)!\)。

因此，总答案为 \(\displaystyle\sum_{i=0,2 \mid n-i}^{n}2\times (n-i)! \times (C_{n-i-1}^{i-1}+C_{n-i}^{i})\)。

这里说一下 \(n\) 个球取 \(m\) 个不相邻的球的方案数怎么算。可以先在 \(n-m+1\) 个球中任取 \(m\) 个球，就有 \(C_{n-m+1}^{m}\) 种选法，然后再另外拿 \(m-1\) 个球插到那 \(m\) 个球的 \(m-1\) 个空位中，这样使得我们原本取出的 \(m\) 个球都互不相邻，并且最后总球数为 \(n\) 个。不难验证逆向思维得出的情况与正常考虑的情况是一一对应的，故我们可以得到上面的结论。

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,k,cnt;
const int mod=1e9+7;
ll fac[1000005],ans,inv[1000005]; 
ll qpow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
ll C(int x,int y){
	if(x<y||x<0||y<0)return 0;
	return fac[x]*inv[x-y]%mod*inv[y]%mod;
}
int main(){
	cin>>n;
	fac[0]=1;
	for(ll i=1;i<=n;++i)fac[i]=(fac[i-1]*i)%mod;
	inv[n]=qpow(fac[n],mod-2);
	inv[0]=1;
	for(int i=n-1;i>=1;--i)inv[i]=(inv[i+1]*(ll)(i+1))%mod;
	for(int i=0;i<=n;++i){
		if((n-i)&1)continue;
		ans=(ans+2*fac[n-i]%mod*((C(n-i-1,i-1)+C(n-i,i))%mod))%mod;
	}
	cout<<ans;
	return 0;                      
}