CFGYM103415A CCPC2021广州A Math Ball

题意: 有$n$种球,每种有无限个,同时第$i$种球有一个代价$c_i$,你要拿不超过$w$个球。如果最后第$i$种球你拿了$k_i$个,那么你会获得$\prod_{1\leq i\leq n}{k_i^{c_i}}$的权值,求所有合法方案的权值和。$n\leq 1e5,\sum{c_i}\leq 1e5,w\leq 10^{18}$

$$  \text{考虑对于价值是}c_i\text{的球,构造生成函数}  \\  F_{c_i}\left( x \right) =\sum_{n\ge 0}{n^{c_i}x^n}  \\  \text{这样}\frac{\prod_i{F_{c_i}\left( x \right)}}{1-x}\text{的}w\text{次项即为答案}  \\  \text{设}F_k\left( x \right) =\sum_{n\ge 0}{n^kx^n},\text{显然可得}F_k\left( x \right) =x\frac{\mathrm{d}F_{k-1}\left( x \right)}{\mathrm{d}x}  \\  \text{进一步递推可得}, F_k\left( x \right) =\frac{\sum_{0\le i\le k}{T\left( k,i \right) x^i}}{\left( 1-x \right) ^{k+1}},\text{其中}T\left( k,i \right) \text{表示欧拉数}  \\  \text{考虑如何快速计算欧拉数}  \\  \text{首先由具体数学可得}  \\  \sum_{0\le i\le k}{T\left( k,i \right) \times \left( z+1 \right) ^i}=\sum_{0\le i\le k}{S_2\left( k,i \right) \times i!\times z^{k-i}}  \\  \text{进一步推导得欧拉数的通项公式}T\left( n,k \right) =\sum_{0\le i\le k}{\begin{array}{c}    \binom{n+1}{i}\left( -1 \right) ^i\left( k+1-i \right) ^n\\  \end{array}}  \\  \text{构造卷积形式}T\left( n,k \right) =\left( n+1 \right) !\sum_{0\le i\le k}{\frac{\left( -1 \right) ^i}{i!\left( n+1-i \right) !}}\times \left( k+1-i \right) ^n  \\  \text{卷积即可求出一行欧拉数。}  \\  \text{现在我们可以对每一个}c_i\text{计算出}F_{c_i}\left( x \right) \text{的分子,并且得到他们分子的乘积,设为}F\left( x \right)   \\  \text{设他们分母的乘积,再乘个}1-x\text{为}\left( 1-x \right) ^k  \\  \text{则答案即为}\frac{F\left( x \right)}{\left( 1-x \right) ^k}\text{的}w\text{次项系数}  \\  \text{即}\sum_{0\le i\le n}{\left[ x^i \right] F\left( x \right) \binom{w-i+k-1}{w-i}}\left( \text{广义二项式定理展开分母} \right)   \\  \text{令}a_i=\left[ x^i \right] F\left( x \right)   \\  \text{即}\sum_{0\le i\le n}{a_i\binom{w-i+k-1}{k-1}}  \\  \text{后者可以通过递推快速转移。}  \\    \\    \\  \frac{x^a}{\left( 1-x \right) ^b}=x^a\left( \sum_{n\ge 0}{\binom{-b}{n}\left( -1 \right) ^n}x^n \right)   \\  =x^a\left( \sum_{n\ge 0}{\frac{\left( -b \right) ^{\underline{n}}}{n!}\left( -1 \right) ^n}x^n \right)   \\  =x^a\left( \sum_{n\ge 0}{\frac{\left( -b-0 \right) \left( -b-1 \right) \left( -b-2 \right) ..\left( -b-\left( n-1 \right) \right)}{n!}\left( -1 \right) ^n}x^n \right)   \\  =x^a\left( \sum_{n\ge 0}{\frac{\left( b+0 \right) \left( b+1 \right) \left( b+2 \right) ..\left( b+\left( n-1 \right) \right)}{n!}}x^n \right)   \\  =x^a\left( \sum_{n\ge 0}{\frac{\left( b+n-1 \right) ^{\underline{n}}}{n!}}x^n \right)   \\  =\sum_{n\ge 0}{\frac{\left( b+n-1 \right) ^{\underline{n}}}{n!}x^{n+a}}  \\  =\sum_{n\ge 0}{\binom{b+n-1}{n}x^{n+a}}  \\  =\sum_{n\ge a}{\binom{b+n-a-1}{n-a}x^n}  \\  =\sum_{n\ge a}{\binom{b+n-a-1}{b-1}x^n}  \\  =\sum_{n\ge a}{\begin{array}{c}     \frac{\left( b-a+n-1 \right) ^{\underline{b-1}}}{\left( b-1 \right) !}x^n\\  \end{array}}  \\  \text{令}t=b-1  \\  \text{则}  \\  \sum_{n\ge a}{\begin{array}{c}      \frac{\left( t-a+n \right) ^{\underline{t}}}{t!}x^n\\  \end{array}}  \\  \text{从}a\text{推进到}a+1  \\  \frac{\left( t-a+n \right) ^{\underline{t}}}{\left( t-a+n-1 \right) ^{\underline{t}}}=\frac{t-a+n}{n-a}  \\    \\  10*9*8/\left( 9*8*7 \right) =10/7  \\    \\  \left( \frac{x^a}{\left( 1-x \right) ^b}\text{的}n\text{次项} \right)   \\    \\  \binom{n+b-1}{n}=\binom{n+b-1}{b-1}  \\  \binom{n+b-1}{n}\rightarrow \binom{n+b}{n+1}  \\    \\  \frac{\binom{n+b}{n+1}}{\binom{n+b-1}{n}}=\frac{n+b}{\left( n+1 \right)}  \\    \\  \frac{\left( n-2+b-i \right) !\left( b-1 \right) !\left( n-i \right) !}{\left( b-1 \right) !\left( n-i-1 \right) !\left( n-i+b-1 \right) !}  \\    \\  \frac{\left( n-i+b-2 \right) !\left( n-i \right)}{\left( n-i+b-1 \right) !}  \\  \frac{\left( n-i \right)}{\left( n-i+b-1 \right)}  \\    \\    $$
#include <cinttypes>
#include <cstring>
#include <fstream>
#include <iostream>
#include <random>
using int_t = int;
using std::cin;
using std::cout;
using std::endl;

