一些记号
下文中令 \(d_p(x)=\max\limits_{k\in\mathbb{N},p^k\mid x}k\)。
题意
对于 \(x\in\mathbb{Q}^{+}\)，设 \(x=\dfrac{p}{q}\)，其中 \(p,q\) 为互质正整数，令 \(f(x)=pq\)。给定长度为 \(n-1\) 的序列 \(a\)，定义一个长度为 \(n\) 的序列 \(s\) 是好序列当且仅当：
- \(\forall 1\leq i<n,f\left(\dfrac{s_i}{s_{i+1}}\right)=a_i\)。
- \(\gcd\limits_{i=1}^ns_i=1\)。
求所有好序列的元素乘积之和，答案对 \(998244353\) 取模。\(2\leq n\leq 10^3\)，\(1\leq a_i\leq 10^3\)。
题解
唐诗题，一眼秒了。
化简一下 \(f\)，显然
整体不好考虑，但是可以拆到每个质数 \(p\) 的指数上考虑，这样限制化成了：
- \(\forall 1\leq i<n,\max(d_p(s_i),d_p(s_{i+1}))-\min(d_p(s_i),d_p(s_{i+1}))=d_p(a_i)\)。
- \(\min\limits_{i=1}^nd_p(s_i)=0\)。
可以发现质数之间是独立的，所以我们可以对每个质数 \(p\)，求出所有好序列只保留 \(p\) 因子后的乘积之和，然后再全部乘起来。
于是考虑枚举 \(p\) 后 DP。令 \(f_{i,j,c}\) 表示考虑了前 \(i\) 个数，\(d_p(s_i)=j\)，\(c\in \{0,1\}\) 表示前 \(i\) 个数中是否存在指数为 \(0\) 的数，所有方案的乘积之和。转移是容易的：
预处理 \(p\) 的幂即可 \(\mathcal{O}(1)\) 转移。注意 \(d_p(a_{i-1})=0\) 时只能转移一次。答案显然是 \(\sum f_{n,j,1}\)。
考虑一下 \(j\) 的范围。由于限制了至少要有 \(1\) 个 \(0\)，所以最坏情况就是令 \(d_p(s_1)=0\)，然后对于 \(2\leq i\leq n\)，令 \(d_p(s_i)=d_p(s_{i-1})+d_p(a_{i-1})\)。因此 \(j\) 的上限就是 \(\sum d_p(a_i)\)。于是对于所有的 \(p\)，\(j\) 的上限的总和是 \(\mathcal{O}(n\log{V})\) 的。时间复杂度为 \(\mathcal{O}(n^2\log{V})\)。
代码
#include <bits/stdc++.h>using namespace std;#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 1e3 + 5, LGN = 10, MOD = 998244353;template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
inline void cadd(int &x, int y) { x += y, x < MOD || (x -= MOD); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += MOD); }int n, v, ans = 1, a[N], k[N], f[N][N * LGN][2], pw[N * LGN];
int sz, pr[N];
bool vis[N];void sieve(int n) {for (int i = 2; i <= n; ++i) {if (!vis[i]) pr[++sz] = i;for (int j = 1; j <= sz && i * pr[j] <= n; ++j) {int p = pr[j], x = i * p;vis[x] = 1;if (!(i % p)) break;}}
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i < n; ++i) cin >> a[i], chk_max(v, a[i]);sieve(v);for (int t = 1; t <= sz; ++t) {int p = pr[t], s = 0;for (int i = 1; i < n; ++i) {k[i] = 0;while (!(a[i] % p)) a[i] /= p, ++k[i];s += k[i];}pw[0] = 1;for (int i = 1; i <= s; ++i) pw[i] = (ll)pw[i - 1] * p % MOD;for (int i = 0; i <= s; ++i) f[0][i][!i] = pw[i];for (int i = 1; i < n; ++i) for (int j = 0; j <= s; ++j) for (int o : {0, 1}) {f[i][j][o] = 0;for (int q : {0, 1}) if ((q || !j) == o) {if (j >= k[i]) cadd(f[i][j][o], (ll)pw[j] * f[i - 1][j - k[i]][q] % MOD);if (j + k[i] <= s && k[i]) cadd(f[i][j][o], (ll)pw[j] * f[i - 1][j + k[i]][q] % MOD);}}int sum = 0;for (int j = 0; j <= s; ++j) cadd(sum, f[n - 1][j][1]);ans = (ll)ans * sum % MOD;}cout << ans;return 0;
}