Submission #1078828

---

Source Code Expand

// #includes {{{
#include <bits/stdc++.h>
using namespace std;
// }}}
// pre-written code {{{
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define RREP(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();++i)
#define LET(x,a) __typeof(a) x(a)
//#define IFOR(i,it,c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();++it,++i)
#define ALL(c) (c).begin(), (c).end()
#define MP make_pair

#define EXIST(e,s) ((s).find(e)!=(s).end())

#define RESET(a) memset((a),0,sizeof(a))
#define SET(a) memset((a),-1,sizeof(a))
#define PB push_back
#define DEC(it,command) __typeof(command) it=command

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define debug2(x) cerr << #x << " = [";REP(__ind,(x).size()){cerr << (x)[__ind] << ", ";}cerr << "] (L" << __LINE__ << ")" << endl;

const int INF=0x3f3f3f3f;

typedef long long Int;
typedef unsigned long long uInt;
typedef long double rn;

typedef pair<int,int> pii;

/*
#ifdef MYDEBUG
#include"debug.h"
#include"print.h"
#endif
*/
// }}}

const int mod = 1000000007;

//{{{ modular algebra
struct Num{
	int v;
	Num(int n):v(n){}
	Num(){}
	operator int() const {return v;}
	operator long long() const {return v;}
	void operator =(int n){v=n;}

	template<class T>
		inline void operator *=(const T &a) {
			v = (v*(long long)a)%mod;
		}
	template<class T>
		inline Num operator *(const T &a) {
			Num n(*this);n*=a;
			return n;
		}
	template<class T>
		inline void operator+=(const T &a){
			v+=(int)a;
			if(v>=mod)v-=mod;
			//	assert(0<=v and v<mod);
		}
	template<class T>
		inline Num operator+(const T &a){
			Num n(*this);n+=a;
			return n;
		}
	inline Num operator -(){
		if(v==0)return v;
		else return Num(mod-v);
	}
	template<class T>
		inline void operator -=(const T &a){
			v-=(int)a;
			if(v<0)v+=mod;
		}
	template<class T>
		inline Num operator -(const T &a){
			Num n(*this);n-=a;
			return n;
		}
#ifdef __GCD_H
	inline Num inv(){
		return invMod(this->v,mod);
	}
	template<class T>
		inline void operator /=(const T &a){
			(*this)*=invMod((int)a,mod);
		}
	template<class T>
		inline Num operator /(const T &a){
			Num n(*this);n/=a;
			return n;
		}
#endif
};

ostream& operator <<(ostream &os,const Num &n){
	os<<(int)n.v;
	return os;
}

istream& operator >>(istream &is, const Num &n){
	is>>(int)n.v;
	return is;
}
//}}}

Num dp[4040][4040], dp0[4040][4040];
Num sum[4040];

int N,M,K;

/*
Num calc(int i,int j){
//	assert((i+j+1)%(K-1)==0);
	int &ret = dp[i][j];
	if(ret>=0)return ret;
	if(i==0 and j==0)return ret = 1;
	Num ans(0);
	for(int s=0;s<=K-1;s++){
		int t = K-1-s;
		if(0<=t and s<=i and t<=j){
			ans+=calc(i-s,j-t);
		}
	}
//	cout<<i<<" "<<j<<" "<<ans<<endl;
	return ret = ans;
}

Num calc0(int i,int j){
	int &ret = dp0[i][j];
	if(dp0[i][j]>=0)return ret;
	if(i==0 or j==0)return ret = 1;
	Num ans(0);
	if(i>=K)ans += calc0(i-K+1,j);
	if(j>=K)ans += calc0(i,j-K+1);
	if(i>=K and j>=K) ans -= calc0(i-K+1,j-K+1);
//	int s = min(i,K-1), t = K-min(j,K-1);
//	if(s<t)ret+=(t-s)*calc();
	for(int s=1;s<=K-1;s++){
		int t = K-s;
		if(1<=t and s<=i and t<=j)ans+=calc(i-s,j-t);
	}
//	cout<<i<<" "<<j<<" "<<ans<<endl;
	return ret = ans;
}
*/

int main(){
	cin>>N>>M>>K;
	for(int s=1;s<=N+M;s+=K-1){
		if(s==1){
			dp[s][0] = 1;
		}else{
			sum[0] = 0;
			//sum defined: 0<=i<=s-2
			for(int i=0;i<=s-K;i++)sum[i+1] = sum[i] + dp[s-(K-1)][i];
			sum[s-K+2] = sum[s-K+1];
			for(int i=0;i<=s-1;i++){
				int l = max(0,i-(K-1)), r = min(s-K,i);
				if(l<=r)dp[s][i] = sum[r+1]-sum[l];
			}
		}
	}
	for(int s=1;s<=N+M;s+=K-1){
		if(s==1){
			dp0[s][0] = (Num)1;
			dp0[s][1] = (Num)1;
		}else{
			int prev_s = s-(K-1);
			sum[0] = 0;
			for(int i=0;i<prev_s;i++){
				sum[i+1] = sum[i] + dp[prev_s][i];
			}
			sum[prev_s+1] = sum[prev_s];
			for(int i=0;i<=s;i++){
				Num ans = 0;
				if(i>=K)ans+=dp0[prev_s][i-(K-1)];
				if(s-i>=K)ans+=dp0[prev_s][i];
				if(i>=K and s-i>=K)ans-=dp0[s-(K-1)*2][i-(K-1)];
				int l = max(0,i-K+1), r = min(i-1,s-(K-1));
				if(l<=r)ans+=sum[r+1] - sum[l];
//				assert(r+1<=prev_s+1);
				dp0[s][i] = ans;
			}
		}
	}
	cout<<dp0[N+M][N]<<endl;
	return 0;
}

Submission Info

Judge Result