题解：CF1536F Omkar and Akmar

对于这些博弈论但是数据范围很大的题目一定要找一些特殊性质。

考虑最终的局面是什么样的。如果出现空格，这个空格两边一定是两个不同的字母，要不然就是两个不同的字母在相邻的位置上。

因此整个环去掉空格后一定是 ABABABABAB 交错或者 BABABABABA 交错。从这个就可以看出 A 的个数一定等于 B 的个数，因此无论后手如何操作一定会赢，因此无论如何操作都是一个人的最优策略。

所以就对最终状态计数即可。

考虑枚举去掉空格后有多少个字母

i

，这里必须保证

i

是偶数，（因为总共操作了偶数次），这样相当于插在

i

个位置中选择

n-i

个位置填空格。由于还需要操作

i

次，所以还需要乘以

i

的圆排列数（这个时候我们可以先不确定序列开头的下标为

1

）。

然后从每一个下标开始都可以有这个序列，同时 A 和 B 的地位等价，所以还需要乘以

2n

。

总的答案就是如下的式子：

2n\sum_{i=2,2|i}^n \binom{i}{n-i}\times(i-1)!

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll maxn=1e6+5,modd=1e9+7;
ll fac[maxn],inv[maxn],n,ans;
ll qpow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=(ret*a)%modd;
        a=(a*a)%modd;
        b>>=1;
    }
    return ret;
}
void init(){
    fac[0]=1;
    for(ll i=1;i<maxn;i++){
        fac[i]=(fac[i-1]*i)%modd;
    }
    inv[maxn-1]=qpow(fac[maxn-1],modd-2);
    for(ll i=maxn-2;i>=0;i--){
        inv[i]=(inv[i+1]*(i+1))%modd;
    }
}
ll C(ll n,ll m){
    if(n<m)return 0;
    if(m==0)return 1;
    return fac[n]*inv[m]%modd*inv[n-m]%modd;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin>>n;
    for(ll i=1;i<=n;i++){
        if(i&1)continue;
        ans=(ans+C(i,n-i)*fac[i-1]%modd)%modd;
    }
    cout<<(ans*2*n%modd+modd)%modd<<"\n";
    return 0;
}

题解：CF1536F Omkar and Akmar

文章操作

相关推荐

评论

题解：CF1536F Omkar and Akmar