F. Omkar and Akmar【游戏，组合，逆元】—— Codeforces Round #724 (Div. 2)

https://codeforces.com/contest/1536/problem/F

游戏

游戏这方面，官方题解已经讲的很好了。
https://codeforces.com/blog/entry/91520
题目问的是

the number of possible distinct games where both players play
optimally

那我们只要把所有的结果考虑一下：
AB交错，且AB之间最多有一个空格。这个时候游戏结束
（也因此必是Omkar赢，因为如果场上还有奇数时，会…A 空A…，可以补个$B$）

组合

假设从A开始——后面$?2$即可
设总共为n分,有i对AB，有$t=2?i$个字母，

1）排字母，是$t!$，因为字母一定，就是选一个放一个的事了。
2）排空格，剩下的$n?t$个空格，插入到A__B之间去，（ __ 表示可能有空格）
隔板法：
1.第一个A是1号位置：
A__B__A__B__…
——也就是：
有$t$个空位，放$n?t$个空格。
$C_t^{n?t}$
2.第一个A是2号位置：
空A__B__A__B…（这里末尾没有__ , 因为在环上，相邻AB只有一个 __)
——也就是：
有$t?1$个空位，放$n?t?1$个空格。
$C_{t?1}^{n?t?1}$
（首先要确定$n?t<=t$即$2?t>=n$必成立，不然没有解）
所以排空格有
$(C_t^{n?t}+C_{t?1}^{n?t?1})$种

综上，有
${\sum }_{(符合条件的t)}2?t!?(C_t^{n?t}+C_{t?1}^{n?t?1})$

逆元

现在问题是，如何求大组合数。
参考网站
https://article.itxueyuan.com/ZoGkvE
但是现在只是记住了最后线性递推逆元（神奇小饼干法）(博主好可爱），数论基础薄弱非一日之功。

第二天让我看懂的：
https://www.freesion.com/article/43361201366/

1. List item

这里还需要一个证明，
开始$inv[i]$是$i$的逆元
后来$inv[i]$是$i?inv[i?1]$，因为$(a?b{)}^{?}1=a^{?}1?b^{?}1$

AC代码：

#include <bits/stdc++.h>
using namespace std;
//#ifdef LOCAL
//FILE*FP=freopen("text.in","r",stdin);
//#endif
#define N 1000005
const int mod=1e9+7;
#define int long long
int fac[N],inv[N];
void pre(){
    fac[0]=inv[0]=inv[1]=1;for(int i=1;i<N;++i)fac[i]=1ll*fac[i-1]*i%mod;for(int i=2;i<N;++i)inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;for(int i=1;i<N;++i)inv[i]=1ll*inv[i-1]*inv[i]%mod;
}
int c(int x,int y){
    if(x<y)return 0;return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
signed main(){
    pre();int n;scanf("%lld",&n);int sum=0;for(int t=0;t<=n;t+=2){
    if(2*t<n)continue;sum+=fac[t]*(c(t,n-t)+c(t-1,n-t-1))%mod;}printf("%lld\n",2*sum%mod);
}