题解：P15375 Soso 的模法矩阵 / modmat
yukimianyan
·
·
题解
希望大家喜欢这个题目。
题目描述
记 \{a_i\} 的前缀积数组为 A，\{b_j\} 的前缀积数组为 B。对每对 i, j 求 (A_i\bmod B_j)\bmod 998244353。
## subtask 1
答案要么是 $a_i$ 的一段前缀的积，要么是 $0$。
## subtask 2
观察到 $15^{15}\leq 10^{18}$。暴力计算答案。
## subtask 5
用十进制高精度计算 $A$，则 $A_i\bmod 10^j$ 可以表示为 $A$ 的低 $j$ 位。精细实现应该可以 $O(nm)$。
## subtask 7
预期使用高精度取模通过，复杂度根据实现决定，Python 等自带高精度的语言写的程序有可能可以通过。
## subtask 10
**维护变进制数**。从小到大枚举 $i$，时刻维护一个长为 $m+1$ 的非负整数数组 $c_i$ 使得
- 对所有 $1\leq i\leq m$，都有 $0\leq c_i<b_i$。
- $\prod_{i=1}^{i_0}a_i=\sum_{j=1}^{m+1}c_j\prod_{k=1}^{j-1}b_k$。
当 $i$ 加一时，考虑从小到大枚举 $j$，将 $c_j$ 乘上 $a_{i+1}$，若 $c_j\geq b_j$，则使 $c_{j+1}$ 加上 $\left\lfloor c_j/b_j\right\rfloor$，并将 $c_j$ 改为 $c_j\bmod b_j$。显然这样仍然满足上述的两条性质。
求解答案时，答案就是 $c_i$ 的低 $j$ 个数（$c[1..j]$）组成的变进制数对应的原数。精细实现可以在 $O(nm)$ 的时间复杂度内解决原问题。
subtask 8, 9 预留给常数较大或者需要求逆元的程序通过。
## std
```cpp
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
template <class T>
using must_int = enable_if_t<is_integral<T>::value, int>;
template <unsigned umod>
struct modint {/*{{{*/
static constexpr int mod = umod;
unsigned v;
modint() : v(0) {}
template <class T, must_int<T> = 0>
modint(T x) {
x %= mod;
v = x < 0 ? x + mod : x;
}
modint operator+() const { return *this; }
modint operator-() const { return modint() - *this; }
friend int raw(const modint &self) { return self.v; }
friend ostream& operator<<(ostream& os, const modint &self) {
return os << raw(self);
}
modint &operator+=(const modint &rhs) {
v += rhs.v;
if (v >= umod) v -= umod;
return *this;
}
modint &operator-=(const modint &rhs) {
v -= rhs.v;
if (v >= umod) v += umod;
return *this;
}
modint &operator*=(const modint &rhs) {
v = 1ull * v * rhs.v % umod;
return *this;
}
modint &operator/=(const modint &rhs) {
assert(rhs.v);
return *this *= qpow(rhs, mod - 2);
}
template <class T, must_int<T> = 0>
friend modint qpow(modint a, T b) {
modint r = 1;
for (; b; b >>= 1, a *= a)
if (b & 1) r *= a;
return r;
}
friend modint operator+(modint lhs, const modint &rhs) { return lhs += rhs; }
friend modint operator-(modint lhs, const modint &rhs) { return lhs -= rhs; }
friend modint operator*(modint lhs, const modint &rhs) { return lhs *= rhs; }
friend modint operator/(modint lhs, const modint &rhs) { return lhs /= rhs; }
bool operator==(const modint &rhs) const { return v == rhs.v; }
bool operator!=(const modint &rhs) const { return v != rhs.v; }
};/*}}}*/
using mint = modint<998244353>;
using modi = modint<int(1e9 + 7)>;
int n, m, a[5010], b[5010];
LL c[5010];
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> m >> n;
for (int j = 1; j <= m; j++) cin >> b[j];
for (int i = 1; i <= n; i++) cin >> a[i];
c[1] = 1;
for (int j = 1; j <= m; j++) {
mint ret = 0, pre = 1;
LL s = 0;
modi ans = 0;
for (int i = 1; i <= n; i++) {
LL tmp = c[i] * b[j] + s;
c[i] = tmp % a[i];
ret += pre * c[i];
pre *= a[i];
s = tmp / a[i];
ans = ans * 998244353 + raw(ret);
}
cout << ans << endl;
}
return 0;
}
```