题意
若非负数列 \(A\) 中任意 \(i(2 \leq i \leq N-1)\) ，都有 \(2A_i \leq A_{i-1} + A_{i+1}\)，则称 \(A\) 为凸数列。
问长为 \(N\) ，且数列中所有项的和为 \(M\) 的凸数列有多少个，答案对 \(10^9+7\) 取模。
分析
我们可以把最靠左的最小值的位置叫做数列的顶点。
为了方便，我们先讨论顶点固定在最左端的情况。
顶点在最左端
我们先假设这个数列全是 \(0\)，此时是一个凸数列，我们不断在顶点右侧(不包括顶点)的位置加值，使得这个数列更“陡”，最终和达到 \(M\)，且仍为凸数列。
可以把在右侧的加值的操作分成若干次，每一次看作对一个区间 \([i,N](i > 1)\)（注意 \(i\) 不能等于 \(1\)）做加法，其中 \(A_j(j \in [i,N])\) 加上了 \(j-i+1\)。手动模拟一下，发现这样构造的数列恰好满足凸数列的条件。
所以我们只要对所有区间做完全背包就好了，时间复杂度为 \(O(NM)\)，但我们发现只有做一次区间加值小于等于 \(M\) 的区间对我们有用，而这样的区间只有 \(O(\sqrt{M})\) 个，复杂度可以优化到 \(O(M\sqrt{M})\)。
所以这样就做完了？
其实不是，我们可以在数列的和较小时，可以把数列整体抬高使得和为 \(M\)，这些情况也要考虑，我们只要在完全背包的初始化时做一点改动就可以了。
顶点在其它位置
我们可以让顶点从最左端向右移动，在移动过程中，左边会增加 \(O(\sqrt{M})\) 个需要考虑加值的区间，右边会减少 \(O(\sqrt{M})\) 个需要考虑加值的区间，我们只要动态地加入和删除做背包的物品就行了。总复杂度仍是 \(O(M\sqrt{M})\)，注意这里 \(\sqrt{M}\) 的含义并不简单，这个复杂度需要小证一下。
设 \(f_i\) 为数列和为 \(i\) 时的方案数，答案就是顶点在所有位置时的 \(f_M\) 的和。
所以这样就做完了？
其实不是，不要忘了我们一开始对顶点的定义，顶点是最靠左的最小值的位置，所以我们要保证顶点左边的数一定都比顶点上的数大，也就是说数列最左端到顶点左侧的区间至少加值一次，因此最后的答案是所有位置的 \(f_{M-S_{i-1}}\) 的和，其中 \(S_i\) 表示区间 \([1,i]\) 加值一次会增加的总和。
两种情况合并
综上，我们就真的做完了。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=460;
const int MOD=1e9+7;
int n,m,cnt,s[M],f[N],ans;
int Add(int a,int b){
return (a+b)%MOD;
}
int Sub(int a,int b){
return (a-b)%MOD;
}
int main(){
scanf("%d%d",&n,&m);
while(s[cnt]<=m){
cnt++;
s[cnt]=s[cnt-1]+cnt;
}
cnt--;//预处理出合法的加值区间长度
for(int i=0;i<=m;i+=n){
f[i]=1;
}//初始化时考虑整体抬高
for(int i=1;i<=min(cnt,n-1);i++){
for(int j=s[i];j<=m;j++){
f[j]=Add(f[j],f[j-s[i]]);//背包
}
}
for(int i=1;i<=n;i++){
if(i-1<=cnt){
ans=Add(ans,f[m-s[i-1]]);//算答案
}
if(i<=cnt){
for(int j=s[i];j<=m;j++){
f[j]=Add(f[j],f[j-s[i]]);//加入新区间
}
}
if(n-i<=cnt){
for(int j=m;j>=s[n-i];j--){
f[j]=Sub(f[j],f[j-s[n-i]]);//去掉旧区间
}
}
}
ans=(ans+MOD)%MOD;
printf("%d",ans);
return 0;
}