SRM534 Div2 Hard

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

view plainprint?

1. const int N = 5;  
2. vector<int> num[N];  
3.   
4. const int L = 26;  
5. int memo[L][L][L][L][L];  
6.   
7. const int mod = 1000000007;  
8.   
9. int idx[N];  
10.   
11. int rec(void)  
12. {     
13.   int &ret = memo[idx[0]][idx[1]][idx[2]][idx[3]][idx[4]];  
14.   if (ret != -1) return ret;  
15.   
16.   lli sum = 0;  
17.   
18.   for (int i = 0; i < N; ++i) {  
19.     int j = (i + 1) % N;  
20.   
21.     if (num[i][idx[i]]) ; else continue;  
22.     if (num[j][idx[j]]) ; else continue;  
23.   
24.     const int a = idx[i], b = idx[j];  
25.   
26.     int n = num[i][idx[i]], m = num[j][idx[j]];  
27.   
28.     if (n % 2 && m % 2) {  
29.       idx[i] = max(idx[i] - 1, 0);  
30.       idx[j] = max(idx[j] - 1, 0);       
31.       sum = (sum + (lli)rec()) % mod;  
32.     }  
33.     
34.     idx[i] = distance(num[i].begin(), lower_bound(num[i].begin(), num[i].end(), n / 2));  
35.     idx[j] = distance(num[j].begin(), lower_bound(num[j].begin(), num[j].end(), m / 2));  
36.     sum = (sum + (lli)rec()) % mod;  
37.   
38.     idx[i] = a;  
39.     idx[j] = b;  
40.   }  
41.   
42.   return ret = sum;  
43. }  
44.   
45. class EllysFiveFriends {  
46. public:  
47.   int getZero(vector <int> ns)  
48.   {  
49.     fill(num, num + 5, vector<int>());     
50.   
51.     for (int i = 0; i < N; ++i) {  
52.       num[i].push_back(ns[i]);  
53.       while (num[i].back()) {  
54.         int n = num[i].back();  
55.         if (n % 2) num[i].push_back(n - 1);  
56.         else num[i].push_back(n / 2);  
57.       }  
58.       reverse(num[i].begin(), num[i].end());  
59.     }  
60.   
61.     for (int i = 0; i < N; ++i) {  
62.       idx[i] = (int)num[i].size() - 1;  
63.     }  
64.   
65.     fill(&memo[0][0][0][0][0], &memo[L - 1][L - 1][L - 1][L - 1][L], -1);  
66.     memo[0][0][0][0][0] = 1;  
67.   
68.     return rec();  
69.   }  
70. };  

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();
  }
};