SRM534 Div2 Hard

1000
lg 10000 が充分小さいことに着目して、メモ化する。
メモを long long int で持つとメモリで落ちた。

const int N = 5;
vector<int> num[N];

const int L = 26;
int memo[L][L][L][L][L];

const int mod = 1000000007;

int idx[N];

int rec(void)
{   
  int &ret = memo[idx[0]][idx[1]][idx[2]][idx[3]][idx[4]];
  if (ret != -1) return ret;

  lli sum = 0;

  for (int i = 0; i < N; ++i) {
    int j = (i + 1) % N;

    if (num[i][idx[i]]) ; else continue;
    if (num[j][idx[j]]) ; else continue;

    const int a = idx[i], b = idx[j];

    int n = num[i][idx[i]], m = num[j][idx[j]];

    if (n % 2 && m % 2) {
      idx[i] = max(idx[i] - 1, 0);
      idx[j] = max(idx[j] - 1, 0);     
      sum = (sum + (lli)rec()) % mod;
    }
  
    idx[i] = distance(num[i].begin(), lower_bound(num[i].begin(), num[i].end(), n / 2));
    idx[j] = distance(num[j].begin(), lower_bound(num[j].begin(), num[j].end(), m / 2));
    sum = (sum + (lli)rec()) % mod;

    idx[i] = a;
    idx[j] = b;
  }

  return ret = sum;
}

class EllysFiveFriends {
public:
  int getZero(vector <int> ns)
  {
    fill(num, num + 5, vector<int>());   

    for (int i = 0; i < N; ++i) {
      num[i].push_back(ns[i]);
      while (num[i].back()) {
        int n = num[i].back();
        if (n % 2) num[i].push_back(n - 1);
        else num[i].push_back(n / 2);
      }
      reverse(num[i].begin(), num[i].end());
    }

    for (int i = 0; i < N; ++i) {
      idx[i] = (int)num[i].size() - 1;
    }

    fill(&memo[0][0][0][0][0], &memo[L - 1][L - 1][L - 1][L - 1][L], -1);
    memo[0][0][0][0][0] = 1;

    return rec();
  }
};