题目
题目链接：https://www.luogu.com.cn/problem/P6189
小 H 是一个热爱运动的孩子，某天他想给自己制定一个跑步计划。小 H 计划跑 \(n\) 米，其中第 \(i(i \geq 1)\) 分钟要跑 \(x_i\) 米（\(x_i\) 是正整数），但没有确定好总时长。
由于随着跑步时间增加，小 H 会越来越累，所以小 H 的计划必须满足对于任意 \(i(i>1)\) 都满足 \(x_i \leq x_{i-1}\)。
现在小 H 想知道一共有多少个不同的满足条件的计划，请你帮助他。两个计划不同当且仅当跑步的总时长不同，或者存在一个 \(i\)，使得两个计划中 \(x_i\) 不相同。
由于最后的答案可能很大，你只需要求出答案对 \(p\) 取模的结果。
思路
哪位神仙想出来的分块算法。。。
简化题目就是把 \(n\) 分为若干个数字之和的方案数，两种方案不同当且仅当长度不同或排序后任意位置不同。
我们设定一个分界点 \(T\)，对于一个数字 \(x\)，分为 \(x<t\) 和 \(x\geq t\) 两部分计算。
Part1
对于 \(x<T\) 的数字，设 \(f[i][j]\) 表示选取若干个数字，其中最大的不超过 \(i\)，和为 \(j\) 的方案数。
这是一个经典的背包。有
显然可以压缩到一维
时间复杂度 \(O(nT)\)
Part2
对于 \(x\geq T\) 的部分，设 \(g[i][j]\) 表示选择了 \(i\) 个不小于 \(T\) 的数字，和为 \(j\) 的方案数。
那么可以转换成两种操作：
- 向序列中增加一个数 \(T\)。
- 将序列中的所有数全部加一。
显然任意一个数字全部不小于 \(T\) 的序列有且仅有一种方法可以被上述操作得到。那么有方程
由于数字全部不小于 \(T\)，所以最多有 \(\frac{n}{T}\) 个数字，时间复杂度 \(O(\frac{n^2}{T})\)。
Part3
将这两个序列合并在一起，总方案数为
由于 \(\sum g\) 可以用前缀和维护，所以时间复杂度 \(O(n)\)。
那么三个 Part 的总时间复杂度为 \(O(nT+\frac{n^2}{T}+n)\)，显然 \(T=\sqrt{n}\) 的时候复杂度最优。此时时间复杂度为 \(O(n\sqrt{n}+n)\)。
代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100010,M=320;
int n,T,MOD,ans,f[N],g[M][N],sumg[N];
int main()
{
scanf("%d%d",&n,&MOD);
T=sqrt(n)+1;
f[0]=1;
for (int i=1;i<T;i++)
for (int j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%MOD;
g[0][0]=sumg[0]=1;
for (int i=1;i<=T;i++)
for (int j=0;j<=n;j++)
{
if (j>=T) g[i][j]=(g[i][j]+g[i-1][j-T])%MOD;
if (j>=i) g[i][j]=(g[i][j]+g[i][j-i])%MOD;
sumg[j]=(sumg[j]+g[i][j])%MOD;
}
for (int i=0;i<=n;i++)
ans=(ans+1LL*f[i]*sumg[n-i]%MOD)%MOD;
printf("%d",ans);
return 0;
}