qoj8171 Cola 题解

题目链接

点击打开链接

题目解法

很牛的题！！！会不了一点

令 \(pref_i\) 表示第 \(i\) 轮知道了前缀 \([1,...,i]\)
考虑怎样的 \(pref\) 序列是合法的（即采用最优策略）：

1. \(pref_0=0\)
2. \(\forall_{i\in [0,n-1]}\;pref_i\le pref_{i+1}\)
3. \(pref\) 中 \(x\) 的出现次数 \(\le n-x-1\)，因为我们至多花 \(n-x-1\) 次可以排除掉所有错误的，剩下一次一定可以选到对的

考虑对于固定的一个 \(pref\) 数组的概率
假设其中 \(x\) 出现了 \(c_x\) 次
考虑从数字 \(x\) 变化到数字 \(x+1\)，且数字 \(x\) 选错了 \(c_x\) 次的概率（即不按照轮数算，即使 \(c_x=0\) 也会计算到）为：
\(\frac{n-x-1}{n-x}\times \frac{n-x-2}{n-x-1}\times ...\times \frac{n-x-(c_x-1)}{n-x-c_x}\times \frac{1}{n-x-(c_x-1)}=\frac{1}{n-x}\)
很惊奇地发现，最终得到的概率与 \(c_x\) 无关，且把每个数变成下一个数的概率乘起来，恰好为 \(\frac{1}{n!}\)

我们现在的问题是计算合法的 \(pref\) 数组的数量
转化一下问题（一个比较直接的想法是转成网格图计数路径）：从 \((0,0)\) 到 \((m-1,n)\) 的方案数（只能往右或往下），满足 \(\forall i\in [0,n-1]\) 第 \(i\) 行走的步数 \(\le n-i-1\)，这里注意没有限制第 \(n\) 行
考虑容斥，我们钦定集合 \(S\) 中的行 \(x\) 有至少 \(n-x\) 步，那么答案显然为 \(\binom{n+m-1-\sum\limits_{x\in S} n-x}{n}\times (-1)^{|S|}\)
变换一下形式，把 \(S\) 的可选集合变为 \(\{1,...,n\}\)，答案为 \(\binom{n+m-1-\sum\limits_{x\in S} x}{n}\times (-1)^{|S|}\)

用多项式来刻画这个式子，即为 \(\sum \binom{n+m-1-q}{n} [x^q]\prod\limits_{i=1}^n {(1-x^i)}\)
观察到 \(q\le m\)，且 \(m\le n\) 的条件很特殊
考虑 \([x^q]\prod\limits_{i=1}^n {(1-x^i)}\) 等价于 \([x^q]\prod\limits_{i=1}^{\infty} {(1-x^i)}\)
用一下五边形数定理，就可以 \(O(\sqrt m)\) 求所有项的系数了

时间复杂度为 \(O(n+m)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
    int FF=0,RR=1;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    return FF*RR;
}
const int N=20000010,P=998244353;
int n,m,ifac[N],fac[N];
int qmi(int x,int y){
    int res=1;
    for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
void comb(int n){
    fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
}
int C(int x,int y){ if(y<0||x<y) return 0;return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;}
int main(){
    n=read(),m=read();m--;
    comb(n+m);
    int ans=C(n+m,n);
    for(int k=1;(3*k*k-k)/2<=m;k++){
        int v=C(n+m-(3*k*k-k)/2,n)+C(n+m-(3*k*k+k)/2,n);
        if(k&1) ans=(ans-1ll*v)%P;
        else ans=(ans+1ll*v)%P;
    }
    ans=1ll*ans*ifac[n]%P;
    printf("%d\n",(ans+P)%P);
    return 0;
}