Submission #1075450

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007;
VVI wy;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,m,k;
  cin>>n>>m>>k;
  in ml=(n+m-1)/(k-1);
  wy.resize(ml+1,VI(m+1,0));
  wy[0][0]=1;
  in sm=0;
  for(in l=1;l<=ml;++l){
    for(in pu=0;pu<=m;++pu){
      for(in nu=1;nu<=k-1;++nu){
	if(nu+pu>m)
	  break;
	if((m-pu-nu)%(k-1)==0 && ((l-1)*(k-1)+k-(nu+pu)<=n))
	  sm+=wy[l-1][pu];
      }
    }
    for(in pu=0;pu<=m;++pu){
      for(in nu=0;nu<=k-1;++nu){
	if(nu+pu>m)
	  break;
	wy[l][nu+pu]+=wy[l-1][pu];
	wy[l][nu+pu]%=mdl;
      }
    }
  }
  sm%=mdl;
  cout<<sm<<endl;
  return 0;
}

Submission Info

Judge Result