Submission #1076846

---

Source Code Expand

//============================================================================
// Author       : Sun YaoFeng
//============================================================================

//#pragma 	comment(linker, "/STACK:100240000,100240000")
//#include	<cstdio>
//#include	<cstdlib>
//#include	<cstring>
//#include	<algorithm>

#include	<bits/stdc++.h>

using	namespace	std;

#define DB		double
#define	lf		else if
#define I64		long long
#define	Rd()	(rand()<<15|rand())
#define For(i,a,b)	for(int i=a,lim=b;i<=lim;i++)
#define Rep(i,a,b)	for(int i=a,lim=b;i>=lim;i--)

#define	fi	first
#define se	second
#define MK	make_pair
#define PA	pair<int, int>

//#define	min(a,b)	((a)<(b)?(a):(b))
//#define	max(a,b)	((a)<(b)?(b):(a))

#define	CH	(ch=getchar())
int		IN()	{
		int x= 0, f= 0, ch;
		for	(; CH < '0' || ch > '9';)	f= (ch == '-');
		for	(; ch >= '0' && ch <= '9'; CH)	x= x*10 + ch -'0';
		return	f? -x : x;
}

#define n	4005
#define P	1000000007

int		N, M, K, D, F[n][n];

inline	void	Plu(int&a,int b){
		a+=b;
		if  (a>=P)	a-=P;
}

int		main(int argc, char* argv[]){
		N= IN();
		M= IN();
		K= IN();
		D= (N+M) / (K-1) + 1;
		
		For(i, 1, K-1)	F[1][i]= 1;
		For(i, 2, D)	For(j, 0, K-1)	For(k, 0, N-j)	Plu(F[i][j+k], F[i-1][k]);
		
		int	Ans= 0;
		For(i, 1, D)	For(j, 0, N)	{
			int k= i*(K-1) + 1 - j;
			if	(k <= M && j % (K-1) == N % (K-1) && k % (K-1) == M % (K-1))	Plu(Ans, F[i][j]);
		}
		
		printf("%d\n", Ans);
		
		return	0;
}

Submission Info

Judge Result