Description
Link：QOJ 8717
有 n 枚 m+1 面的骰子，m+1 个面上分别写着 0∼m，丢出第 i 枚骰子使得数字 j 朝上的概率永远是 pi,j。
你打算投 Q 轮骰子，第 i 次你会将编号在 [li,ri] 中的骰子全部掷出，将每个骰子面朝上的数字相加，设总和是 sum，若 sum≤m，你会获得 bsum 的开心度，否则你将什么都得不到。
请你求出每一轮投骰子，得到的开心度的期望是多少。答案对 109+7 取模。
数据范围：1≤n≤1500，1≤m≤200，1≤Q≤6×105。
时空限制：未知。
Solution
设 Fi=∑j=0mpi,jxj，则询问 [l,r] 的答案，相当于是求出 (∏l≤i≤rFi)modxm+1，然后再求出该多项式与向量 B=∑j=0mbjxj 点乘的值。
trick：若想要求出多项式 A 与向量 B 点乘的值，可以考虑将向量 B 进行翻转得到 B′=∑j=0mbm−jxj，此时点乘的值即为 [xm](A×B′)。
现在考虑如何快速求出 ∏l≤i≤rFi，一个朴素的想法是求出 F 的前缀积 prei，以及前缀积逆元 iprei。此时 prer×iprel−1 即为区间 F 之积。点乘的值即为 [xm](B′×prer×iprel−1)。
进一步，可以先预处理出所有的 B′×prer。此时求出两个多项式乘积的某一项，只需要 O(m) 的时间。
此时还有一个小 bug：若存在某个 F 的常数项为 0，则不可求逆。于是，对于一个有 s 个前导零的 F，我们先将其除以 xs（也就是将这些 0 先全都拿走）。最后回答询问时，记 s 表示区间 [l,r] 中 Fi 的前导零个数之和，则我们要求的值即为 [xm−s](B′×prer×iprel−1)。
时间复杂度 O(nm2+Qm)。代码中的多项式只实现了暴力乘法、暴力求逆。
By the way：分治可以绕过求逆，但时间复杂度为更高的 O(nm2logn+Qm)。
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
| #include <bits/stdc++.h>
#define debug(a) std::cout << #a << "=" << (a) << ' '
using s64 = long long;
using u64 = unsigned long long;
template <class T>
inline void chmin(T &x, const T &y) {
if (x > y) {
x = y;
}
}
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;
}
|