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 B B）

組合

假設從A開始——后面 ? 2 *2 ?2即可
設總共為n分,有i對AB，有 t = 2 ? i t=2*i t=2?i個字母，

1）排字母，是 t ! t! t!，因為字母一定，就是選一個放一個的事了，
2）排空格，剩下的 n ? t n-t n?t個空格，插入到A__B之間去，（ __ 表示可能有空格）
隔板法：
1.第一個A是1號位置：
A__B__A__B__…
——也就是：
有 t t t個空位，放 n ? t n-t n?t個空格，
C t n ? t C^{n-t}_t Ctn?t?
2.第一個A是2號位置：
空A__B__A__B…（這里末尾沒有__ , 因為在環上，相鄰AB只有一個 __)
——也就是：
有 t ? 1 t-1 t?1個空位，放 n ? t ? 1 n-t-1 n?t?1個空格，
C t ? 1 n ? t ? 1 C^{n-t-1}_{t-1} Ct?1n?t?1?
（首先要確定 n ? t < = t n-t<=t n?t<=t即 2 ? t > = n 2*t>=n 2?t>=n必成立，不然沒有解）
所以排空格有
( C t n ? t + C t ? 1 n ? t ? 1 ) (C^{n-t}_t+C^{n-t-1}_{t-1}) (Ctn?t?+Ct?1n?t?1?)種

綜上，有
∑ ( 符 合 條 件 的 t ) 2 ? t ! ? ( C t n ? t + C t ? 1 n ? t ? 1 ) \sum _{(符合條件的t)} 2*t!*(C^{n-t}_t+C^{n-t-1}_{t-1}) ∑(符合條件的t)?2?t!?(Ctn?t?+Ct?1n?t?1?)

逆元

現在問題是，如何求大組合數，
參考網站
https://article.itxueyuan.com/ZoGkvE
但是現在只是記住了最后線性遞推逆元（神奇小餅干法）(博主好可愛），數論基礎薄弱非一日之功，

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

1. List item

這里還需要一個證明，
開始 i n v [ i ] inv[i] inv[i]是 i i i的逆元
后來 i n v [ i ] inv[i] inv[i]是 i ? i n v [ i ? 1 ] i*inv[i-1] i?inv[i?1]，因為 ( a ? b ) ? 1 = a ? 1 ? b ? 1 (a*b)^-1=a^-1*b^-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);
}