signed

QiShunwang

“诚信为本、客户至上”

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

2021/6/9 0:22:13   来源:

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=2i个字母,

1)排字母,是 t ! t! t!,因为字母一定,就是选一个放一个的事了。
2)排空格,剩下的 n − t n-t nt个空格,插入到A__B之间去,( __ 表示可能有空格)
隔板法
1.第一个A是1号位置:
A__B__A__B__…
——也就是:
t t t个空位,放 n − t n-t nt个空格。
C t n − t C^{n-t}_t Ctnt
2.第一个A是2号位置:
空A__B__A__B…(这里末尾没有__ , 因为在环上,相邻AB只有一个 __)
——也就是:
t − 1 t-1 t1个空位,放 n − t − 1 n-t-1 nt1个空格。
C t − 1 n − t − 1 C^{n-t-1}_{t-1} Ct1nt1
(首先要确定 n − t < = t n-t<=t nt<=t 2 ∗ t > = n 2*t>=n 2t>=n必成立,不然没有解)
所以排空格有
( C t n − t + C t − 1 n − t − 1 ) (C^{n-t}_t+C^{n-t-1}_{t-1}) (Ctnt+Ct1nt1)

综上,有
∑ ( 符 合 条 件 的 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)2t!(Ctnt+Ct1nt1)

逆元

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

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);
}