{"id":968,"date":"2020-04-12T11:52:10","date_gmt":"2020-04-12T18:52:10","guid":{"rendered":"http:\/\/209.126.2.187\/?p=968"},"modified":"2021-07-04T21:26:27","modified_gmt":"2021-07-05T04:26:27","slug":"binary-exponentiation-dp-counting","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/12\/binary-exponentiation-dp-counting\/","title":{"rendered":"Linear Recurrence Relation & Binary Exponentiation & DP Counting"},"content":{"rendered":"\n

Summary <\/h2>\n\n\n\n

In this post, I will introduce a common technique in some DP counting problems: binary exponentiation. <\/p>\n\n\n\n

Typically, in these problems, you will be given a number n<\/code> and you are asked to return the number of valid combinations. You need to figure out the initial state and the transform function between states. The problems then could be solved by DP. <\/p>\n\n\n\n

During the iteration, if the the current state and the previous states has a linear<\/strong> recurrence relation<\/strong>. Then a bonus is that you could use binary exponentiation<\/strong> of square matrixes to reduce the complexity to log(n)<\/code>.<\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
1411. Number of Ways to Paint N \u00d7 3 Grid <\/a><\/td>DP in Linear Structures + Binary Exponentiation<\/td>6 points<\/td>\n<\/tr>\n
935. Knight Dialer<\/a><\/td>DP in Linear Structures + Binary Exponentiation<\/td>5-6 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

LC 1411. Number of Ways to Paint N \u00d7 3 Grid<\/a><\/h4>\n\n\n\n

A naive O(12*12*3 n)<\/code> solution is not difficult. The number of states is 12n<\/code>. At each i<\/code>, it takes O(12*3)<\/code> time to see if the current option has conflicts with the previous one. <\/p>\n\n\n\n

alg[i][prev] = sum {(alg[i + 1][curr]) if curr & prev not conflict, for curr in 12 options}\n\/\/ alg[n - 1][prev] = sum {1 if ok(curr, prev) for curr in 12 options}<\/code><\/pre>\n\n\n\n
A better DP will decrease the number of states. At each i<\/code>, the number of states now becomes 2, either in pattern 121, or pattern 123. <\/p>\n\n\n\n
pattern 121: 121, 131, 212, 232, 313, 323.\npattern 123: 123, 132, 213, 231, 312, 321.<\/code><\/pre>\n\n\n\n
We consider the next possible pattern for each current pattern.<\/p>\n\n\n\n
Patter 121 can be followed by: 212, 213, 232, 312, 313;\n3 121s, 2 123s \n\nPatter 123 can be followed by: 212, 231, 312, 232; \n2 121s, 2 123s<\/code><\/pre>\n\n\n\n
We can write the following transform equation.<\/p>\n\n\n\n
\/\/ alg[i][0]: 121, alg[i][1]: 123\nalg[i][0] = alg[i + 1][0] * 3 + alg[i + 1][1] * 2\nalg[i][1] = alg[i + 1][0] * 2 + alg[i + 1][1] * 2\n[alg[i][0],    [[3, 2]   [alg[i + 1][0],  \n alg[i][1]] =   [2, 2]]   alg[i + 1][1]]\n\/\/ [alg[n - 1][0],    [6,\n    alg[n - 1][1]] =   6]<\/code><\/pre>\n\n\n\n
Once we get the square matrix as the transform function, we could apply the binary exponentiation for matrixes to reduce the complexity. <\/p>\n\n\n\n
\/\/ The final result will be \n\/\/ fastPow(a, n - 1) * [6, 6]\nvector<vector<ll>> modMul(vector<vector<ll>> const &a, vector<vector<ll>> const &b) {\n    int n = a.size();\n    vector<vector<ll>> result(n, vector<ll>(n));\n    for (int i = 0; i < n; ++i) {\n        for (int j = 0; j < n; ++j) {\n            for (int k = 0; k < n; ++k) {\n                result[i][j] += a[i][k] * b[k][j];\n                result[i][j] %= MOD;\n            }\n        }\n    }\n    return result;\n}\n\nvector<vector<ll>> fastPow(vector<vector<ll>> const &a, int n) {\n    if (n == 0) {\n        int n = a.size();\n        vector<vector<ll>> result(n, vector<ll>(n));\n        for (int i = 0; i < n; ++i) {\n            result[i][i] = 1;\n        }\n        return result;\n    } else if (n == 1) {\n        return a;\n    } else {\n        if ((n & 1) == 0) {\n            vector<vector<ll>> a_square = modMul(a, a);\n            return fastPow(a_square, n \/ 2);\n        } else {\n            return modMul(a, fastPow(a, n - 1));\n        }\n    }\n}<\/code><\/pre>\n\n\n\n
Template<\/h2>\n\n\n\n
\/\/ m * n . n * l => m * l\nvector<vector<ll>> MatMul(vector<vector<ll>> const &a, vector<vector<ll>> const &b) {\n  int m = a.size();\n  int n = a[0].size();\n  int l = b[0].size();\n  vector<vector<ll>> res(m, vector<ll>(l));\n  for (int i = 0; i < m; ++i) {\n    for (int j = 0; j < l; ++j) {\n      for (int k = 0; k < n; ++k) {\n        res[i][j] += a[i][k] * b[k][j];\n        res[i][j] %= kMod;\n      }\n    }\n  }\n  return res;\n}\n\nvector<vector<ll>> FastPower(vector<vector<ll>> const &a, ll n) {\n  if (n == 0) {\n    int n = a.size();\n    vector<vector<ll>> result(n, vector<ll>(n));\n    for (int i = 0; i < n; ++i) {\n        result[i][i] = 1;\n    }\n    return result;\n  } else if (n == 1) {\n      return a;\n  } else {\n      if ((n & 1) == 0) {\n          vector<vector<ll>> a_square = MatMul(a, a);\n          return FastPower(a_square, n \/ 2);\n      } else {\n          return MatMul(a, FastPower(a, n - 1));\n      }\n  }\n}<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
Summary In this post, I will introduce a common technique in some DP counting problems: binary exponentiation. Typically, in these problems, you will be given a number n and you are asked to return the number of valid combinations. You need to figure out the initial state and the transform function between states. The problems…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,60,61],"tags":[],"class_list":["post-968","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-counting","category-dp-state-compression"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/968","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=968"}],"version-history":[{"count":13,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/968\/revisions"}],"predecessor-version":[{"id":1606,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/968\/revisions\/1606"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}