P10154 (Official) - 洛谷保存站

**Update：优化了 std，将运行时间控制在 $1$ 秒以内。**

# Part 0

由 $h_i=i \times s_i$，可以发现 $W=h_1\times h_2\times \ldots\times h_n=1 \times s_1 \times 2 \times s_2 \times \ldots \times n \times s_n=(1 \times 2 \times \ldots \times n) \times (s_1\times s_2\times \ldots\times s_n)=n! \times (s_1\times s_2\times \ldots\times s_n)$。

由于 $n \le 10^7$，阶乘部分可以预处理。下面只讨论如何求 $s_1\times s_2\times \ldots\times s_n$。
# Part 1

先来模拟一下样例第 $4$ 组数据：

| $\color{blue}i$ | $\color{blue}1$ | $\color{blue}2$ | $\color{blue}3$ | $\color{blue}4$ | $\color{blue}5$ | $\color{blue}6$ | $\color{blue}7$ | $\color{blue}8$ | $\color{blue}9$ | $\color{blue}10$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $s_i$ | $6$ | $3$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ | $\color{red}2$ |
| $h_i$ | $6$ | $6$ | $6$ | $8$ | $10$ | $12$ | $14$ | $16$ | $18$ | $20$ |

再来模拟一下样例第 $5$ 组数据：

| $\color{blue}i$ | $\color{blue}1$ | $\color{blue}2$ | $\color{blue}3$ | $\color{blue}4$ | $\color{blue}5$ | $\color{blue}6$ | $\color{blue}7$ | $\color{blue}8$ | $\color{blue}9$ | $\color{blue}10$ | $\color{blue}11$ | $\color{blue}12$ | $\color{blue}13$ | $\color{blue}14$ | $\color{blue}15$ | $\color{blue}16$ | $\color{blue}17$ | $\color{blue}18$ | $\color{blue}19$ | $\color{blue}20$ | $\color{blue}21$ | $\color{blue}22$ | $\color{blue}23$ |
| :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: |
| $s_i$ | $44$ | $22$ | $15$ | $12$ | $10$ | $9$ | $8$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ | $\color{red}7$ |
| $h_i$ | $44$ | $44$ | $45$ | $48$ | $50$ | $54$ | $56$ | $56$ | $63$ | $70$ | $77$ | $84$ | $91$ | $98$ | $105$ | $112$ | $119$ | $126$ | $133$ | $140$ | $147$ | $154$ | $161$ |

# Part 2

不难发现，当 $s_i \le i$ 时，$s_i$ 便不再变化了。

**证明：**

若 $s_i \le i$，则：

$$h_i=i \times s_i$$

$$\dfrac{h_{i}}{i+1}=\dfrac{i \times s_i}{i+1}$$

------------

$$s_i \le i$$

$$s_i-i-1 \le -1$$

$$s_i-i-1<0$$

------------

$$s_i = \dfrac{i \times s_i + s_i}{i+1} > \dfrac{i \times s_i}{i+1}>\dfrac{i \times s_i+s_i-i-1}{i+1}=s_i-1$$

$$s_i>\dfrac{i \times s_i}{i+1}>s_i-1$$

$$s_i>\dfrac{h_{i}}{i+1}>s_i-1$$

$$\lceil \dfrac{h_{i}}{i+1} \rceil=s_i$$

$$s_{i+1}=s_i$$

故 $s_i$ 不再变化。

# Part 3

此外，当这个时刻到来时，$i \le \sqrt{2a}$。

**证明：**

$s_i \le i$ 等价于 $h_i \le i^2$。设 $f(i)=h_i$，$g(i)=i^2$，$d(i)=f(i)-g(i)$，则 $f(1)=a$，$g(1)=1$，$d(1)=a-1$，$s_i \le i$ 等价于 $d(i)\le0$；

当 $i$ 增加 $1$（即设 $j=i+1$）时，$g(j)-g(i)=2j-1$；

显然：

$$\lceil \dfrac{h_{i}}{j} \rceil-\dfrac{h_{i}}{j}<1$$

$$\lceil \dfrac{h_{j-1}}{j} \rceil \times j-\dfrac{h_{i}}{j} \times j<j$$

$$h_j-h_i<j$$

$$f(j)-f(i)<j$$

$$f(j)-f(i)\le j-1$$

故 $d(j)-d(i)=[f(j)-g(j)]-[f(i)-g(i)]=[f(j)-f(i)]-[g(j)-g(i)]\le (j-1)-(2j-1)=-j$，即 $d(j)-d(i)\le-j$。

也就是说，当 $i$ 增加到 $j=i+1$ 时，$d$ 函数的值至少减小 $j$；

当 $i=\sqrt{2a}$ 时，$d(i)=a-1-2-3-\ldots-\sqrt{2a}=a-\dfrac{(1+\sqrt{2a})\times \sqrt{2a}}{2}=-\sqrt{\dfrac{a}{2}}<0$，显然这个时刻已经到来。

# Part 4

于是，我们暴力计算 $s_1 \sim s_{\sqrt{2a}}$，剩下的上快速幂就行了。

最终的时间复杂度为 $O(n+T\sqrt{a})$，空间复杂度为 $O(n)$。

提示：代码中 $\lfloor\dfrac{(a+1)\times (i-1)}{i}\rfloor=\lfloor\dfrac{a\times (i-1)+(i-1)}{i}\rfloor=\lceil\dfrac{a\times (i-1)}{i}\rceil$。

# Part 5

std：

```cpp
#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7, N = 1e7 + 12, Real_N = 1e7;
int power(int a, int b, int p)
{
    if (b == 1) return a;
    int x = power(a, b >> 1, p);
    x = 1ll * x * x % p;
    if (b & 1) x = 1ll * x * a % p;
    return x;
}
int fc[N];
void preset()
{
    fc[0] = 1;
    for (int i = 1; i <= Real_N; i++)
        fc[i] = 1ll * fc[i - 1] * i % P;
}
int main()
{
    preset();
	int T;
    cin >> T;
    while (T--)
    {
        int n, a, i;
        cin >> n >> a;
        long long W = a;
	    for (i = 2; i <= n; i++)
	    {
		    a = (a + 1) * (i - 1) / i;
		    W *= a, W %= P;
		    if (a <= i) break;
	    }
	    if (i < n) W *= power(a, n - i, P), W %= P;
	    cout << W * fc[n] % P << endl;
    }
	return 0;
}
```

正在渲染内容...