AtCoder Beginner Contest 241EX(推式子)

题意： n种物品，每个物品有$b_i$个，每个价值为$a_i$，设总价值为所有物品的价值乘积，求选m个物品所有本质不同的方案的价值和。($n\le 16,1\le a_i<998244353,1\le b_i\le 1e7,m\le 1e18$)
Solution:
设第k种物品的生成函数为
$F(k)={\sum }_{i=0}^{b_k}{a}_k^i\ast x^i=\frac{1-(a_{k}x{)}^{b_k+1}}{1-a^{k}x}$
n种物品的生成函数为
G = $\prod f(k)=\prod \frac{1-(a_{k}x{)}^{b_k+1}}{1-a^{k}x}$

则 ans = $[x^m]$G
上面式子，分子可以直接暴力求，因为就是16个多项式，乘出来2^16个项。
假设分子有$A_k{x}^k,k\le m$这个项，分母的多项式去找$[x^{m-k}]$，两者乘积就是其中一个贡献。
所以，重点在于分母,也需要转化成形式幂级数。

分母 = $\prod \frac{1}{1-(a_{k}x)}$，可以写成$\sum \frac{c_k}{1-a_{k}x}$(由高数知识，若分母为多个多项式相乘的分式，可以化成若干个分母为多项式分子最高次数比分母少一次的多项式的和，有点绕😨），写成这样的好处是什么呢？，每一个分式其实是某个等比级数的封闭形式，可以转为形式幂级数，这样每项的系数都可以算了。

接下来求每个$c_i$，由上
$$\begin{gathered} \prod \frac{1}{1-(a_{k}x)}=\sum \frac{c_k}{1-a_{k}x} \\ <=>1=c_1(1-a_{1}x)(1-a_{3}x)..(1-a_{n}x)+c3(1-a_{1}x)(1-a_{2}x)..(1-a_{n}x).... \end{gathered}$$
令x为某个$a_i$,则可以消掉n-1项，可以求出$c_i=\frac{1}{\prod (1-a_j{a}_i)},j\ne i$（类似拉格朗日插值的构造）。
求出了所有$c_i$，每个分式可以写成$\frac{c_i}{1-a_{i}x}=ci(1+a_{i}x+a_i^2{x}^2+...)=c_i\sum a_i^j{x}^j$，那分母就可转化成形式幂级数即$1+B_{1}x+B_2{x}^2+...$的形式，其中$B_i={\sum }_{j=1}^n{c}_j{a}_j^i$。

#include
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define inf 0x3f3f3f3f
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int mod=998244353;
const int N=1e6+10;
const double eps=1e-8;
int a[N],b[N],p[N],d[N],c[N];
ll qsm(int a,int b){
    ll ans =  1, tmp = a;
    while( b ){
        if( b&1 ) ans = ans * tmp%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif  
    IOS;
    int n,m;cin>>n>>m;
    _for(i,0,n-1) cin>>a[i]>>b[i] , b[i]++;
    d[0]=1;
    _for(i,0,n-1){
        int x = (mod - qsm(a[i],b[i]) ) %mod;
        for(int j=0 ;j<(1<<i) ;j++){
            d[(1<<i)+j] = d[j] * x %mod;
            p[(1<<i)+j] = p[j] + b[i];
        }
    }
    _for(i,0,n-1){
        int x = qsm(a[i],mod-2);
        c[i]=1;
        _for(j,0,n-1){
            if(j!=i){
                int y = a[j] * x %mod;
                c[i] = (c[i] * (mod + 1 - y )%mod) %mod;
            }
        }
        c[i] = qsm(c[i],mod-2);
    }
    int ans = 0;
    for(int i=0 ;i<(1<<n) ;i++){
        if( p[i] <=m ){
            int x = 0;
            for(int j=0 ;j<n ;j++){
                x = ( x + qsm(a[j] , m - p[i]) * c[j]%mod )%mod;
            }
            ans = (ans + x*d[i]%mod )%mod;
        }
    }
    cout<<ans<<endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74