[ABC241Ex] Card Deck Score 题解

题目链接

点击打开链接

题目解法

个人认为推式子很妙的生成函数题

暴力套上生成函数，\(ans=[x^m]\prod\limits_{i=1}^{n}(\sum\limits_{j=1}^{b_i}(a_ix)^j)\)
\(\sum\limits_{j=1}^{b_i}(a_ix)^j=\frac{1-(a_ix)^{b_i+1}}{1-a_ix}\)
所以 \(ans=[x^m]\prod\limits_{i=1}^{n}\frac{1-(a_ix)^{b_i+1}}{1-a_ix}\)
分离一下分子分母：\(ans=[x^m]\prod\limits_{i=1}^{n}(1-a_ix^{b_i+1})\prod\limits_{i=1}^n\frac{1}{1-a_ix}\)
因为 \(n\) 非常小，所以 \(\prod\limits_{i=1}^{n}(1-a_ix^{b_i+1})\) 可以 \(2^n\) 枚举子集然后暴力计算系数和指数
上面的都是比较套路的 GF 技巧

现在考虑 \(\prod \frac{1}{1-a_ix}\) 怎么算
我感觉这道题的精髓在于下面的化 \(\prod\) 为 \(\sum\)，这样可以避免除法的操作
具体怎么做，可以待定系数法：\(\prod \frac{1}{1-a_ix}=\sum \frac{t_i}{1-a_ix}\)
考虑分子恒为 \(1\)，列出一下等式：\(1=\sum\limits_{i=1}^n c_i\prod\limits_{j=1,j\neq i}(1-a_jx)\)

下面一步我感觉也很妙
因为 \(x\) 是任意的，所以考虑构造出 \(x\) 从而构造出 \(t\) 使得等式满足
考虑 \(crt\) 的思想，因为我们需要在 \(i\neq k\) 时，使 \(\sum c_k\prod\limits_{l=1,l\neq k}(1-a_lx)=0\)
可以构造 \(x_i=\frac{1}{a_i}\)，然后不难求得 \(t_i\)

因为 \(1-a_ix=\sum\limits_{j=0}^{\infty} (a_ix)^j\)
所以不难直接统计答案

时间复杂度 \(O(2^nn\log b)\)

#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 pb push_back
#define int long long
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=16,P=998244353;
int n,m,f[1<<N],mi[1<<N],coef[N],a[N],b[N],t[N];
int qmi(int a,int b){
    int res=1;
    for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
    return res;
}
signed main(){
    n=read(),m=read();
    F(i,0,n-1){
        a[i]=read(),b[i]=read();b[i]++;
        coef[i]=P-qmi(a[i],b[i]);
    }
    F(S,0,(1<<n)-1){
        f[S]=1;
        F(i,0,n-1) if(S>>i&1) f[S]=1ll*f[S]*coef[i]%P,mi[S]+=b[i];
    }
    F(i,0,n-1){
        int x=qmi(a[i],P-2);t[i]=1;
        F(j,0,n-1) if(i!=j) t[i]=1ll*t[i]*(P+1-a[j]*x%P)%P;
        t[i]=qmi(t[i],P-2);
    }
    int ans=0;
    F(S,0,(1<<n)-1) if(m>=mi[S]) F(i,0,n-1) ans=(ans+f[S]*t[i]%P*qmi(a[i],m-mi[S]))%P;
    printf("%lld\n",ans);
    fprintf(stderr,"%d ms\n",int64_t(1e3*clock()/CLOCKS_PER_SEC));
    return 0;
}