SP15257
gitxiaozheng
·
·
题解
十三年老题目。
Solution
本题有直接递推的削弱版，详情见 SP15256。
那么这道题，n\le10^8，直接递推不可行，于是我们给出一个超强公式：Hardy–Ramanujan–Rademacher 公式，简称 HRR，其内容如下：
定义：
F(x) = \begin{cases}
x-\lfloor x\rfloor-\frac{1}{2} & x \notin \mathbb Z \\
0 & x \in \mathbb Z
\end{cases}
则有：
s(h,k) = \sum_{r=1}^{k-1} F(\frac{r}{k}) F(\frac{hr}{k})
A_k(n) = \sum_{\substack{0 \le h < k \\ \operatorname{gcd}(h,k)=1}} e^{\pi i s(h,k)} \, e^{\frac{-2\pi i n h }{ k}}
p(n) = \frac{1}{\pi\sqrt{2}} \sum_{k=1}^{\infty} A_k(n)\, \sqrt{k}\, \frac{d}{dx}\!\left[\frac{\sinh\!\left(\frac{\pi}{k}\sqrt{\frac{2}{3}\left(x-\frac{1}{24}\right)}\right)}{\sqrt{x-\frac{1}{24}}}\right]_{x=n}
这个公式的证明可以见 [此处](https://arxiv.org/pdf/2302.03835)。
由于这个公式收敛得太快了，想要计算 $p(n)$ 只需要计算 $O(\sqrt{n})$ 项即可得出很精确的答案，而 $\sqrt{10^8}=10^4$，可以接受。
公式是有了，但是实现的难度可想而知，常数巨大，还要想一大堆的优化方法。
然而有人说了这样一句话：
在网上一搜索，发现 python 里的 Sympy 库（这其实是一个第三方库）确实有这么一个函数是可以拿来用的：
```python
from sympy.functions.combinatorial.numbers import partition as pt
ans=pt(n) # 计算答案
```
该函数早在 2008 年的时候就已经被引入到 Sympy 0.6.0 版本了（Sympy 1.13 版本将该函数调用方式改成了现在的），主要的行为就是对于较大的 $n$ 用本文提到的公式计算 $p(n)$，对于小的 $n$ 使用普通的递推。
然后我在 vjudge 上使用 Python 3.12.3 版本，试着交了一发，结果没想到不仅能跑起来竟然还过了？？？
因此我们就~~莫名其妙地~~通过了本题。
:::success[AC code & 提交记录]
```python
import sys
from sympy.functions.combinatorial.numbers import partition as pt
sys.set_int_max_str_digits(0)
print(pt(int(input())))
```
[提交记录](https://vjudge.net/solution/74002750/Fihr8WFA996RKj0i0ICk)。
:::
总之在这里还是膜拜实现这个函数的大神，以及任何一个在不知道这个函数的情况下使用 python 甚至 C++ 通过此题的人。