ABC300E Dice Product 3
题意
初始一个整数为 \(1\)，你有一个可以等概率地掷出 \(1\) 至 \(6\) 这六个数值的骰子，再给定一个整数 \(N\)，当初始给出的整数严格小于 \(N\) 时，重复以下操作：
- 掷一次骰子，将初始给出的整数乘上你掷出来的数字。
求出最终得到 \(N\) 的概率模上 \(998244353\) 的值。
思路
先判无解。由于骰子只能掷出 \(1\) 至 \(6\) 的值，而 \([1, 6]\) 中共有三个质数 \(2\)，\(3\) 与 \(5\)，因此如果一个整数能由以上操作得到，则其一定能被分解为 \(2^{a}3^{b}5^{c}\) 的形式，否则无论如何也不能得到。
我们令 \(P(x)\) 为当前数为 \(x\) 时，最终得到 \(N\) 的概率。不难得到当当前得到的数字已经比 \(N\) 还大时，得到 \(N\) 的概率为 \(0\)，而当 \(x = N\)，即我们已得到 \(N\) 时，概率为 \(1\)。而当当前数字比 \(N\) 小时，根据题意，需要再掷一次骰子并将当前得到的数乘上投出来的数。于是我们可以写出如下的方程：
\[P(x) =
\begin{cases}
0 & x \gt N \\
1 & x = N \\
\frac{P(x) + P(2x) + P(3x) + P(4x) + P(5x) + P(6x)}{6} & x \lt N
\end{cases}
\]
第三种情况的式子有点怪，两边都有 \(P(x)\)，因此我们考虑移项：
\[\begin{align*}
P(x) &= \frac{P(x)}{6} + \frac{P(2x) + P(3x) + P(4x) + P(5x) + P(6x)}{6} \\
\frac{5P(x)}{6} &= \frac{P(2x) + P(3x) + P(4x) + P(5x) + P(6x)}{6} \\
P(x) &= \frac{P(2x) + P(3x) + P(4x) + P(5x) + P(6x)}{5}
\end{align*}
\]
然后就做完了，由于这个式子显然没有后效性，因此我们可以记忆化，但是由于要模上 \(998244353\)，因此不能使用普通的数组，而是要用 map 状物来保存计算值。
代码
使用了 AtCoder 官方黑科技 atcoder_library，用于简化逆元计算。这个代码写得还是有点复杂，其实还有很多地方可以简化。
#include <atcoder/modint.hpp>
#include <bits/stdc++.h>
using i64 = long long;
using f80 = long double;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
i64 n;
std::cin >> n;
i64 copy = n;
std::vector<int> factor(6);
for (auto i : {5, 3, 2}) {
while (copy % i == 0) {
copy /= i;
factor[i]++;
}
if (copy == 1) {
break;
}
}
if (copy != 1) {
std::cout << 0 << "\n";
return 0;
}
std::map<i64, atcoder::modint998244353> mp;
std::function<atcoder::modint998244353(i64)> dfs = [&](i64 cur) -> atcoder::modint998244353 {
if (cur == n) {
return 1;
} else if (cur > n) {
return 0;
} else if (mp.count(cur)) {
return mp[cur];
}
atcoder::modint998244353 res = 0;
for (int i = 2; i <= 6; i++) {
res += dfs(i * cur) / 6;
}
return mp[cur] = res * atcoder::modint998244353(6) / atcoder::modint998244353(5);
};
std::cout << dfs(1).val() << "\n";
return 0;
}