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 格的放置情况：

对于字符来说，顺序是任意的，并且 \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;                      
}