1
作者:
梦若浮生
,
2023-06-30 20:01:47
,
所有人可见
,
阅读 98
#include<bits/stdc++.h>
using namespace std;
const int N =2e3+10;
#define int long long
int tr[N],n,m,ans[N][N];
int Mod=1e9+7;
int lowbit(int x){
return x&-x;
}
int sum(int x){
if(x<=0) return 0;
int res=0;
for(int i=x;i;i-=lowbit(i)) res+=tr[i],res%=Mod;
return res;
}
void add(int x,int v){
for(int i=x;i<N;i+=lowbit(i)) tr[i]+=v,tr[i]%=Mod;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
if(i==1){
for(int j=1;j<=m;j++){
ans[1][j]=1;
add(j,1);
}
}
else{
for(int j=1;j<=m;j++){
int L=(i*j-m+i-2)/(i-1);
int R=(i*j-1)/(i-1);
if(L<=0) L=1;
ans[i][j]=((sum(R)-sum(L-1))%Mod+Mod)%Mod;
}
for(int j=1;j<=m;j++) add(j,-ans[i-1][j]),add(j,ans[i][j]);
}
}
cout<<sum(m);
}