询问满足如下条件的数列的方案数:
\(a_i\ge 0\)
\(\sum a_i=m\)
\(2a_i\le a_{i-1}+a_{i+2}\)
\(n,m\le 10^5\)
自己搞的时候连负数都不知道怎么处理……
钦定最终数列的最小值(位置为第二关键字)。设为\(i\)。
那么一个合法的数列可以如此构造:
- 整个数列加\(1\)。
- 选择\(j<i\),给\(a_{j},a_{j-1},a_{j-2},\dots,a_1\)分别加\(1,2,3,\dots\)。至少给\(i-1\)操作一次。
- 选择\(j>i\),给\(a_j,a_{j+1},a_{j+2},\dots,a_{n}\)分别加\(1,2,3,\dots\)。
无序的搞上面的若干次操作,最终要求总和为\(m\)。
不关心具体取值,于是可以看成背包。物品大小平方级增长,所以有效的物品数可视作\(\sqrt m\)。\(i\)固定时直接做是\(m\sqrt m\)的,移动\(i\)时相当于删物品和加物品。都可以\(O(m)\)做,总时间\(O(m\sqrt m)\)
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
#define ll long long
#define mo 1000000007
int n,m;
int f[N];
void insert(int f[],ll w){
for (ll i=w;i<=m;++i)
f[i]=(f[i]+f[i-w])%mo;
}
void erase(int f[],ll w){
for (ll i=m;i>=w;--i)
f[i]=(f[i]-f[i-w]+mo)%mo;
}
int query(ll x){
return x<0 || x>m?0:f[x];
}
ll val(int x){return (ll)x*(x+1)/2;}
int main(){
freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
f[0]=1;
insert(f,n);
for (int i=1;i<=n-1;++i)
insert(f,val(i));
ll ans=0;
for (int i=1;i<=n;++i){
ans+=query(m-val(i-1));
erase(f,val(n-i));
insert(f,val(i));
}
ans%=mo;
printf("%lld\n",ans);
return 0;
}