Submission #1725730

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

const int MOD = 1e9 + 7;

void add(int &a, int b)
{
	a+=b;
	while(a>=MOD) a-=MOD;
}

int mult(int a, int b)
{
	return (a*1LL*b)%MOD;
}

int dp[4017][2017][2];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m,kk; cin>>n>>m>>kk;
	dp[0][0][0] = 1;
	for(int i = 0; i < (n+m-1)/(kk-1); i++)
	{
		for(int j = 0; j <= n; j++)
		{
			for(int k = 0; k < 2; k++)
			{
				int v = dp[i][j][k];
				if(v==0) continue;
				for(int z=0;z<kk;z++)
				{
					int newk=(z!=0);
					int newi=i+1;
					int newj=j+z;
					if(newj>n) continue;
					add(dp[newi][newj][newk],v);
				}
			}
		}
	}
	int ans=0;
	for(int i=1;i<=(n+m-1)/(kk-1);i++)
	{
		for(int j = n; j >= 0; j-=(kk-1))
		{
			int sj = (kk-1)*i - j;
			if(sj>=0&&sj<=m-1&&(m-1-sj)%(kk-1)==0)
			{
				add(ans,dp[i][j][1]);
			}
		}
	}
	cout<<ans<<'\n';
}

Submission Info

Judge Result