「2024 北京市赛」E. 骰子
有 n 枚 m + 1 面的骰子,m + 1 个面上分别写着 0 \sim m,丢出第 i 枚骰子使得数字 j 朝上的概率永远是 p_{i, j}。
你打算投 Q 轮骰子,第 i 次你会将编号在 [l_i, r_i] 中的骰子全部掷出,将每个骰子面朝上的数字相加,设总和是 \mathrm{sum},若 \mathrm{sum} \leq m,你会获得 b_{\mathrm{sum}} 的开心度,否则你将什么都得不到。
请你求出每一轮投骰子,得到的开心度的期望是多少。答案对 10^9 + 7 取模。
数据范围:1 \leq n \leq 1500,1 \leq m \leq 200,1 \leq Q \leq 6 \times 10^5。
时空限制:未知。
Solution
设 F_i = \sum_{j = 0}^m p_{i, j}x^j,则询问 [l, r] 的答案,相当于是求出 \left(\prod_{l \leq i \leq r} F_i\right) \bmod x^{m + 1},然后再求出该多项式与向量 B = \sum_{j = 0}^m b_jx^j 点乘的值。
trick:若想要求出多项式 A 与向量 B 点乘的值,可以考虑将向量 B 进行翻转得到 B' = \sum_{j = 0}^m b_{m - j}x^j,此时点乘的值即为 [x^m](A \times B')。
现在考虑如何快速求出 \prod_{l \leq i \leq r} F_i,一个朴素的想法是求出 F 的前缀积 \mathrm{pre}_i,以及前缀积逆元 \mathrm{ipre}_i。此时 \mathrm{pre}_r \times \mathrm{ipre}_{l - 1} 即为区间 F 之积。点乘的值即为 [x^m]\left( B' \times \mathrm{pre}_r \times \mathrm{ipre}_{l - 1} \right)。
进一步,可以先预处理出所有的 B' \times \mathrm{pre}_r。此时求出两个多项式乘积的某一项,只需要 \mathcal{O}(m) 的时间。
此时还有一个小 bug:若存在某个 F 的常数项为 0,则不可求逆。于是,对于一个有 s 个前导零的 F,我们先将其除以 x^s(也就是将这些 0 先全都拿走)。最后回答询问时,记 s 表示区间 [l, r] 中 F_i 的前导零个数之和,则我们要求的值即为 [x^{m - s}]\left( B' \times \mathrm{pre}_r \times \mathrm{ipre}_{l - 1} \right)。
时间复杂度 \mathcal{O}(nm^2 + Qm)。代码中的多项式只实现了暴力乘法、暴力求逆。
By the way:分治可以绕过求逆,但时间复杂度为更高的 \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
*/