Cola

题目链接：https://contest.ucup.ac/contest/1499/problem/8171

题目大意： $A$ 手里有个排列，$B$ 能问 $A$ 一个排列，如果排列完全匹配上，那就 $B$ 胜利，否则 $A$ 回答前 $x$ 个位置都是正确的，$x+1$ 的位置是错误的，如果 $m$ 次询问 $B$ 没有胜利就 $A$ 胜利。问 $B$ 在最优决策下， $A$ 随机拿到一个排列时 $B$ 的获胜概率。

做法

显然要对所有排列计数，而 $B$ 的最优策略就是变 $x+1$ 的位置，然后后面的位置从小到大排序（反正是随机拿一个排列，后面的部分随便一个都行，不会影响答案，从小到大好计数）。

所以问题等价于，有多少个 $n-1$ 的序列 $a$ ，满足：

$0\le a_i\le i,\sum\limits_{i=1}^{n-1}a_i\le m-1$ 。

那么等价于求：$[x^{m-1}]\frac{\prod\limits_{i=1}^{n-1}(1-x^i)}{(1-x)^{n+1}}$ ，但是注意到 $m\le n$ .

所以又等价于求： $[x^{m-1}]\frac{\prod\limits_{i=1}^{\infty}(1-x^i)}{(1-x)^{n+1}}$

分母是经典的高维前缀和，可以用组合意义快速计算 $x^i$ 的系数，分子是五边形数定理，直接算就行了。

时空复杂度：$O(n)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=998244353;
const int N=2e7+5;
LL fc[N],nfc[N];
LL C(LL x,LL y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
int n,m;
int main(){
    scanf("%d%d",&n,&m);n--;m--;
    if(!n){
        printf("1\n");
        return 0;
    }
    nfc[0]=nfc[1]=fc[0]=fc[1]=1;for(int i=2;i<=n+n+1;i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
    for(int i=2;i<=n+n+1;i++)nfc[i]=nfc[i-1]*nfc[i]%mod,fc[i]=fc[i-1]*i%mod;
    LL ans=0;
    for(int i=0;i<=n;i++){
        int x=i*(3*i-1)/2;
        if(x>m)break;
        if(i&1)ans=(ans+(mod-1)*C(n+1+m-x,n+1))%mod;
        else ans=(ans+C(n+1+m-x,n+1))%mod;
        x=i*(3*i+1)/2;
        if(x>m || !i)continue;
        if(i&1)ans=(ans+(mod-1)*C(n+1+m-x,n+1))%mod;
        else ans=(ans+C(n+1+m-x,n+1))%mod;
    }
    printf("%lld\n",ans*nfc[n+1]%mod);
    return 0;
}