memset0's Notebook

有没有可爱的小哥哥来我的博客玩玩呀~

题解 P6189 【[NOI Online 入门组]跑步(民间数据)】

这题相当于我们求任意模数的拆分数,可以使用五边形数定理。

五边形数定理用来描述欧拉函数展开式的特性:

$$\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

代码

#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);
}

2020-03-07 23:54:54 in 题解