{"id":3006,"date":"2023-06-09T06:17:56","date_gmt":"2023-06-08T22:17:56","guid":{"rendered":"https:\/\/www.shuizilong.com\/house\/?p=3006"},"modified":"2023-06-09T06:17:56","modified_gmt":"2023-06-08T22:17:56","slug":"luogu-p1933-noi2010-%e6%97%85%e8%a1%8c%e8%b7%af%e7%ba%bf","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/luogu-p1933-noi2010-%e6%97%85%e8%a1%8c%e8%b7%af%e7%ba%bf\/","title":{"rendered":"Luogu P1933. [NOI2010] \u65c5\u884c\u8def\u7ebf"},"content":{"rendered":"<ul>\n<li><a href=\"https:\/\/www.luogu.com.cn\/problem\/P1933\">https:\/\/www.luogu.com.cn\/problem\/P1933<\/a><\/li>\n<\/ul>\n<p>\u7ecf\u5178\u63d2\u5934 dp\uff0c\u4f46\u662f\u548c\u4f20\u7edf\u7684\u4e00\u6761\u8def\u5f84\u95ee\u9898\u76f8\u6bd4\uff0c\u6211\u4eec\u8fd8\u9700\u8981\u538b\u7f29\u8fdb\u8f6e\u5ed3\u7ebf\u4e0a\u4f4d\u7f6e\u7684\u6807\u53f7\uff0c\u8fd8\u8981\u7ef4\u62a4\u63d2\u5934\u7684\u65b9\u5411\uff08\u9012\u589e\u8fd8\u662f\u9012\u964d\uff09\uff0c\u7136\u540e\u5173\u952e\u662f\u63d2\u5934\u7684\u65b9\u5411\u4fe1\u606f\u5728 m=3 \u7684\u60c5\u51b5\u4e0b\uff0c\u662f\u53ef\u4ee5\u5ba2\u4e32\u8fde\u901a\u6027\u4fe1\u606f\u7684\uff0c\u8fd9\u6837\u53ef\u4ee5\u628a\u63d2\u5934\u63a7\u5236\u5728 int \u8303\u56f4\u91cc\uff08\u6070\u597d 32 \u4f4d\uff0c\u6ce8\u610f\u7528 uint\u3002\uff09<\/p>\n<pre class=\"brush: cpp; light: false; title: ; toolbar: true; notranslate\" title=\"\">\r\n\/*\r\n    Last Weapon is my own algorithms library for competitive programming, it is a fork from ACL with some alternative algorithms and additional features. Use it at your own risk.\r\n    Repo: https:\/\/github.com\/lychees\/last-weapon\r\n    Blog: https:\/\/www.shuizilong.com\/house\r\n*\/\r\n#pragma comment(linker, &quot;\/STACK:36777216&quot;)\r\n#define LOCAL\r\n#include &lt;functional&gt;\r\n#include &lt;algorithm&gt;\r\n#include &lt;iostream&gt;\r\n#include &lt;fstream&gt;\r\n#include &lt;sstream&gt;\r\n#include &lt;iomanip&gt;\r\n#include &lt;numeric&gt;\r\n#include &lt;cstring&gt;\r\n#include &lt;climits&gt;\r\n#include &lt;cassert&gt;\r\n#include &lt;complex&gt;\r\n#include &lt;cstdio&gt;\r\n#include &lt;string&gt;\r\n#include &lt;vector&gt;\r\n#include &lt;bitset&gt;\r\n#include &lt;queue&gt;\r\n#include &lt;stack&gt;\r\n#include &lt;cmath&gt;\r\n#include &lt;ctime&gt;\r\n#include &lt;list&gt;\r\n#include &lt;set&gt;\r\n#include &lt;map&gt;\r\n\r\n\r\nusing namespace std;\r\n\r\n#define REP(i, n) for (int i=0;i&lt;n;++i)\r\n#define FOR(i, a, b) for (int i=a;i&lt;b;++i)\r\n#define DWN(i, b, a) for (int i=b-1;i&gt;=a;--i)\r\n#define REP_1(i, n) for (int i=1;i&lt;=n;++i)\r\n#define FOR_1(i, a, b) for (int i=a;i&lt;=b;++i)\r\n#define DWN_1(i, b, a) for (int i=b;i&gt;=a;--i)\r\n\r\n#define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it)\r\n#define rECH(it, A) for (__typeof((A).rbegin()) it=(A).rbegin(); it != (A).rend(); ++it)\r\n#define REP_S(i, str) for (char*i=str;*i;++i)\r\n#define REP_L(i, hd, suc) for (int i=hd;i;i=suc&#x5B;i])\r\n#define REP_G(i, u) REP_L(i,hd&#x5B;u],suc)\r\n#define REP_SS(x, s) for (int x=s;x;x=(x-1)&amp;s)\r\n#define DO(n) for ( int ____n = n; ____n--&gt;0; )\r\n\r\n#define ALL(A) A.begin(), A.end()\r\n#define LLA(A) A.rbegin(), A.rend()\r\n#define CPY(A, B) memcpy(A, B, sizeof(A))\r\n#define INS(A, P, B) A.insert(A.begin() + P, B)\r\n#define ERS(A, P) A.erase(A.begin() + P)\r\n#define LBD(A, x) (lower_bound(ALL(A), x) - A.begin())\r\n#define UBD(A, x) (upper_bound(ALL(A), x) - A.begin())\r\n#define CTN(T, x) (T.find(x) != T.end())\r\n#define SZ(A) int((A).size())\r\n#define PB push_back\r\n#define MP(A, B) make_pair(A, B)\r\n#define PTT pair&lt;T, T&gt;\r\n#define Ts *this\r\n#define rTs return Ts\r\n#define fi first\r\n#define se second\r\n#define re real()\r\n#define im imag()\r\n\r\n#define Rush for(int ____T=RD(); ____T--;)\r\n#define Display(A, n, m) {                      \\\r\n  REP(i, n){\t\t                            \\\r\n        REP(j, m-1) cout &lt;&lt; A&#x5B;i]&#x5B;j] &lt;&lt; &quot; &quot;;     \\\r\n        cout &lt;&lt; A&#x5B;i]&#x5B;m-1] &lt;&lt; endl;\t\t        \\\r\n\t}\t\t\t\t\t\t                    \\\r\n}\r\n#define Display_1(A, n, m) {                    \\\r\n\tREP_1(i, n){\t\t                        \\\r\n        REP_1(j, m-1) cout &lt;&lt; A&#x5B;i]&#x5B;j] &lt;&lt; &quot; &quot;;   \\\r\n        cout &lt;&lt; A&#x5B;i]&#x5B;m] &lt;&lt; endl;\t\t        \\\r\n\t}\t\t\t\t\t\t                    \\\r\n}\r\n\r\ntypedef long long LL;\r\ntypedef double DB;\r\ntypedef unsigned uint;\r\ntypedef unsigned long long uLL;\r\n\r\ntypedef vector&lt;int&gt; VI;\r\ntypedef vector&lt;char&gt; VC;\r\ntypedef vector&lt;string&gt; VS;\r\ntypedef vector&lt;LL&gt; VL;\r\ntypedef vector&lt;DB&gt; VF;\r\ntypedef set&lt;int&gt; SI;\r\ntypedef set&lt;string&gt; SS;\r\ntypedef map&lt;int, int&gt; MII;\r\ntypedef map&lt;string, int&gt; MSI;\r\ntypedef pair&lt;int, int&gt; PII;\r\ntypedef pair&lt;LL, LL&gt; PLL;\r\ntypedef vector&lt;PII&gt; VII;\r\ntypedef vector&lt;VI&gt; VVI;\r\ntypedef vector&lt;VII&gt; VVII;\r\n\r\ntemplate&lt;class T&gt; inline T&amp; RD(T &amp;);\r\ntemplate&lt;class T&gt; inline void OT(const T &amp;);\r\ninline LL RD(){LL x; return RD(x);}\r\ninline DB&amp; RF(DB &amp;);\r\ninline DB RF(){DB x; return RF(x);}\r\ninline char* RS(char *s);\r\ninline char&amp; RC(char &amp;c);\r\ninline char RC();\r\ninline char&amp; RC(char &amp;c){scanf(&quot; %c&quot;, &amp;c); return c;}\r\ninline char RC(){char c; return RC(c);}\r\n\r\ntemplate&lt;class T0, class T1&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1){RD(x0), RD(x1); return x0;}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2){RD(x0), RD(x1), RD(x2); return x0;}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline T0&amp; RD(T0 &amp;x0, T1 &amp;x1, T2 &amp;x2, T3 &amp;x3, T4 &amp;x4, T5 &amp;x5, T6 &amp;x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;}\r\ntemplate&lt;class T0, class T1&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1){OT(x0), OT(x1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2){OT(x0), OT(x1), OT(x2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3){OT(x0), OT(x1), OT(x2), OT(x3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4, const T5 &amp;x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void OT(const T0 &amp;x0, const T1 &amp;x1, const T2 &amp;x2, const T3 &amp;x3, const T4 &amp;x4, const T5 &amp;x5, const T6 &amp;x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);}\r\ninline char&amp; RC(char &amp;a, char &amp;b){RC(a), RC(b); return a;}\r\ninline char&amp; RC(char &amp;a, char &amp;b, char &amp;c){RC(a), RC(b), RC(c); return a;}\r\ninline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d){RC(a), RC(b), RC(c), RC(d); return a;}\r\ninline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;}\r\ninline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e, char &amp;f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;}\r\ninline char&amp; RC(char &amp;a, char &amp;b, char &amp;c, char &amp;d, char &amp;e, char &amp;f, char &amp;g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b){RF(a), RF(b); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c){RF(a), RF(b), RF(c); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d){RF(a), RF(b), RF(c), RF(d); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e, DB &amp;f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;}\r\ninline DB&amp; RF(DB &amp;a, DB &amp;b, DB &amp;c, DB &amp;d, DB &amp;e, DB &amp;f, DB &amp;g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;}\r\ninline void RS(char *s1, char *s2){RS(s1), RS(s2);}\r\ninline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);}\r\n\r\ntemplate&lt;class T&gt; inline void RST(T &amp;A){memset(A, 0, sizeof(A));}\r\ntemplate&lt;class T&gt; inline void FLC(T &amp;A, int x){memset(A, x, sizeof(A));}\r\ntemplate&lt;class T&gt; inline void CLR(T &amp;A){A.clear();}\r\n\r\ntemplate&lt;class T0, class T1&gt; inline void RST(T0 &amp;A0, T1 &amp;A1){RST(A0), RST(A1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){RST(A0), RST(A1), RST(A2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){RST(A0), RST(A1), RST(A2), RST(A3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void RST(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);}\r\ntemplate&lt;class T0, class T1&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, int x){FLC(A0, x), FLC(A1, x);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void FLC(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);}\r\ntemplate&lt;class T&gt; inline void CLR(priority_queue&lt;T&gt; &amp;Q){while (!Q.empty()) Q.pop();}\r\ntemplate&lt;class T&gt; inline void CLR(stack&lt;T&gt; &amp;S){while (!S.empty()) S.pop();}\r\ntemplate&lt;class T&gt; inline void CLR(queue&lt;T&gt; &amp;Q){while (!Q.empty()) Q.pop();}\r\n\r\ntemplate&lt;class T0, class T1&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1){CLR(A0), CLR(A1);}\r\ntemplate&lt;class T0, class T1, class T2&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2){CLR(A0), CLR(A1), CLR(A2);}\r\ntemplate&lt;class T0, class T1, class T2, class T3&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);}\r\ntemplate&lt;class T0, class T1, class T2, class T3, class T4, class T5, class T6&gt; inline void CLR(T0 &amp;A0, T1 &amp;A1, T2 &amp;A2, T3 &amp;A3, T4 &amp;A4, T5 &amp;A5, T6 &amp;A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);}\r\ntemplate&lt;class T&gt; inline void CLR(T &amp;A, int n){REP(i, n) CLR(A&#x5B;i]);}\r\n\r\ntemplate&lt;class T&gt; inline bool EPT(T &amp;a){return a.empty();}\r\ntemplate&lt;class T&gt; inline T&amp; SRT(T &amp;A){sort(ALL(A)); return A;}\r\ntemplate&lt;class T, class C&gt; inline T&amp; SRT(T &amp;A, C cmp){sort(ALL(A), cmp); return A;}\r\ntemplate&lt;class T&gt; inline T&amp; RVS(T &amp;A){reverse(ALL(A)); return A;}\r\ntemplate&lt;class T&gt; inline T&amp; UNQQ(T &amp;A){A.resize(unique(ALL(A))-A.begin());return A;}\r\ntemplate&lt;class T&gt; inline T&amp; UNQ(T &amp;A){SRT(A);return UNQQ(A);}\r\ntemplate&lt;class T, class C&gt; inline T&amp; UNQ(T &amp;A, C cmp){SRT(A, cmp);return UNQQ(A);}\r\n\r\n\r\n\r\n\/** Constant List .. **\/ \/\/{\r\n\r\nint MOD = int(1e9) + 7;\r\nconst int INF = 0x3f3f3f3f;\r\nconst LL INFF = 0x3f3f3f3f3f3f3f3fLL;\r\nconst DB EPS = 1e-9;\r\nconst DB OO = 1e20;\r\nconst DB PI = acos(-1.0); \/\/M_PI;\r\n\r\nconst int dx&#x5B;] = {-1, 1, 0, 0};\r\nconst int dy&#x5B;] = {0, 0, 1, -1};\r\n\r\n\r\n\/** Add On .. **\/ \/\/{\r\n\r\ntemplate&lt;class T&gt; inline bool checkMin(T &amp;a,const T b){return b &lt; a ? a = b, 1 : 0;}\r\ntemplate&lt;class T&gt; inline bool checkMax(T &amp;a,const T b){return a &lt; b ? a = b, 1 : 0;}\r\ntemplate &lt;class T, class C&gt; inline bool checkUpd(T&amp; a, const T b, C c){return c(b,a) ? a = b, 1 : 0;}\r\ntemplate&lt;class T&gt; inline T min(T a, T b, T c){return min(min(a, b), c);}\r\ntemplate&lt;class T&gt; inline T max(T a, T b, T c){return max(max(a, b), c);}\r\ntemplate&lt;class T&gt; inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));}\r\ntemplate&lt;class T&gt; inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));}\r\ntemplate&lt;class T&gt; inline T sqr(T a){return a*a;}\r\ntemplate&lt;class T&gt; inline T cub(T a){return a*a*a;}\r\ntemplate&lt;class T&gt; inline T ceil(T x, T y){return (x - 1) \/ y + 1;}\r\ntemplate&lt;class T&gt; T abs(T x){return x&gt;0?x:-x;}\r\ninline int sgn(DB x){return x &lt; -EPS ? -1 : x &gt; EPS;}\r\ninline int sgn(DB x, DB y){return sgn(x - y);}\r\n\r\ntemplate&lt;typename T1, typename T2&gt; istream&amp; operator&gt;&gt;(istream&amp; in, pair&lt;T1, T2&gt;&amp; a) {\r\n    in &gt;&gt; a.fi &gt;&gt; a.se;\r\n    return in;\r\n}\r\ntemplate&lt;typename T, size_t N&gt; istream&amp; operator&gt;&gt;(istream&amp; in, array&lt;T, N&gt;&amp; a) {\r\n    REP(i, N) cin &gt;&gt; a&#x5B;i];\r\n    return in;\r\n}\r\ntemplate&lt;typename T&gt; istream&amp; operator&gt;&gt;(istream&amp; in, vector&lt;T&gt;&amp; a) {\r\n    REP(i, SZ(a)) in &gt;&gt; a&#x5B;i];\r\n    return in;\r\n}\r\ntemplate&lt;typename T1, typename T2&gt; ostream&amp; operator&lt;&lt;(ostream&amp; out, pair&lt;T1, T2&gt;&amp; a) {\r\n    out &lt;&lt; a.fi &lt;&lt; &quot; &quot; &lt;&lt; a.se;\r\n    return out;\r\n}\r\ntemplate&lt;typename T, size_t N&gt; ostream&amp; operator&lt;&lt;(ostream&amp; out, array&lt;T, N&gt;&amp; a) {\r\n    REP(i, N-1) out &lt;&lt; a&#x5B;i] &lt;&lt; &quot; &quot;; if (N) out &lt;&lt; a.back();\r\n    return out;\r\n}\r\ntemplate&lt;typename T&gt; ostream&amp; operator&lt;&lt;(ostream&amp; out, vector&lt;T&gt;&amp; a) {\r\n    REP(i, SZ(a)-1) out &lt;&lt; a&#x5B;i] &lt;&lt; &quot; &quot;; if (SZ(a)) out &lt;&lt; a.back();\r\n    return out;\r\n}\r\n\r\n\r\n\r\n\r\n\r\n\/** I\/O Accelerator Interface .. **\/ \/\/{\r\n#define g (c=getchar())\r\n#define d isdigit(g)\r\n#define p x=x*10+c-'0'\r\n#define n x=x*10+'0'-c\r\n#define pp l\/=10,p\r\n#define nn l\/=10,n\r\ntemplate&lt;class T&gt; inline T&amp; RD(T &amp;x){\r\n    char c;while(g,c!='-'&amp;&amp;!isdigit(c));\r\n    if (c=='-'){x='0'-g;while(d)n;}\r\n    else{x=c-'0';while(d)p;}\r\n    return x;\r\n}\r\ninline DB&amp; RF(DB &amp;x){\r\n    char c;while(g,c!='-'&amp;&amp;c!='.'&amp;&amp;!isdigit(c));\r\n    if(c=='-')if(g=='.'){x=0;DB l=1;while(d)nn;x*=l;}\r\n        else{x='0'-c;while(d)n;if(c=='.'){DB l=1;while(d)nn;x*=l;}}\r\n    else if(c=='.'){x=0;DB l=1;while(d)pp;x*=l;}\r\n        else{x=c-'0';while(d)p;if(c=='.'){DB l=1;while(d)pp;x*=l;}}\r\n    return x;\r\n}\r\n#undef nn\r\n#undef pp\r\n#undef n\r\n#undef p\r\n#undef d\r\n#undef g\r\ninline char* RS(char *s){\r\n    scanf(&quot;%s&quot;, s);\r\n    return s;\r\n}\r\n\r\nLL last_ans; int Case; template&lt;class T&gt; inline void OT(const T &amp;x){\r\n    cout &lt;&lt; x &lt;&lt; endl;\r\n}\r\nnamespace lastweapon {}\r\nnamespace lastweapon {\r\n\r\nnamespace NT{\r\ninline LL gcd(LL a, LL b){return b?gcd(b,a%b):a;}\r\ninline LL lcm(LL a, LL b){return a*b\/gcd(a,b);}\r\n\r\ninline void INC(int &amp;a, int b){a += b; if (a &gt;= MOD) a -= MOD;}\r\ninline int sum(int a, int b){a += b; if (a &gt;= MOD) a -= MOD; return a;}\r\n\r\ninline void DEC(int &amp;a, int b){a -= b; if (a &lt; 0) a += MOD;}\r\ninline int dff(int a, int b){a -= b; if (a &lt; 0) a  += MOD; return a;}\r\ninline void MUL(int &amp;a, int b){a = (LL)a * b % MOD;}\r\ninline int pdt(int x,int y) {\r\n    int ret; __asm__ __volatile__ (&quot;\\tmull %%ebx\\n\\tdivl %%ecx\\n&quot;:&quot;=d&quot;(ret):&quot;a&quot;(x),&quot;b&quot;(y),&quot;c&quot;(MOD));\r\n    return ret;\r\n}\r\n\r\n\r\ninline int gcd(int m, int n, int &amp;x, int &amp;y){\r\n\r\n    x = 1, y = 0; int xx = 0, yy = 1, q;\r\n\r\n    while (1){\r\n        q = m \/ n, m %= n;\r\n        if (!m){x = xx, y = yy; return n;}\r\n        DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy));\r\n        q = n \/ m, n %= m;\r\n        if (!n) return m;\r\n        DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y));\r\n    }\r\n}\r\n\r\ninline int sum(int a, int b, int c){return sum(a, sum(b, c));}\r\ninline int sum(int a, int b, int c, int d){return sum(sum(a, b), sum(c, d));}\r\ninline int pdt(int a, int b, int c){return pdt(a, pdt(b, c));}\r\ninline int pdt(int a, int b, int c, int d){return pdt(pdt(a, b), pdt(c, d));}\r\n\r\ninline int pow(int a, LL b){\r\n    int c(1); while (b){\r\n        if (b&amp;1) MUL(c, a);\r\n        MUL(a, a), b &gt;&gt;= 1;\r\n    }\r\n    return c;\r\n}\r\n\r\ntemplate&lt;class T&gt; inline T pow(T a, LL b){\r\n    T c(1); while (b){\r\n        if (b&amp;1) c *= a;\r\n        a *= a, b &gt;&gt;= 1;\r\n    }\r\n    return c;\r\n}\r\n\r\ntemplate&lt;class T&gt; inline T pow(T a, int b){\r\n    return pow(a, (LL)b);\r\n}\r\n\r\ninline int _I(int b){\r\n    int a = MOD, x1 = 0, x2 = 1, q; while (1){\r\n        q = a \/ b, a %= b;\r\n        if (!a) return x2;\r\n        DEC(x1, pdt(q, x2));\r\n\r\n        q = b \/ a, b %= a;\r\n        if (!b) return x1;\r\n        DEC(x2, pdt(q, x1));\r\n    }\r\n}\r\n\r\ninline void DIV(int &amp;a, int b){MUL(a, _I(b));}\r\ninline int qtt(int a, int b){return pdt(a, _I(b));}\r\n\r\nstruct Int{\r\n    int val;\r\n\r\n    operator int() const{return val;}\r\n\r\n    Int(int _val = 0):val(_val){\r\n        val %= MOD; if (val &lt; 0) val += MOD;\r\n    }\r\n    Int(LL _val):val(_val){\r\n        _val %= MOD; if (_val &lt; 0) _val += MOD;\r\n        val = _val;\r\n    }\r\n\r\n    Int&amp; operator +=(const int&amp; rhs){INC(val, rhs);rTs;}\r\n    Int operator +(const int&amp; rhs) const{return sum(val, rhs);}\r\n    Int&amp; operator -=(const int&amp; rhs){DEC(val, rhs);rTs;}\r\n    Int operator -(const int&amp; rhs) const{return dff(val, rhs);}\r\n    Int&amp; operator *=(const int&amp; rhs){MUL(val, rhs);rTs;}\r\n    Int operator *(const int&amp; rhs) const{return pdt(val, rhs);}\r\n    Int&amp; operator \/=(const int&amp; rhs){DIV(val, rhs);rTs;}\r\n    Int operator \/(const int&amp; rhs) const{return qtt(val, rhs);}\r\n    Int operator-()const{return MOD-*this;}\r\n};\r\n\r\n} using namespace NT;\/\/}\r\n\r\n}  \/\/ namespace lastweapon\r\n\r\n#include &lt;bits\/stdc++.h&gt;\r\nusing namespace lastweapon;\r\n\r\n\/\/ 256 = 2^8 * 3\r\n\/\/ 3*4 = 12\r\n\r\nconst int N = 50, M = 3;\r\nconst int offset = 2, mask = (1 &lt;&lt; offset) - 1, offset2 = 8, mask2 = (1 &lt;&lt; offset2) - 1;\r\nint A&#x5B;N]&#x5B;M], B&#x5B;N*M];\r\nint n, m, d;\r\nconst int MaxSZ = 186796, Prime = 109973;\r\n\r\nstruct hashTable\r\n{\r\n    int head&#x5B;Prime], next&#x5B;MaxSZ], sz;\r\n    uint state&#x5B;MaxSZ];\r\n    int key&#x5B;MaxSZ];\r\n\r\n    void clear()\r\n    {\r\n        sz = 0;\r\n        memset(head, -1, sizeof(head));\r\n    }\r\n\r\n    void push(uint s)\r\n    {\r\n        int x = s % Prime;\r\n        for (int i = head&#x5B;x]; ~i; i = next&#x5B;i])\r\n        {\r\n            if (state&#x5B;i] == s)\r\n            {\r\n                key&#x5B;i] += d; if (key&#x5B;i] &gt; MOD) key&#x5B;i] -= MOD;\r\n                return;\r\n            }\r\n        }\r\n        state&#x5B;sz] = s, key&#x5B;sz] = d;\r\n        next&#x5B;sz] = head&#x5B;x];\r\n        head&#x5B;x] = sz++;\r\n    }\r\n\r\n    void roll()\r\n    {\r\n        for (int i = 0; i &lt; sz; i++) {\r\n            int s0 = state&#x5B;i] &amp; ((1 &lt;&lt; (offset2*m)) - 1), s1 = state&#x5B;i] ^ s0;\r\n            state&#x5B;i] = (s1 &lt;&lt; offset) | s0;\r\n        }\r\n    }\r\n} H&#x5B;2]&#x5B;3], *H0, *H1;\r\n\r\nint b&#x5B;M + 1];\r\nint b2&#x5B;M];\r\n\r\nint encode()\r\n{\r\n    uint s = 0;\r\n    for (int i = m; i &gt;= 0; --i)\r\n    {\r\n        s &lt;&lt;= offset;\r\n        s |= b&#x5B;i];\r\n    }\r\n\r\n    for (int i = m-1; i &gt;= 0; --i)\r\n    {\r\n        s &lt;&lt;= offset2;\r\n        s |= b2&#x5B;i];\r\n    }\r\n    return s;\r\n}\r\n\r\nvoid decode(uint s)\r\n{\r\n    for (int i = 0; i &lt; m; i++)\r\n    {\r\n        b2&#x5B;i] = s &amp; mask2;\r\n        s &gt;&gt;= offset2;\r\n    }\r\n    for (int i = 0; i &lt; m + 1; i++)\r\n    {\r\n        b&#x5B;i] = s &amp; mask;\r\n        s &gt;&gt;= offset;\r\n    }\r\n}\r\n\r\nbool onTheEdge(int x, int y) {\r\n    return !x || !y || (x == n-1) || (y == m-1);\r\n}\r\n\r\nint i, j;\r\nvoid push(int c, int j, int dn, int rt, int o)\r\n{\r\n    if (o &lt; 0 || n*m &lt;= o) return;\r\n    if (!o &amp;&amp; !onTheEdge(i, j)) return;\r\n    if (A&#x5B;i]&#x5B;j] != B&#x5B;o]) return;\r\n\r\n    b&#x5B;j] = dn; b&#x5B;j + 1] = rt; b2&#x5B;j] = o;\r\n\r\n    H1&#x5B;c].push(encode());\r\n}\r\n\r\nvoid init()\r\n{\r\n    cin &gt;&gt; n &gt;&gt; m; swap(n, m);\r\n    H0 = H&#x5B;0], H1 = H&#x5B;1]; for (int c = 0; c &lt; 3; c++) H1&#x5B;c].clear();\r\n\r\n    for (int j = 0; j &lt; m; j++)\r\n        for (int i = 0; i &lt; n; i++) cin &gt;&gt; A&#x5B;i]&#x5B;j];\r\n\r\n    REP(i, n*m) RD(B&#x5B;i]);\r\n}\r\n\r\nInt solve()\r\n{\r\n\r\n    if (n == 1 &amp; m == 1) { \/\/ \u7279\u5224\r\n        return A&#x5B;0]&#x5B;0] = B&#x5B;0];\r\n    }\r\n\r\n\r\n    d = 1; H1&#x5B;0].push(encode());\r\n\r\n    for (i = 0; i &lt; n; i++)\r\n    {\r\n        for (j = 0; j &lt; m; j++)\r\n        {\r\n\r\n            swap(H0, H1);\r\n            for (int c = 0; c &lt; 3; c++)\r\n                H1&#x5B;c].clear();  \/\/ c \u8868\u793a\u751f\u6210\u548c\u6d88\u5931\u4e8b\u4ef6\u53d1\u751f\u7684\u603b\u6b21\u6570\uff0c\u6700\u591a\u4e0d\u8d85\u8fc7 2 \u6b21\r\n\r\n            for (int c = 0; c &lt; 3; c++)\r\n                for (int ii = 0; ii &lt; H0&#x5B;c].sz; ii++)\r\n                {\r\n                    decode(H0&#x5B;c].state&#x5B;ii]);\r\n                    d = H0&#x5B;c].key&#x5B;ii];\r\n\r\n                    \/\/cout &lt;&lt; i &lt;&lt; &quot; &quot; &lt;&lt; j &lt;&lt; &quot; &quot; &lt;&lt; d &lt;&lt; &quot;: &quot; &lt;&lt; endl;\r\n                    \/\/REP(i, m) cout &lt;&lt; b2&#x5B;i] &lt;&lt; &quot; &quot;; cout &lt;&lt; endl;\r\n                    \/\/REP(i, m+1) cout &lt;&lt; b&#x5B;i] &lt;&lt; &quot; &quot;; cout &lt;&lt; endl;\r\n\r\n\r\n                    int lt = b&#x5B;j], up = b&#x5B;j + 1];\r\n                    bool dn = i != n-1, rt = j != m-1;\r\n                    if (lt &amp;&amp; up)\r\n                    {\r\n                        if (lt == up)    \/\/ \u5728\u4e00\u6761\u8def\u5f84\u95ee\u9898\u4e2d\uff0c\u6211\u4eec\u4e0d\u80fd\u5408\u5e76\u76f8\u540c\u7684\u63d2\u5934\u3002\r\n                        {\r\n                            \/\/ Cannot deploy here...\r\n                        }\r\n                        else      \/\/ \u6709\u53ef\u80fd\u53c2\u4e0e\u5408\u5e76\u7684\u4e24\u8005\u4e2d\u6709\u72ec\u7acb\u63d2\u5934\uff0c\u4f46\u662f\u4e5f\u53ef\u4ee5\u7528\u540c\u6837\u7684\u4ee3\u7801\u7247\u6bb5\u5904\u7406\r\n                        {\r\n                            \/\/for (int i = 0; i &lt; m + 1; i++) if (b&#x5B;i] == lt) b&#x5B;i] = up;\r\n                            if ((b2&#x5B;j-1] + 2 == b2&#x5B;j] &amp;&amp; lt == 1 &amp;&amp; up == 2) || (b2&#x5B;j] + 2 == b2&#x5B;j-1] &amp;&amp; up == 1 &amp;&amp; lt == 2)) {\r\n                                push(c, j, 0, 0, (b2&#x5B;j] + b2&#x5B;j-1])\/2);\r\n                            }\r\n                        }\r\n                    }\r\n                    else if (lt || up)\r\n                    {\r\n                        int t = lt | up;\r\n\r\n                        int o = lt ? b2&#x5B;j-1] : b2&#x5B;j];\r\n\r\n                        if (dn)\r\n                        {\r\n                            if (t == 1) push(c, j, t, 0, o+1);\r\n                            else push(c, j, t, 0, o-1);\r\n                        }\r\n                        if (rt)\r\n                        {\r\n                            if (t == 1) push(c, j, 0, t, o+1);\r\n                            else push(c, j, 0, t, o-1);\r\n                        }\r\n                        \/\/ \u4e00\u4e2a\u63d2\u5934\u6d88\u5931\u7684\u60c5\u51b5\uff0c\u5982\u679c\u662f\u72ec\u7acb\u63d2\u5934\u5219\u610f\u5473\u7740\u6d88\u5931\uff0c\u5982\u679c\u662f\u6210\u5bf9\u51fa\u73b0\u7684\u63d2\u5934\u5219\u76f8\u5f53\u4e8e\u751f\u6210\u4e86\u4e00\u4e2a\u72ec\u7acb\u63d2\u5934\uff0c\r\n                        \/\/ \u65e0\u8bba\u54ea\u4e00\u7c7b\u4e8b\u4ef6\u90fd\u9700\u8981\u5c06 c + 1\u3002\r\n                        if (c &lt; 2)\r\n                        {\r\n                            if (o == 1 &amp;&amp; t == 2) push(c + 1, j, 0, 0, 0);\r\n                            else if (o == n*m-2 &amp;&amp; t == 1) push(c + 1, j, 0, 0, n*m-1);\r\n                        }\r\n                    }\r\n                    else\r\n                    {\r\n                        if (dn &amp;&amp; rt)    \/\/ \u751f\u6210\u4e00\u5bf9\u63d2\u5934\r\n                        {\r\n                            FOR(o, 1, n*m-1) {\r\n                                push(c, j, 1, 2, o);\r\n                                push(c, j, 2, 1, o);\r\n                            }\r\n                        }\r\n                        if (c &lt; 2)    \/\/ \u751f\u6210\u4e00\u4e2a\u72ec\u7acb\u63d2\u5934\r\n                        {\r\n                            \/\/cout &lt;&lt; dn &lt;&lt; &quot; &quot; &lt;&lt; rt &lt;&lt; &quot;???&quot; &lt;&lt; &quot; &quot; &lt;&lt; onTheEdge(i, j) &lt;&lt; endl;\r\n\r\n                            if (dn)\r\n                            {\r\n                                push(c + 1, j, 1, 0, 0);\r\n                                push(c + 1, j, 2, 0, n*m-1);\r\n                            }\r\n                            if (rt)\r\n                            {\r\n                                push(c + 1, j, 0, 1, 0);\r\n                                push(c + 1, j, 0, 2, n*m-1);\r\n                            }\r\n                        }\r\n                    }\r\n                }\r\n        }\r\n        for (int c = 0; c &lt; 3; c++) H1&#x5B;c].roll();  \/\/ \u4e00\u884c\u7ed3\u675f\uff0c\u8c03\u6574\u8f6e\u5ed3\u7ebf\r\n    }\r\n\r\n    LL ans = 0; for (int ii = 0; ii &lt; H1&#x5B;2].sz; ii++) ans += H1&#x5B;2].key&#x5B;ii];\r\n    return ans % MOD;\r\n}\r\n\r\nint main() {\r\n\r\n#ifndef ONLINE_JUDGE\r\n    freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);\r\n    \/\/freopen(&quot;\/Users\/minakokojima\/Documents\/GitHub\/ACM-Training\/Workspace\/out.txt&quot;, &quot;w&quot;, stdout);\r\n#endif\r\n\r\n\r\n    MOD = 11192869;\r\n    init();\r\n    cout &lt;&lt; solve() &lt;&lt; endl;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/www.luogu.com.cn\/problem\/P1933 \u7ecf\u5178\u63d2\u5934 dp\uff0c\u4f46\u662f\u548c\u4f20\u7edf\u7684\u4e00\u6761\u8def\u5f84\u95ee\u9898\u76f8\u6bd4\uff0c\u6211\u4eec\u8fd8\u9700\u8981\u538b\u7f29\u8fdb\u8f6e\u5ed3\u7ebf\u4e0a\u4f4d\u7f6e\u7684\u6807\u53f7\uff0c\u8fd8\u8981\u7ef4\u62a4\u63d2\u5934\u7684\u65b9\u5411\uff08\u9012\u589e\u8fd8\u662f\u9012\u964d\uff09\uff0c\u7136\u540e\u5173\u952e\u662f\u63d2\u5934\u7684\u65b9\u5411\u4fe1\u606f\u5728 m=3 \u7684\u60c5\u51b5\u4e0b\uff0c\u662f\u53ef\u4ee5\u5ba2\u4e32\u8fde\u901a\u6027\u4fe1\u606f\u7684\uff0c\u8fd9\u6837\u53ef\u4ee5\u628a\u63d2\u5934\u63a7\u5236\u5728 int \u8303\u56f4\u91cc\uff08\u6070\u597d 32 \u4f4d\uff0c\u6ce8\u610f\u7528 uint\u3002\uff09 \/* Last Weapon is my own algorithms library for competitive programming, it is a fork from ACL with some alternative algorithms and additional features. Use it at your own risk. Repo: https:\/\/github.com\/lychees\/last-weapon Blog: https:\/\/www.shuizilong.com\/house *\/ #pragma comment(linker, &quot;\/STACK:36777216&quot;) #define LOCAL #include &lt;functional&gt; #include &lt;algorithm&gt; #include [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-3006","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Mu","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3006","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=3006"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3006\/revisions"}],"predecessor-version":[{"id":3007,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/3006\/revisions\/3007"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=3006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=3006"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=3006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}