const int_t LARGE = 2e6;

using i64 = int64_t;
#ifdef NTTCNT
std::ofstream nttcnt("nttcnt.txt");
#endif
const int_t mod = 998244353;
const int_t g = 3;

int_t power(int_t b, int_t i) {
    int_t r = 1;
    if (i < 0)
        i = ((i64)i % (mod - 1) + mod - 1) % (mod - 1);
    while (i) {
        if (i & 1)
            r = (i64)r * b % mod;
        b = (i64)b * b % mod;
        i >>= 1;
    }
    return r;
}

void makeflip(int_t* arr, int_t size2) {
    int_t len = (1 << size2);
    arr[0] = 0;
    for (int_t i = 1; i < len; i++) {
        arr[i] = (arr[i >> 1] >> 1) | ((i & 1) << (size2 - 1));
    }
}

int_t upper2n(int_t x) {
    int_t r = 0;
    while ((1 << r) < x)
        r++;
    return r;
}
template <int_t arg = 1>
void transform(int_t* A, int_t size2, int_t* flip) {
    // #define int_t i64
    int_t len = (1 << size2);
#ifdef NTTCNT
    nttcnt << len << endl;
#endif
    for (int_t i = 0; i < len; i++) {
        int_t r = flip[i];
        if (r > i)
            std::swap(A[i], A[r]);
    }
    for (int_t i = 2; i <= len; i *= 2) {
        int_t mr = power(g, (i64)arg * (mod - 1) / i);
        for (int_t j = 0; j < len; j += i) {
            int_t curr = 1;
            for (int_t k = 0; k < i / 2; k++) {
                int_t u = A[j + k], v = (i64)curr * A[j + k + i / 2] % mod;
                A[j + k] = ((i64)u + v) % mod;
                A[j + k + i / 2] = ((i64)u - v + mod) % mod;
                curr = (i64)curr * mr % mod;
            }
        }
    }
    // #undef int_t
}
void poly_mul(const int_t* A, int_t n, const int_t* B, int_t m, int_t* C) {
    /*
       计算n次多项式A与m次多项式B的乘积
    */
    int_t size2 = upper2n(n + m + 1);
    int_t len = 1 << size2;
    static int_t T1[LARGE], T2[LARGE];
    for (int_t i = 0; i < len; i++) {
        if (i <= n)
            T1[i] = A[i];
        else
            T1[i] = 0;
        if (i <= m)
            T2[i] = B[i];
        else
            T2[i] = 0;
    }
    static int_t fliparr[LARGE];
    makeflip(fliparr, size2);
    transform(T1, size2, fliparr);
    transform(T2, size2, fliparr);
    for (int_t i = 0; i < len; i++)
        T1[i] = (i64)T1[i] * T2[i] % mod;
    transform<-1>(T1, size2, fliparr);
    int_t inv = power(len, -1);
    for (int_t i = 0; i <= n + m; i++)
        C[i] = (i64)T1[i] * inv % mod;
}

const int_t FLARGE = 2e5 + 10;

int_t fact[FLARGE + 1], inv[FLARGE + 1], factInv[FLARGE + 1];
void euler_num(int_t n, int_t* out) {
    static int_t P1[LARGE];
    static int_t P2[LARGE];
    for (int_t i = 0; i <= n; i++) {
        P1[i] = (i64)((i % 2) ? (mod - 1) : 1) * factInv[i] % mod *
                factInv[n + 1 - i] % mod;
        P2[i] = power(i, n);
    }
    poly_mul(P1, n, P2, n, out);
    for (int_t i = 0; i <= n; i++)
        out[i] = (i64)out[i] * fact[n + 1] % mod;
}

