P6189 [NOI Online #1 入门组] 跑步（分拆数）
简要题意
给你一个整数 \(n\)，你需要求 \(\sum_{i=1}^n x_i=n\) 且 \(x_i\le x_{i+1}\) 的非负整数解数量对给定模数 \(p\) 取模后的结果。
\(n\le 10^5\)
分析
考虑一个显然的 DP：设 \(f_{i,j}\) 表示考虑 \(1\sim i\) 这些数，总和为 \(j\) 的方案数。转移是完全背包型转移：\(f_{i,j}=f_{i-1,j}+f_{i,j-i}\)。时间复杂度 \(O(n^2)\)，飞了。
考虑优化。
注意到当取的数较大的时候，取的数不会太多。
考虑根号分治，设阈值 \(B=\sqrt n\)，那么 \(>B\) 的数选的数的个数 \(\le B\)。设 \(g_{i,j}\) 表示选了 \(i\) 个数，选的数的和是 \(j\) 的方案数。我们在选数的时候，先固定选了 \(i\) 个 \(B\)，然后每次考虑若要选更大的数，我们就给当前的数全局加 \(1\)。那么写成转移方程就是 \(g_{i,j}=g_{i-1,j-B}+g_{i,j-i}\)。结合暴力 DP 时间复杂度 \(O(n\sqrt n)\)。
int n,mod;
int f[maxm][maxn],g[maxm][maxn];
int F[maxn],G[maxn];
void add(int &x,int y){x+=y,x=x>=mod?x-mod:x;}
void solve_the_problem(){
rd(n),rd(mod);
f[0][0]=1;
rep(i,1,B-1)rep(j,0,n){
add(f[i][j],f[i-1][j]);
if(j>=i)add(f[i][j],f[i][j-i]);
}
rep(i,0,n)F[i]=f[B-1][i];
g[0][0]=G[0]=1;
rep(i,1,B)rep(j,0,n){
if(j>=B)add(g[i][j],g[i-1][j-B]);
if(j>=i)add(g[i][j],g[i][j-i]);
add(G[j],g[i][j]);
}
int ans=0;
rep(i,0,n)ans=(ans+1ll*F[i]*G[n-i]%mod)%mod;
write(ans);
}