询问满足如下条件的数列的方案数:
(a_ige 0)
(sum a_i=m)
(2a_ile a_{i-1}+a_{i+2})
(n,mle 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)固定时直接做是(msqrt m)的,移动(i)时相当于删物品和加物品。都可以(O(m))做,总时间(O(msqrt 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
",ans);
return 0;
}