Atcoder 241

Atcoder 241

\(Ex. Card Deck Score\)

题意

给定\(N\)种物品，每种物品价值为\(A_i\)，个数为\(B_i\)。现在要选取\(W\)个物品，设第\(i\)种物品选了\(K_i\)个，那么一种选法的总价值就是\(\prod_{i=1}^nA_i^{k_i}\)，现在要你求所有方案的总价值和。答案对\(998244353\)取模

\(1\le N\le 16\) \(1\le W\le 10^{18}\) \(1\le A_i\le 998244353\) \(1\le B_i\le 10^{17}\)

保证\(A_i\)两两互不相等。

Sol

容易写出生成函数为\(F(x)=\prod_{i=1}^n\sum_{j=0}^{B_i}(A_ix)^j=\prod_{i=1}^n\frac{1-(A_ix)^{B_i+1}}{1-A_ix}\)

由于\(N\)最大为\(16\)，所以分子可以在\(O(2^n)\)内求出所有项的系数，由于我们需要的是\([x^W]F(x)\)，但分式不好计算，考虑乘积项。

考虑部分分式分解：\(\frac{1}{\prod_{i=1}^n(1-A_ix)}=\frac{c_1}{1-A_1x}+\frac{c_2}{1-A_2x}+...+\frac{1}{1-A_nx}\)

设当前求系数\(c_j\)，那么将上面的式子变形为\(\frac{1}{\prod_{i=1\ and \ i!=j}^n(1-A_ix)}=\frac{c_1(1-A_jx)}{1-A_1x}+\frac{c_2(1-A_jx)}{1-A_2x}+...c_j+...+\frac{c_n(1-A_jx)}{1-A_nx}\)

取\(x=A_j^{-1}\)，在模\(998244353\)意义下，\(1-A_jA_j^{-1}=0\)。那么上式变为\(c_j=\frac{1}{\prod_{i=1\ and \ i!=j}^n(1-A_iA_j^{-1})}\)

又\(\frac{c_i}{1-A_ix}=c_i\sum_{j=0}^{\infty}(A_ix)^j\)，用级数展开。

则\(F(x)=\prod_{i=1}^n\frac{1-(A_ix)^{B_i+1}}{1-A_ix}=\prod_{i=1}^n(1-(A_ix)^{B_i+1})\sum_{i=1}^nc_i\sum_{j=0}^{\infty}(A_ix)^j\)

#include 
using namespace std;
constexpr int P = 998244353;
using i64 = long long;
i64 power(i64 a, i64 b) {
    i64 res = 1LL;
    for (; b; b /= 2, a = a*a%P) {
        if (b % 2) {
            res =res*a%P;
        }
    }
    return res;
}

int main()
{
   ios::sync_with_stdio(false);
   cin.tie(nullptr);
   int n;
   i64 m;
   cin>>n>>m;
   vectorA(n),B(n),p(1<>A[i]>>B[i];
     B[i]++;
     i64 x=(-power(A[i],B[i])+P)%P;
     for(int j=0;j<1<c(n);
   for(int i=0;im) continue;
      //cout<