「2024 北京市赛」E. 骰子

    「2024 北京市赛」E. 骰子

    QOJ 8717

    有 nn 枚 m+1m + 1 面的骰子,m+1m + 1 个面上分别写着 0∼m0 \sim m,丢出第 ii 枚骰子使得数字 jj 朝上的概率永远是 pi,jp_{i, j}。

    你打算投 QQ 轮骰子,第 ii 次你会将编号在 [li,ri][l_i, r_i] 中的骰子全部掷出,将每个骰子面朝上的数字相加,设总和是 sum\mathrm{sum},若 sum≤m\mathrm{sum} \leq m,你会获得 bsumb_{\mathrm{sum}} 的开心度,否则你将什么都得不到。

    请你求出每一轮投骰子,得到的开心度的期望是多少。答案对 109+710^9 + 7 取模。

    数据范围:1≤n≤15001 \leq n \leq 1500,1≤m≤2001 \leq m \leq 200,1≤Q≤6×1051 \leq Q \leq 6 \times 10^5。

    时空限制:未知。

    Solution

    设 Fi=∑j=0mpi,jxjF_i = \sum_{j = 0}^m p_{i, j}x^j,则询问 [l,r][l, r] 的答案,相当于是求出 (∏l≤i≤rFi) mod xm+1\left(\prod_{l \leq i \leq r} F_i\right) \bmod x^{m + 1},然后再求出该多项式与向量 B=∑j=0mbjxjB = \sum_{j = 0}^m b_jx^j 点乘的值。

    trick:若想要求出多项式 AA 与向量 BB 点乘的值,可以考虑将向量 BB 进行翻转得到 B′=∑j=0mbm−jxjB' = \sum_{j = 0}^m b_{m - j}x^j,此时点乘的值即为 [xm](A×B′)[x^m](A \times B')。

    现在考虑如何快速求出 ∏l≤i≤rFi\prod_{l \leq i \leq r} F_i,一个朴素的想法是求出 FF 的前缀积 prei\mathrm{pre}_i,以及前缀积逆元 iprei\mathrm{ipre}_i。此时 prer×iprel−1\mathrm{pre}_r \times \mathrm{ipre}_{l - 1} 即为区间 FF 之积。点乘的值即为 [xm](B′×prer×iprel−1)[x^m]\left( B' \times \mathrm{pre}_r \times \mathrm{ipre}_{l - 1} \right)。

    进一步,可以先预处理出所有的 B′×prerB' \times \mathrm{pre}_r。此时求出两个多项式乘积的某一项,只需要 O(m)\mathcal{O}(m) 的时间。

    此时还有一个小 bug:若存在某个 FF 的常数项为 00,则不可求逆。于是,对于一个有 ss 个前导零的 FF,我们先将其除以 xsx^s(也就是将这些 00 先全都拿走)。最后回答询问时,记 ss 表示区间 [l,r][l, r] 中 FiF_i 的前导零个数之和,则我们要求的值即为 [xm−s](B′×prer×iprel−1)[x^{m - s}]\left( B' \times \mathrm{pre}_r \times \mathrm{ipre}_{l - 1} \right)。

    时间复杂度 O(nm2+Qm)\mathcal{O}(nm^2 + Qm)。代码中的多项式只实现了暴力乘法、暴力求逆。

    By the way:分治可以绕过求逆,但时间复杂度为更高的 O(nm2log⁡n+Qm)\mathcal{O}(nm^2 \log n + Qm)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    const int mod = 1e9 + 7; // 模数需根据实际问题调整
    
    /* 模意义下 加法 */
    inline void add(int &x, const int &y) {
        x += y;
        if (x >= mod) {
            x -= mod;
        }
    }
    
    /* 模意义下 减法 */
    inline void dec(int &x, const int &y) {
        x -= y;
        if (x < 0) {
            x += mod;
        }
    }
    
    /* 模意义下 乘法 */
    inline void mul(int &x, const int &y) {
        x = 1ll * x * y % mod;
    }
    
    /* 快速幂 */
    int qpow(int a, int b, int p) {
        int ans = 1;
        for (; b; b >>= 1) {
            if (b & 1) ans = 1ll * ans * a % p;
            a = 1ll * a * a % p;
        }
        return ans;
    }
    
    struct poly : public std::vector<int> {
        poly() : std::vector<int>() {}
        explicit constexpr poly(int n) : std::vector<int>(n) {}
        explicit constexpr poly(const std::vector<int> &a) : std::vector<int>(a) {}
        constexpr poly(const std::initializer_list<int> &a) : std::vector<int>(a) {}
    
        template <class InputIt, class = std::_RequireInputIter<InputIt>>
        explicit constexpr poly(InputIt st, InputIt ed) : std::vector<int>(st, ed) {}
    
        // 多项式乘法(暴力)
        constexpr friend poly mul_bf(poly a, poly b) {
            poly c(a.size() + b.size() - 1);
            for (int i = 0; i < a.size(); i ++) {
                for (int j = 0; j < b.size(); j ++) {
                    c[i + j] = (c[i + j] + 1ll * a[i] * b[j]) % mod;
                }
            }
            return c;
        }
    
        constexpr poly divxk(int k) const {
            if (k >= size()) return poly();
            return poly((*this).begin() + k, (*this).end());
        }
    
        // 少项式求逆
        constexpr poly inv_bf(int m) const {
            int n = size() - 1, inv = qpow((*this)[0], mod - 2, mod);
            poly b(m);
            for (int i = 0; i < m; i ++) {
                b[i] = i == 0;
                for (int j = std::max(0, i - n); j < i; j ++) {
                    dec(b[i], 1ll * b[j] * (*this)[i - j] % mod);
                }
                mul(b[i], inv);
            }
            return b;
        }
    };
    
    const int N = 1510, M = 210;
    
    int n, m, Q;
    
    poly b;
    poly pre[N], ipre[N];
    
    int sum[N];
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> n >> m >> Q;
    
        b.resize(m + 1);
        for (int i = 0; i <= m; i ++) {
            std::cin >> b[i];
        }
    
        pre[0].resize(m + 1);
        pre[0][0] = 1;
    
        for (int i = 1; i <= n; i ++) {
            poly cur(m + 1);
            for (int j = 0; j <= m; j ++) {
                std::cin >> cur[j];
                cur[j] %= mod;
            }
    
            int p = 0;
            while (p <= m && !cur[p]) {
                p ++;
            }
            assert(p <= m);
    
            pre[i] = mul_bf(pre[i - 1], cur.divxk(p));
            pre[i].resize(m + 1);
    
            sum[i] = sum[i - 1] + p;
        }
    
        for (int i = 0; i <= n; i ++) {
            ipre[i] = pre[i].inv_bf(m + 1);
        }
    
        std::reverse(b.begin(), b.end());
        for (int i = 1; i <= n; i ++) {
            pre[i] = mul_bf(pre[i], b);
        }
    
        while (Q --) {
            int l, r;
            std::cin >> l >> r;
    
            int s = sum[r] - sum[l - 1];
            int x = m - s;
    
            if (x < 0) {
                std::cout << 0 << '\n';
                continue;
            }
    
            int ans = 0;
            for (int i = 0; i <= x; i ++) {
                ans = (ans + 1ll * pre[r][i] * ipre[l - 1][x - i]) % mod;
            }
    
            std::cout << ans << '\n';
        }
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/
    
    /*
    3 3 3
    4 3 2 1
    0 1 0 1000000007
    0 500000004 0 500000004
    0 0 500000004 500000004
    1 1
    1 2
    1 3
    
    3 3 6
    4 3 2 1
    1000000007 0 1 0
    1000000007 1 0 0
    1000000007 0 1 0
    1 1
    1 2
    1 3
    2 2
    2 3
    3 3
    */