这真是一道红题

· · 题解

### 直接推公式 1. 对于 $i$ 由于 $n$ 是给定得所以 $i$ 只能从 $1$ 取到 $n$。 2. 对于 $j$ 由于 $i$ 在变所以 $j$ 得上线也在变，但是 $j$ 得范围为 $1$ 到 $i$ 这个不会变所以我们就可以很轻松讨论出 $j$ 的取值 $\\ 1 \\ 1,2 \\ 1,2,3 \\ 1,2,3,4 \\1,2,3,4,5 \\ \dots \\1,2,3,\dots,n$。如果我们竖着看就可以得知 $j = a$ 时有 $n - a + 1$ 个 $j$。当然这种证明并不是特别严谨，所以我们需要其他的证明：由于 $i$ 在变所以 $j$ 得上线也在变所以当 $j = a$ 时，只有 $n - a + 1$ 个 $i \geq a$，所以有 $n - a + 1$ 个 $j = a$。 3. 对于 $k$ 的取值讨论方法跟 $j$ 一模一样，所以我们直接说结论当 $k = a$ 是只有 $1 + 2 + 3 + 4 + \dots + (n -(a - 1)) = \frac{(n - a + 2) \times (n - a + 1)}{2}$ 个 $j \geq a$。 最后求出 $\prod \limits_{k=1}^{n} k^{\frac{(n - k + 2) \times (n - k + 1) \times k}{2}}$ 求出这个东西我们只需要用快速幂加 for 循环即可，所以时间复杂度为 $\Omicron(n \log n)$。 ### 考虑前缀和模拟 我们可以用前缀和进行模拟。 定义以下数组： - $sumk_{num}$ 表示的值为 $\prod \limits_{k=1}^{num} k^k$。 - $sumj_{num}$ 表示的值为 $\prod \limits_{j=1}^{num} \prod \limits_{k=1}^j k^k$。 - $sumi_{num}$ 表示的值为 $\prod \limits_{i=1}^{num} \prod \limits_{j=1}^i \prod\limits_{k=1}^j k^k$。 那么不难推出： $sumk_{i} = sumk_{i - 1} \times i^i \\ sumj_{i} = sumj_{i - 1} \times sumk_{i} \\ sumi_{i} = sumi_{i - 1} \times sumj_{i}$。 所以我们跑一遍 $\Omicron(n)$ 的循环就行了，答案就是 $sumi_{n}$。由于计算 $k ^ k$ 需要快速幂，所以总时间复杂度 $\Omicron({n \log n})$。 ### 提醒一下 赛时有许多人代码 TLE 原因是因为对于 $mod$ 的定义不能直接用 `longlong` 需要定义成 `const long long`。