結果

問題 No.802 だいたい等差数列
ユーザー tempura_pptempura_pp
提出日時 2019-03-10 00:30:22
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,282 ms
126,592 KB
testcase_01 AC 26 ms
5,888 KB
testcase_02 AC 1,596 ms
106,880 KB
testcase_03 AC 325 ms
28,160 KB
testcase_04 AC 1,726 ms
114,560 KB
testcase_05 AC 9 ms
5,376 KB
testcase_06 AC 1,025 ms
94,848 KB
testcase_07 AC 904 ms
102,400 KB
testcase_08 AC 276 ms
29,568 KB
testcase_09 AC 775 ms
67,712 KB
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 AC 2 ms
5,376 KB
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 2 ms
5,376 KB
testcase_33 RE -
権限があれば一括ダウンロードができます

ソースコード

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