题解 P6189 【[NOI Online 入门组]跑步（民间数据）】
memset0
2020-03-07 23:54:54
这题相当于我们求任意模数的拆分数，可以使用五边形数定理。
五边形数定理用来描述欧拉函数展开式的特性：
$$\varphi(x) = \prod_{n=1}^\infty (1 - x^n) = \sum_{k=-\infty}^{\infty} (-1)^k x^{\frac {k(3k+1)} 2} = \sum_{k=0}^{\infty} (-1)^k x^{\frac {k(3k \pm 1)} 2}$$
欧拉函数的倒数是划分数的生成函数：
$$\frac 1 {\varphi(x)} = \sum_{i=0}^\infty p(i) x^i = \prod_{i=0}^\infty \sum_{j=0}^\infty x^{ij} = \prod_{i=0}^\infty \frac 1 {1 - x^i}$$
由定义我们可以得到：
$$\varphi(x) \times \frac 1 {\varphi(x)} = 1 \Leftrightarrow \left( \sum_{k=0}^{\infty} (-1)^k x^{\frac {k(3k \pm 1)} 2} \right) \left( \sum_{i=0}^\infty p(i) x^i \right) = 1$$
通过这个我们可以得到划分数的递推式。
同时发现五边形数生成函数的项数是 $O(\sqrt n)$ 级别的，故我们可以在 $O(n \sqrt n)$ 的时间复杂度内求出划分数前 $n$ 项。
当然此题中我们只需输出第 $n$ 项即可。
感兴趣的读者也可以思考下如果此题规定 $a_i$ 小于一给定常数 $k$ 应该如何处理。[sol](https://memset0.cn/wu-bian-xing-shu-ding-li)。
代码
```cpp
#include<bits/stdc++.h>
int T,n,m,mod,f[100010],g[100010];
int main(){
f[0]=1,scanf("%d%d",&n,&mod);
for(int i=1;i*(3*i-1)/2<=n;i++)g[m++]=i*(3*i-1)/2,g[m++]=i*(3*i+1)/2;
for(int i=1;i<=n;i++)for(int j=0;j<m&&g[j]<=i;j++)f[i]=(f[i]+(((j>>1)&1)?-1ll:1ll)*f[i-g[j]])%mod;
printf("%d\n",(f[n]+mod)%mod);
}
```