Submission #1261484

---

Source Code Expand

//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
typedef long long ll;
const int Imx=2147483647;
const int mod=1000000007;
const ll Lbg=2e18;
int n,m,k;
ll dp[4011],ndp[4011];
int main()
{
	cin>>n>>m>>k;
	dp[0]=1;
	ll ans=0;
	for(int i=1;i<=(n+m-1)/(k-1);i++)
	{
		memset(ndp,0,sizeof(ndp));
		int sz=i*(k-1)+1;
		for(int j=0;j<=sz;j++)
		{
			for(int t=1;t<k&&t<=j;t++)ndp[j]+=dp[j-t];
			ndp[j]%=mod;
		}
		for(int j=1;j<=sz;j++)
		{
			if(j<=n&&sz-j<=m&&(n-j)%(k-1)==0)ans+=ndp[j];
		}
		ans%=mod;
		for(int j=0;j<=sz;j++)ndp[j]=(ndp[j]+dp[j])%mod;
		swap(ndp,dp);
	}
	cout<<ans%mod<<endl;
	return 0;
}

Submission Info

Judge Result