Submission #1261462

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define maxn 3111
#define rep(i,a,b) for(int i=a;i<=b;++i)

typedef long long ll;
ll f[maxn*2][maxn*2];
ll mod=1000000007;
ll ans;
int n,m,k;

ll upd(ll &x,ll y)
{
	x+=y;
	x>=mod?x-=mod:(1);
}

int main()
{
	cin>>n>>m>>k;
	f[0][0]=1;
	rep(i,1,n+m)
	{
		rep(j,0,n+m)
		{
			upd(f[i][j],f[i-1][j]);
			upd(f[i][j+k],mod-f[i-1][j]);
		}
		rep(j,1,n+m)
			upd(f[i][j],f[i][j-1]);
	}
	int nn=n%(k-1);
	rep(i,1,n+m)
	{
		rep(j,0,n+m)
		{
			if (!f[i][j]) continue;
			int p=j,q=i*(k-1)-j;
			if (q<0) break;
			if (p<=n && q<m && (p%(k-1)==nn))
			{
				upd(ans,f[i][j]);
				upd(ans,mod-f[i-1][j]);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result