using poly_t = std::vector<int_t>;
poly_t poly_dcmul(const poly_t* P, int_t left, int_t right) {
    if (left == right)
        return P[left];
    int_t mid = (left + right) / 2;
    auto lret = poly_dcmul(P, left, mid);
    auto rret = poly_dcmul(P, mid + 1, right);
    poly_t ret;
    ret.resize(lret.size() - 1 + rret.size() - 1 + 1);
    poly_mul(&lret[0], lret.size() - 1, &rret[0], rret.size() - 1, &ret[0]);
    while (!ret.empty() && ret.back() == 0)
        ret.pop_back();
    return ret;
}
int_t C(int_t n, int_t m) {
    return (i64)fact[n] * factInv[m] % mod * factInv[n - m] % mod;
}
i64 getC(i64 n, int_t m) {
    if (n < 0 || n < m)
        return 0;
    i64 prod = 1;
    for (int_t i = 0; i < m; i++)
        prod = prod * (n % mod - i + mod) % mod;
    return prod * factInv[m] % mod;
}
int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    {
        fact[0] = fact[1] = inv[1] = factInv[0] = factInv[1] = 1;
        for (int_t i = 2; i <= FLARGE; i++) {
            fact[i] = (i64)fact[i - 1] * i % mod;
            inv[i] = (i64)(mod - mod / i) * inv[mod % i] % mod;
            factInv[i] = (i64)factInv[i - 1] * inv[i] % mod;
        }
    }
    int_t n;
    i64 w;
    cin >> n >> w;

    static poly_t up[int_t(1e5 + 10)];
    static poly_t cache[int_t(1e5 + 10)];
    int_t sum = 0;
    for (int_t i = 1; i <= n; i++) {
        int_t c;
        cin >> c;
        sum += c + 1;
        poly_t& curr = up[i];
        if (!cache[c].empty()) {
            curr = cache[c];
            continue;
        }
        curr.resize(2 * c + 3);
        euler_num(c, &curr[0]);
        curr.resize(c + 1);
        cache[c] = curr;
#ifdef DEBUG
        cout << "up " << i << " = ";
        for (auto t : curr)
            cout << t << " ";
        cout << endl;
#endif
    }
    sum++;
    // for (int_t i = 0; i <= sum; i++) {
    //     down[i] = (i64)((i % 2) ? (mod - 1) : 1) * C(sum, i) % mod;
    // }
    auto upprod = poly_dcmul(up, 1, n);
    // cout << upprod.size() << endl;
    upprod.resize(sum + 1);
#ifdef DEBUG
    cout << "up prod = ";
    for (auto t : upprod)
        cout << t << " ";
    cout << endl;
    cout << "sum = " << sum << endl;
#endif
    // cout << "down size = " << sum << endl;
    // w -= cutcount;
    // if (w < 0) {
    //     cout << 0 << endl;
    //     return 0;
    // }
    // int_t ret = poly_divat(&upprod[0], down, upprod.size() - 1, sum, w);
    i64 ret = 0;
    {
        i64 b = sum;
        i64 n = w;
        i64 curr = getC(n - 0 + b - 1, b - 1);
// C(n-i+b-1,b-1)到C(n-(i+1)+b-1,b-1)
// getC(n - i + b - 1, b - 1)
#ifdef DEBUG
        cout << "init curr = " << curr << endl;
#endif
        for (i64 i = 0; i < upprod.size(); i++) {
            ret = (ret + upprod[i] * curr % mod) % mod;
            curr = curr * (n % mod - i + mod) % mod *
                   power((n % mod - i + b - 1 + (i64)3 * mod) % mod, -1) % mod;
            if (curr == 0 || n <= i - n + 1)
                break;
#ifdef DEBUG
            cout << "curr = " << curr << " at i = " << i << " with n = " << n
                 << endl;
#endif
        }
        // int_t curr = getC(w - b + b - 1, b - 1);
        // for (i64 i = std::max<i64>(0, w - sum); i < upprod.size(); i++) {
        //     ret = (ret + curr * upprod[i] % mod) % mod;
        //     curr = curr * (n % mod + n % mod - sum % mod + mod + i) % mod *
        //            power(n + 1, -1) % mod;
        // }
        // i64 n = w;
        // i64 t = sum - 1;
        // i64 prod = 1;
        // // i64 curr = (t + n) % mod;
        // for (int_t i = 0; i < t; i++)
        //     prod = (prod * (t + n % mod - i) % mod);
        // for (int_t a = 0; a < upprod.size(); a++) {
        //     if (n >= a) {
        //         ret = (ret + prod * factInv[t] % mod * upprod[a] % mod) %
        //         mod;
        //     }
        //     prod = prod * (t - a + n % mod) % mod *
        //            power((n % mod - a + mod) % mod, -1) % mod;
        // }
    }
    cout << ret << endl;
    return 0;
}

 

评论

《“CFGYM103415A CCPC2021广州A Math Ball”》 有 1 条评论

  1. 物灵 的头像

    谢谢您还在

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理