admin官方

小数据做法

对于 n≤5, ai≤5n \le 5,\ a_i \le 5 的数据，可以直接枚举所有可能的序列 bb。

对每个 ii，bi+nb_{i+n} 必须是 aia_i 的因子，bib_i 必须是 bi+nb_{i+n} 的因子。先把每个位置所有合法的 (bi,bi+n)(b_i,b_{i+n}) 列出来，再做 DFS 枚举所有组合，最后检查

∏i=1nbi+n≤∏i=1nbi2\prod_{i=1}^{n} b_{i+n} \le \prod_{i=1}^{n} b_i^2

即可。

小数据下因子数量很少，这种做法可以通过。

单质数做法

如果所有 aia_i 都是 22 的幂，设

ai=2ci.a_i=2^{c_i}.

令 bi+nb_{i+n} 中 22 的指数为 kik_i，bib_i 中 22 的指数为 tit_i。由于 bi∣bi+n∣aib_i\mid b_{i+n}\mid a_i，有

0≤ti≤ki≤ci.0\le t_i\le k_i\le c_i.

条件 2 等价于

∑i=1nki≤2∑i=1nti,\sum_{i=1}^{n} k_i \le 2\sum_{i=1}^{n} t_i,

也就是

∑i=1n(2ti−ki)≥0.\sum_{i=1}^{n}(2t_i-k_i)\ge 0.

于是可以做背包 DP。设 dp[i][s]\text{dp}[i][s] 表示考虑前 ii 个位置，当前 ∑(2t−k)=s\sum(2t-k)=s 的方案数。转移时枚举 ki,tik_i,t_i。由于指数总和不超过 100log⁡2109100\log_2 10^9，状态数是可接受的。

100 分做法

直接统计不等式一侧会遇到多个质数之间的耦合。关键是利用对称性。

对于每个 ii，令

xi=bi,yi=bi+nbi.x_i=b_i,\qquad y_i=\frac{b_{i+n}}{b_i}.

因为 bi∣bi+nb_i\mid b_{i+n}，所以 yiy_i 是正整数。又因为 bi+n∣aib_{i+n}\mid a_i，所以

xiyi∣ai.x_i y_i \mid a_i.

条件 2 变为

∏i=1nxiyi≤∏i=1nxi2,\prod_{i=1}^{n} x_i y_i \le \prod_{i=1}^{n} x_i^2,

即

∏i=1nyi≤∏i=1nxi.\prod_{i=1}^{n} y_i \le \prod_{i=1}^{n} x_i.

现在所有合法选择就是若干组 (xi,yi)(x_i,y_i)，满足 xiyi∣aix_i y_i\mid a_i。如果把所有 (xi,yi)(x_i,y_i) 同时交换成 (yi,xi)(y_i,x_i)，仍然满足 xiyi∣aix_i y_i\mid a_i，并且会把

∏yi<∏xi\prod y_i < \prod x_i

的方案一一对应到

∏yi>∏xi\prod y_i > \prod x_i

的方案。

设：

  • SS 表示只要求 xiyi∣aix_i y_i\mid a_i 的总方案数；
  • EE 表示额外满足 ∏xi=∏yi\prod x_i=\prod y_i 的方案数。

那么答案就是

S+E2.\frac{S+E}{2}.

在模 998244353998244353 意义下，除以 22 等价于乘以 499122177499122177。

计算总方案数 SS

对每个 aia_i 独立计算。

若某个质数 pp 在 aia_i 中的指数为 cc，设 pp 在 xix_i 中的指数为 α\alpha，在 yiy_i 中的指数为 β\beta。条件 xiyi∣aix_i y_i\mid a_i 等价于

α+β≤c.\alpha+\beta\le c.

满足这个条件的非负整数对 (α,β)(\alpha,\beta) 有

∑α=0c(c−α+1)=(c+1)(c+2)2\sum_{\alpha=0}^{c}(c-\alpha+1)=\frac{(c+1)(c+2)}{2}

种。

不同质因子互相独立，不同的 ii 也互相独立，所以把所有这些值相乘即可得到 SS。

计算取等方案数 EE

取等条件

∏xi=∏yi\prod x_i=\prod y_i

等价于对每个质数 pp，pp 在两边的总指数相等。也就是说，如果 pp 在 xix_i 中的指数是 αi\alpha_i，在 yiy_i 中的指数是 βi\beta_i，那么需要满足

∑i=1n(αi−βi)=0.\sum_{i=1}^{n}(\alpha_i-\beta_i)=0.

不同质数之间仍然独立，因此可以对每个质数 pp 分别做一次 DP，最后把结果相乘。

对于固定的质数 pp，设 cic_i 是 pp 在 aia_i 中的指数。我们要统计有多少种选择满足：

αi≥0,βi≥0,αi+βi≤ci,\alpha_i\ge 0,\quad \beta_i\ge 0,\quad \alpha_i+\beta_i\le c_i,

并且

∑(αi−βi)=0.\sum(\alpha_i-\beta_i)=0.

设 C=∑ciC=\sum c_i，所有可能的指数差只会落在 [−C,C][-C,C] 中。

用一维背包：

dp[s]=当前指数差为 s 的方案数.\text{dp}[s]=\text{当前指数差为 }s\text{ 的方案数}.

处理一个指数 cic_i 时，枚举所有满足 α+β≤ci\alpha+\beta\le c_i 的二元组，令贡献为

Δ=α−β.\Delta=\alpha-\beta.

然后做转移

ndp[s+Δ]+=dp[s].\text{ndp}[s+\Delta]\mathrel{+}= \text{dp}[s].

实现时可以先把同一个 cic_i 下每种 Δ\Delta 的出现次数预处理出来，这样一次转移只需要枚举 O(ci)O(c_i) 个不同的 Δ\Delta，不用枚举全部二元组。

对于这个质数，最终的 dp[0]\text{dp}[0] 就是它对 EE 的贡献。

复杂度

质因数分解直接试除即可。因为 ai≤109a_i\le 10^9，每个数最多试到 ai\sqrt{a_i}。

对于每个质数 pp，记 CpC_p 为它在所有 aia_i 中的总指数。DP 的状态数是 O(Cp)O(C_p)，每次转移枚举的指数差数量也是 O(ci)O(c_i)，总复杂度可以看作

O(∑pCp2),O\left(\sum_p C_p^2\right),

在本题范围内可以轻松通过。