<span>题解「Luogu6189 [NOI Online #1 入门组]跑步」</span>
整数拆分问题。
首先有一个dp的方法：
设 \(f_{i,j}\) 表示用小于等于 \(i\) 的正整数组合成 \(j\) 的方案数，则有转移：
\[f_{i,j}=f_{i-1,j}+f_{i,j-i} \]
前一项相当于不用 \(i\) 组成 \(j\) ，后一项表示使用了 \(i\) 。
用这个卡一卡能得到 \(70\) 分，再滚动一下就有 \(80\) 分。
当 \(n\) 达到 \(10^5\) 时，只用上面的做法就不行了。
再考虑一种dp：
设 \(g_{i,j}\) 表示将 \(i\) 拆分成 \(j\) 个正整数的方案数，则有转移：
\[g_{i,j}=g_{i-1,j-1}+g_{i-j,j} \]
前一项表示新拆出一个 \(1\) ，后一项表示 \(j\) 个数全部加 \(1\) 。
考虑根号分治：用第一种dp求出只用小于等于 \(\sqrt{n}\) 的正整数的方案数，将第二种dp魔改一下，求出将 \(i\) 拆分成 \(j\) 个大于等于 \(\sqrt{n}\) 的正整数的方案数。
魔改后 \(g_{i,j}\) 有转移：
\[g_{i,j}=g_{i-\sqrt{n},j-1}+g_{i-j,j} \]
前一项表示新拆出一个 \(\sqrt{n}\) ，后一项同上。
考虑如何合并答案：
枚举一个数 \(i\) ，将 \(n\) 分成两部分： \(i\) 和 \(n-i\) 。将 \(i\) 拆分成小于 \(\sqrt{n}\) 的数，将 \(n-i\) 拆分成大于等于 \(\sqrt{n}\) 的数，则总方案数：
\[\text{Ans}=\sum_{i=1}^n(f_{i,\sqrt{n}-1}\times \sum_{j=0}^{\sqrt{n}}g_{n-i,j}) \]
采用根号分治的做法，计算 \(f\) 需要 \(O(n\sqrt{n})\) ，因为大于 \(\sqrt{n}\) 的数最多只会用 \(\sqrt{n}\) 个，所以计算 \(g\) 也只需要 \(O(n\sqrt{n})\) ，统计答案需要 \(O(n\sqrt{n})\) ，总时间复杂度 \(O(n\sqrt{n})\) 。
\(\text{Code}:\)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define maxn 100005
#define BN 400
#define Rint register int
#define INF 0x3f3f3f3f
using namespace std;
typedef long long lxl;
template <typename T>
inline void read(T &x)
{
x=0;T f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
x*=f;
}
int n;
int p,g[maxn][BN+5],f[maxn];
int main()
{
// freopen("P6189.in","r",stdin);
read(n),read(p);
int S=n/BN+1;
f[0]=1;
for(int i=1;i<BN;++i)
for(int j=i;j<=n;++j)
(f[j]+=f[j-i])%=p;
g[0][0]=1;
for(int i=0;i<=n;++i)
for(int j=1;j<=S&&j<=i;++j)
{
if(i>=BN) (g[i][j]+=g[i-BN][j-1])%=p;
if(i>=j) (g[i][j]+=g[i-j][j])%=p;
}
lxl ans=0;
for(int i=0;i<=n;++i)
{
int res=0;
for(int j=0;j<=S;++j)
(res+=g[n-i][j])%=p;
(ans+=1ll*f[i]*res%p)%=p;
}
printf("%lld\n",ans);
return 0;
}
