結果

問題 No.802 だいたい等差数列
ユーザー tempura_pptempura_pp
提出日時 2019-03-10 00:30:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,973 bytes
コンパイル時間 1,140 ms
コンパイル使用メモリ 106,776 KB
実行使用メモリ 126,592 KB
最終ジャッジ日時 2024-07-01 19:32:56
合計ジャッジ時間 14,285 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3 RE * 1
other AC * 11 RE * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;



template<typename T>
struct SegmentTree{
private:
	int n;
	T E;
	vector<T> node;
	inline void updatef(T& x,T& y){
		//x = y;
		(x += y)%=mod;
		//x = max(x,y);
		//x = min(x,y);
	}
	inline T queryf(T& x,T& y){
		//return x*y;
		return (x+y)%mod;
		//return max(x,y);
		//return min(x,y);
	}

public:
	SegmentTree(int sz,T E_=0):E(E_){
		n=1;
		while(n<sz)n<<=1;
		node.resize(2*n-1,E);
	}

	SegmentTree(vector<T>& A,T& E_):E(E_){
		int sz=A.size();
		n=1;
		while(n<sz)n<<=1;
		node.resize(2*n-1,E);
		rep(i,sz)node[i+n-1]=A[i];
		for(int i=n-2;i>=0;--i){
			node[i]=queryf(node[2*i+1], node[2*i+2]);
		}
	}
	void update(int k,T x){
		k+=n-1;
		updatef(node[k],x);
		while(k>0){
			k=(k-1)/2;
			node[k]=queryf(node[2*k+1], node[2*k+2]);
		}
	}
	   //[a,b)での和を返す
	T get(int a,int b,int k=0,int l=0,int r=-1){
		if(r<0)r=n;
		if(r<=a||b<=l)return E;
		if(a<=l&&r<=b)return node[k];
		T xl=get(a,b,2*k+1,l,(l+r)/2);
		T xr=get(a,b,2*k+2,(l+r)/2,r);
		return queryf(xl, xr);
	}
};

ll dp[3030][3030];
int main(){
	int n,m,d1,d2;
	cin>>n>>m>>d1>>d2;
	m-=(n-1)*(d1-1);
	d2-=d1-1;
	if(m<0){
		cout<<0<<endl;
		return 0;
	}
	assert(n<=3000);
	vector<SegmentTree<ll>> sg(n+2,m+5);
	sg[0].update(0,1);
	rep(i,n){
		rep(j,m){
			if(i==0){
				ll ret=sg[0].get(0,j+1);
				sg[1].update(j+1,ret);
			}
			else {
				ll ret=sg[i].get(max(0,j+1-d2),j+1);
				sg[i+1].update(j+1,ret);
			}
		}
	}
	cout<<sg[n].get(0,m+1)<<endl;
	return 0;
}
0