Submission #1076540

---

Source Code Expand

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <stack>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
using namespace std;

const int mmod = 1000000007;

//vector<vector<vector<int> > cnt;

vector<vector<vector<pair<int, int> > > > M;

int calc(int one, int zero, int step, int depth, int k) {
  // one, one-(k-1), ... one-(k-1)*(step-1) are possible.
  // zero is remaining freedom.

  int plus = 0;
  if (one-(k-1)*(step-1) <= 0 && one % (k-1) == 0) {
    plus = 1;
    step = one / (k-1);
  }
  step = min(step, one/(k-1)+1);
  if (zero == 0) {
    return plus;
  }

  if (one < 0 || zero < 0 || step == 0) return plus;

  if (depth == 0) {
    return plus; //one >= 0 && one-(k-1)*(step-1) <= 0 && one % (k-1) == 0;
  }
  while (step && one > 0 && one > depth * (k-1)) {
    one -= k-1;
    step --;
  }
  zero = min(zero, depth * (k-1));
  if (step == 0) return plus;

//  printf("%d %d %d %d\n", one, zero, step, depth);
  int now = (depth << 15) + step;
  for (auto pr : M[zero][one])
    if (pr.first == now) return (pr.second + plus) % mmod;

  int pl = 1;
  int next_step = step;
  for (int j=0; j<depth-1; j++) {
    next_step += pl;
    pl *= k;
    if (one-(k-1)*(next_step-1) < 0) break;
  }
//printf("%d %lld ", one, next_step);
  next_step = min(next_step, one/(k-1)+1);
//printf("%lld\n", next_step);

  int res = 0;
  for (int i=0; i<k; i++) {
    if (i == 0) {
      res = calc(one, zero-(k-1), step, depth-1, k);
      continue;
    }
    int next_zero = zero - (k-1-i);
    int next_one = one - i;
    res += calc(next_one, next_zero, next_step, depth-1, k);
    if (res >= mmod) res -= mmod;
  }
//  printf("one = %d, zero = %d, step = %d, depth = %d, k = %d : %d\n", one, zero, step, depth, k, res);
  M[zero][one].push_back(pair<int, int>(now, res));
  return (res + plus) % mmod;
}


int main()
{
  int n, m, k;
  cin >> n >> m >> k;
  if (k == n+m) {
    printf("1\n");
    return 0;
  }

  int depth = (n+m-1)/(k-1);
  M.resize(n+1);
  for (int i=0; i<=n; i++)
    M[i].resize(m+1);
  // i = 0 .. depth-1
  // p = 0 .. k-1
  // j = 0 .. n+m
/*  cnt.resize(depth);
  for (int i=0; i<depth; i++) {
    cnt[i].resize(k);
    for (int p=0; p<k-1; p++)
      cnt[i][p].resize(n+m);
  }*/

/*  // cnt[i][p][j] : possible ways to make (k^i)*p with j nodes
  for (int i=0; i<depth; i++) {
    cnt[i][1][1] = 1;

    for (int p=1; p<k; p++) {
      
    }
  }*/
    


  cout << calc(m, n, 1, depth, k) << endl;
}

Submission Info

Judge Result