Submission #1371794

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pa;
typedef unsigned int uint;
typedef unsigned long long ull;
#define w1 first
#define ls (x<<1)
#define w2 second
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) (int((x).size()))
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
#define Rep2(p,x) for(int (p)=cur[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
const int maxn=4e3+5,mod=1e9+7;
int n,m,K,ans;
int dp[2][maxn];
int add(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
int main(){
	read(n);read(m);read(K);
	dp[0][0]=1;
	rep(i,0,(n+m-1)/(K-1)){
		int nxti=i+1;
		memset(dp[nxti&1],0,sizeof dp[nxti&1]);
		rep(j,0,n)rep(k,1,K-1){
			int nxtj=j+k;
			if(nxtj>n)continue;
			dp[nxti&1][nxtj]=add(dp[nxti&1][nxtj],dp[i&1][j]);
		}
		rep(j,1,n){
			int tot=(K-1)*(i+1);
			if(!((j-n)%(K-1))&&!((m-1-(tot-j))%(K-1))&&tot-j<=m-1)ans=add(ans,dp[nxti&1][j]);
		}
		rep(j,0,n)dp[nxti&1][j]=add(dp[nxti&1][j],dp[i&1][j]);
	}
	printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result