codeforces136C

2022/9/30 codeforces 逆元组合数

这波是划水叶师傅对逆元有感而发，觉得有必要好好学学，组合数开mod还是挺有必要的

有一说一，逆元是从沈✌那学的，逆元的证明看右边分栏里 s师傅的blog里的数论分块，我就不写了

题意：

有n张标号 1~n 的牌(保证为偶数)，Alice和Bob每人分到 n/2 张牌进行游戏。
游戏规则为：
Alice先手出一张牌，若Bob不能出比Alice的更大的牌则Bob输了，反之两张牌去除，一回合结束。下一回合由Bob先手，持续到一方没牌时平局。
问 Alice 赢，Bob 赢，二人平局的情况分别有多少种。
某个朋友一眼博弈论，在此我要狠狠的批评TA，我每场前都提醒TA，但是TA每场都不打！

当 n = 4 的时候，每人两张牌的话一共有 = 6 种，其中
当Alice的牌为{1，4}，{2，4}，{3，4}时必胜
当Alice的牌为{1，3}，{1，2}时Bob必胜
当Alice的牌为{2，3}是平局(Alice先手出3，Bob出4，Bob出1，Alice出2，此时二者都没牌)

我们用a[i]记录Alice 在 n=i 时赢的情况，b[i] 记录 Alice输的情况(即Bob赢)
我们可以随便取一个值自己从后往前推一下发现，平局的情况是固定的且只有一种

我们来看当 n=6 时，
第一种情况，我们可以发现如果Alice选第6个牌的话，其他两个牌不论这么选都能赢(因为先手)
共有 = 10 种情况

第二种情况，如果Alice不选6，Bob选6，而Alice选5，那么在第一回合5和6都会被用掉，只剩下前四张且Bob先手出牌，如果在这四张牌里Bob先手且要Alice赢的话，我们需要知道4张牌时先手必败的情况，这我们就可以从 b[4] 里知道，从前 for(int i=4;i<=60;i+=2) 往后计算，每一个b[i-2]都存在，所以此时的 a[6]=+b[4]=12 , b[6]=-a[6]-1
综上所述，每一次的 a[i]=+b[i-2] , b[i]= -a[i]-1

接下来就是代码的解决了
我们发现n最大有60，组合数都爆范围了，所以题目也要求要MOD，此时就需要用逆元来求组合数，

对 1到60的逆元我们可以用递推公式求得证明请看沈师傅

for(int i=1;i<=60l++i){
  inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
}

此时inv数组存着每一个数的逆元

当我们算时，简单算一下发现
分子要计算 i 到 (i/2+1) 分母要计算 (i/2) 到 1，分别有 i/2 个

这时候就可以从大往小 *分母 *分子的逆元（MOD）。

    for(int x=i,y=i/2;y>0;--x,--y){
        num=((num*x)%MOD*inv[y])%MOD;
    }

也是同理
code：

#include <bits/stdc++.h>
#define rep(i,n,m) for(int i=n;i<=m;++i)
#define per(i,n,m) for(int i=n;i>=m;--i)
#define PII pair<int,int>
#define lowbit(x) x&-x
#define INF 1<<30
using namespace std;
typedef long long ll;
const int N=2e5+10;
const int MOD=998244353;
ll inv[N],a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    //初始化
  inv[1]=1,a[2]=1,b[2]=0;
    
  //计算逆元
    rep(i,2,60)inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;

    for(int i=4;i<=60;i+=2){
        //计算第一种情况时的组合数
    ll sum=1;
        for(int x=i-1,y=i/2-1;y>0;--x,--y){
            sum=((sum*x)%MOD*inv[y])%MOD;
        }
    //计算第二种情况时的组合数
        ll num=1;
        for(int x=i,y=i/2;y>0;--x,--y){
            num=((num*x)%MOD*inv[y])%MOD;
        }

    //因为前面MOD过了，数据可能是负数，请记得 +MOD
        a[i]=(sum+b[i-2]+MOD)%MOD;
        b[i]=(num-a[i]-1+MOD)%MOD;
    }

    int m;cin>>m;
    while(m--){
        int n;cin>>n;
        cout<<a[n]<<" "<<b[n]<<' '<<1<<endl; 
    }
    return 0;
}

其实有时间的话，自己一个一个打表也行的（doge）

LOADING

codeforces136C