..

· · 个人记录

How LHF’s mind works?

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

Part1

考虑 b_i\leq n 怎么做.

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

Part2

分块，设 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})).