..

How LHF’s mind works?

题意：给定 $n,a_{1\sim n},b_{1\sim n}$，求 $\prod_{i=1}^na_i^{b_i}$.

考虑 $b_i\leq n$ 怎么做.

设 $g_i=\prod_{b_j=i}a_j$，对 $g$ 做一遍后缀积，然后全乘起来就是答案.

分块，设 $b_i=c_i+Bd_i$，答案为 $(\prod_{i=1}^na_i^{c_i})(\prod_{i=1}^na_i^{d_i})^B$. 取 $B=\sqrt{mod}$. 复杂度 $O(n+\sqrt{mod})$. 可以做到 $O(k(n+mod^{\frac1k}))$.