题目描述
小 $H$ 是一个热爱运动的孩子，某天他想给自己制定一个跑步计划。
小 $H$ 计划跑 $n$ 米，其中第 $i(i≥1)$ 分钟要跑 $x_i$ 米（$x_i$ 是正整数），但没有确定好总时长。
由于随着跑步时间增加，小 $H$ 会越来越累，所以小 $H$ 的计划必须满足对于任意 $i(i>1)$ 有 $x_i≤x_{i−1}$。
现在小 $H$ 想知道一共有多少个不同的满足条件的计划，请你帮助他。
两个计划不同当且仅当跑步的总时长不同，或者存在一个 $i$，使得两个计划中 $x_i$ 不相同。
由于最后的答案可能很大，你只需要求出答案对 $p$ 取模的结果。
输入格式
仅一行两个整数 $n,p$ 表示跑步距离与模数。
输出格式
仅一行一个整数，表示答案模 $p$ 的值。
输入样例$1$
4 44
输出样例$1$
5
样例$1$解释
五个不同的计划分别是：$\{1,1,1,1\}$，$\{2,1,1\}$，$\{3,1\}$，$\{2,2\}$，$\{4\}$。
输入样例$2$
66 666666
输出样例$2$
323522
输入样例$3$
66666 66666666
输出样例$3$
45183149
算法$1$
暴力递归
思路：
将 $M$ 米分配在在 $N$ 分钟里，求方案数。
边界条件：跑完了或者只有一分钟时，方案数为 $1$。
若 $n > m$，那就算每分钟一米最多也只能占有 $m$ 分钟。即$f(m, n) = f(m, m)$
对其余情况 $f(m, n)$，分为占满n分钟和未占满两种情况。
-
若占满，则可以将每分钟去掉一米，方案数不变。即 $f_1(m, n) = f(m-n, n)$
-
若未占满，则可以去掉一分钟。即 $f_2(m, n) = f(m, n-1)$
所以 $f(m, n) = f_1(m, n) + f_2(m, n) = f(m-n, n)+f(m, n-1)$
大概能过 $30\%$ 数据
时间复杂度： 玄学 不知道
$(2^n?)$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
int a,MOD;
int f(int m,int n) //返回把m米分配在n分钟的情况总数
{
if(n>m)n=m; //如果n>m则f(m,n)=f(m,m)
if(m<=1||n==1) //边界条件：跑完了或者只有一分钟时，方案数为1
return 1;
return (f(m-n,n)%MOD+f(m,n-1)%MOD)%MOD;
//递归f(m,n)=f(m-n,n)+f(m,n-1)
}
int main()
{
scanf("%d %d",&a,&MOD);
printf("%d",f(a,a)%MOD);
return 0;
}
算法$2$
二维递推
$($就把上面那个反过来操作$)$
时间复杂度： $O(n^2)$
骗到了 $70$ 分
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=5010;
int f[N][N];
int main()
{
int n,MOD;
cin>>n>>MOD;
for(int i=0;i<=n;i++)
for(int j=1;j<=n;j++)
if(j==1||i==0) f[i][j]=1; //边界条件
else if(i<j) f[i][j]=f[i][i]%MOD; //如果n>m则f(m,n)=f(m,m)
else f[i][j]=(f[i-j][j]%MOD+f[i][j-1]%MOD)%MOD;
printf("%d",f[n][n]%MOD);
return 0;
}
算法$3$
五边形数定理优化
假设小 $H$ 跑 $1$ ~ $n$ 米的情况数分别为 $P_0，P_1，P_1，…，P_n$
并将此序列记为 $\{P_n\}$。
那么有生成函数 $f(x) = P_0 + P_1x + P_2x^2 + … + P_nx^n$。
显然 $P_0 = 1$，那么我们可以令 $f(x) = (1 + x + x^2 + …)(1 + x^2 + x^4 +…)(1 + x^3 + x^6 +…)…$，其中 $0 \leq x \leq 1$。
则 $P_n$ 就是所有括号中乘积组合出的 $x^n$ 的系数。
问题转化为求生成函数所有括号乘积组合出的 $x^n$ 的情况数。
是不是好抽象？
举个栗子：
比如我们要求 $P_3$，那么我们可以数一下从 $f(x)$ 中组合出 $x^3$ 的数量：
- 第一个括号里的 $1$，乘第三个括号里的 $x^3$，乘后面无穷个括号里的 $1$
- 第一个括号里的 $x$，乘第二个括号里的 $x^2$，乘后面无穷个括号里的 $1$
- 第一个括号里的 $x^3$，乘后面无穷个括号里的 $1$
一共 $3$ 种情况，所以 $P_3 = 3$
还没懂？那再举个栗子
要求 $P_4$，则可以数一下从 $f(x)$ 中组合出 $x^4$ 的数量：
（脑补一下每句话后面的乘后面无穷个括号里的 1，没错我懒癌又犯了）
- 第一个括号里的 $1$，乘第二个括号里的 $x^4$。
- 第一个括号里的 $1$，乘第四个括号里的 $x^4$。
- 第一个括号里的 $x$，乘第三个括号里的 $x^3$。
- 第一个括号里的 $x^2$，乘第二个括号里的 $x^2$。
- 第一个括号里的 $x^4$。
一共 $5$ 种情况，所以 $P_4 = 5$
继续，我们对第二个式子进行化简。（数学大佬跳过）
先看第一个括号：
令 $A = 1 + x + x^2 + x^3 + x^4 +…$
则 $A x = x + x^2 + x^3 + x^4 + x^5…$
由下式减上式可得 $ A (x - 1)= x^\infty - 1$
因为 $0 \leq x \leq 1$，所以 $x^\infty = 0($感性理解一下，我就不严谨证明了$)$
所以 $ A (x - 1)= -1 \Rightarrow A = \frac{1}{1-x}$
同理可得第二个括号中 $1 + x^2 + x^4 + x^6 + x^8 +… = \frac{1}{1-x^2}$
第三个括号中 $1 + x^3 + x^6 + x^9 +… = \frac{1}{1-x^3}$
…
以此类推
那么 $f(x) = \frac{1}{1-x} \times \frac{1}{1-x^2} \times \frac{1}{1-x^3}…$
$=\frac{1}{(1-x)(1-x^2)(1-x^3)(1-x^4)…}$
由五边形数定理可得
$f(x) = \frac{1}{1-x-x^2+x^5+x^7-x^{12}-x^{15}+…}$
两边同乘 $1-x-x^2+x^5+…$ 可得
$f(x)(1-x-x^2+x^5+x^7-x^{12}-x^{15}+…) = 1$
即 $(P_0 + P_1x + P_2x^2 + … + P_nx^n)(1-x-x^2+x^5+x^7-x^{12}-x^{15}+…) = 1$
亦即 $(\sum^n_{k=0}{P_kx^k})(\sum^{\infty}_{k=0}{(-1)^kx^{\frac{k(3k \pm 1)}{2}}})=1$
得 $P_n-P_{n-1}-P_{n-2}+P_{n-5}+P_{n-7}…=0$
则 $P_n = P_{n-1}+P_{n-2}-P_{n-5}-P_{n-7}…$
这样我们就得到了我们的递推式。
由于递推右边的项数是 $\sqrt{n}$ 级别的，所以总的时间复杂度是 $O(n\sqrt{n})$
时间复杂度：$O(n\sqrt{n})$
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int N=100010;
int n,p;
int f[N],g[N];
int main()
{
cin>>n>>p;
int m=0;
for(int k=1;g[m]<=n;k++)
{
g[++m]=(3*k*k-k)/2;
g[++m]=(3*k*k+k)/2;
}
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=1,t=1;g[j]<=i;j++)
{
f[i]=(f[i]+f[i-g[j]]*t)%p;
if(j%2==0)t*=-1;
}
cout<<(f[n]+p)%p;
return 0;
}
%%% 献上膝盖
STO
Orz
Orz%%%
Orz您大佬