【题解】整数划分 [51nod1201] 整数划分 V2 [51nod1259]
传送门：整数划分 ([51nod1201]) 整数划分 (V2) ([51nod1259])**
【题目描述】
(【T1】)
将整数 (N) 划分为若干个不同整数的和，有多少种不同的划分方式，答案对 (10^9 + 7) 取模。
例：(n=6)，(n) 可划分为 ({6} {1,5} {2,4} {1,2,3}) 共 (4) 种。
【样例】
样例输入：
6
样例输出：
4
【数据范围】
(100\%) (1 leqslant N leqslant 50000)
(【T2】)
将 (N) 划分为若干个整数的和，有多少种不同的划分方式，答案对 (10^9 + 7) 取模。
例：(n=4)，(n) 可划分为 ({4} {1,3} {2,2} {1,1,2} {1,1,1,1}) 共 (5) 种。
【样例】
样例输入：
4
样例输出：
5
【数据范围】
(100\%) (1 leqslant N leqslant 50000)
【分析】
【球盒问题】
这两道题实际上是一种球盒问题的变型。
球盒问题见隔壁 【学习笔记】薛定谔的喵咪 (Cat) (—) 球盒问题（全详解）。
先来看 (T2)，想象一下，有 (n) 个 (1) 整整齐齐地站成一排，你可以将其划分为 (m) 个区间，其中 (m in [1,n])。实际上就是要把 (n) 个相同的球放进 (m) 个相同的盒子，盒子不可为空。
可以发现，如果随意放的话，会有大量的重复情况。而每一种分配方式都可以将盒子按照球的数量从大到小排序，排出来一个非严格降序（或升序）的序列。所以，每次为新的盒子分配时，只要分配的球数小于等于上一次的分配球数，就可以保证不重不漏。
设 (dp[i][j]) 表示将 (j) 个球放入 (i) 个盒子的方案数。
(dp) 方程为： (dp[i][j]=dp[i−1][j−1]+dp[i][j−i]) 。
用简单一些的方式来理解（我也不知道是否严谨，数学证明见隔壁）：
(dp[i-1][j-1]) 指的是新的盒子 (i) 里面只放了一个球。
(dp[i][j-i]) 指的是在所有已经分好的 (i) 个盒子里面都多放一个球。
那么 (T1) 呢？由于同一整数只能用一次，即任意两个盒子里面不能放入相同数量的球，那么降序排列后就应该是严格单调下降的，新盒子所分配的球数需要小于上一次的分配球数。
多了一些限制，还是一样的状态表示，(dp[i][j-i]) 方程中的仍可保留。
而 (dp[i-1][j-1]) 出现了一个问题：每次都在新盒子中放 (1) 会触犯到限制。但如果先把前面 (i-1) 个盒子都加 (1)，新盒子就可以放 (1) 了，所以改为 (dp[i-1][j-(i-1)-1]) 。
(dp) 方程为：(dp[i][j]=dp[i−1][j−i]+dp[i][j−i]) 。
【背包问题】
用背包也可以做做。
将 (1,2,3,4...n) 使作 (n) 个不同的物品，其编号就是体积。
用 (dp[j]) 表示选了总体积为 (V) 的物品的方案数，正序枚举 (i) 的同时保证了物品的选择保持单调不下降态，至于后面的 (j)，两道题用不同的做法。
(T1) 倒序枚举，即 (01) 背包。(T2) 正序枚举，即完全背包。
(dp) 方程均为：(dp[j]+=dp[j-i]) 。
但以上两种做法时间复杂度均为是 (O(n^2))，需要想办法优化。
【优化加速】
【T1】
考虑【球盒问题】的优化。
如果尽量让每个盒子中的球数最小，那么选出来的盒子那么选出来的升序序列就是这样子的：(1,2,3...n)，而使用的盒子数量最大值就是此时的 (m)。
序列之和 (frac {m(m+1)}{2}=n)，(m) 算出来大概是 (sqrt{2n}+1)，所以枚举盒子数时只需要枚举 (1) 到 (m) 就可以了。
时间复杂度为 (O(nsqrt{2n}))
【T2】
由于可以重复分配某一数量的球，盒子数最大可以达到 (n) （全部都只放一个），(T1) 的优化不再适用。
考虑分成 ([1,m-1],[m,n]) 两块计算。
即分别算出只使用某块以内的数来组成 (n) 的方案数，然后乘法原理再求和即可。
前面部分就用【完全背包】，不多废话。
后面部分用【球盒问题】解决。
由于可以选的数大于等于 (m)，所用盒子数量必定小于等于 (lceil frac{n}{m}
ceil)，因此盒子数量只需要枚举 ([1,lceil frac{n}{m}
ceil])。
只是这次可选的最小数变成了 (m) 而不是 (1)，所以将 (dp[i-1][j-1]) 改成 (dp[i-1][j-m])，即在新的盒子 (i) 里面放 (m) 个球。
(dp) 方程为：(dp[i][j]=dp[i−1][j−m]+dp[i][j−i]) 。
总时间复杂度为 (O(n(m+frac{n}{m})))。
由均值不等式可知：(m+frac{n}{m} geqslant 2sqrt{m*frac{n}{m}} = 2sqrt{n})，当且仅当 (m=frac{n}{m}) 时等号成立，所以 (m) 取 (sqrt{n}+1) 即可（老师说每次使用 (sqrt) 时都要注意精度误差，在后面加个 (1) 比较保险）。
【Code】
【T1】
#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
const int N=5e4+3,P=1e9+7;
int n,m,ans,dp[320][N];
int main(){
scanf("%d",&n);m=sqrt(2*n)+1;
dp[0][0]=1;
for(Re i=1;i<=m;++i)
for(Re j=i;j<=n;++j)
(dp[i][j]=(dp[i-1][j-i]+dp[i][j-i])%P)%=P;
for(Re i=1;i<=m;++i)(ans+=dp[i][n])%=P;
printf("%d",ans);
}
【T2】
#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
const int N=5e4+3,P=1e9+7;
int n,m,ans,f2[250][N],ans1[N],ans2[N];
int main(){
scanf("%d",&n);m=sqrt(n)+1;
ans1[0]=1;
for(Re i=1;i<m;++i)
for(Re j=i;j<=n;++j)
(ans1[j]+=ans1[j-i])%=P;
f2[0][0]=ans2[0]=1;
for(Re i=1;i<=m;++i)
for(Re j=m;j<=n;++j){//j>=i&&j>=m，又因为i<=m所以j从m开始枚举
(f2[i][j]+=(f2[i-1][j-m]+f2[i][j-i])%P)%=P;
(ans2[j]+=f2[i][j])%=P;
}
for(Re i=0;i<=n;++i)(ans+=(long long)ans1[i]*ans2[n-i]%P)%=P;
printf("%d",ans);
}