经典插头 dp,但是和传统的一条路径问题相比,我们还需要压缩进轮廓线上位置的标号,还要维护插头的方向(递增还是递降),然后关键是插头的方向信息在 m=3 的情况下,是可以客串连通性信息的,这样可以把插头控制在 int 范围里(恰好 32 位,注意用 uint。)
/* 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, "/STACK:36777216") #define LOCAL #include <functional> #include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cstring> #include <climits> #include <cassert> #include <complex> #include <cstdio> #include <string> #include <vector> #include <bitset> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <list> #include <set> #include <map> using namespace std; #define REP(i, n) for (int i=0;i<n;++i) #define FOR(i, a, b) for (int i=a;i<b;++i) #define DWN(i, b, a) for (int i=b-1;i>=a;--i) #define REP_1(i, n) for (int i=1;i<=n;++i) #define FOR_1(i, a, b) for (int i=a;i<=b;++i) #define DWN_1(i, b, a) for (int i=b;i>=a;--i) #define ECH(it, A) for (__typeof((A).begin()) it=(A).begin(); it != (A).end(); ++it) #define rECH(it, A) for (__typeof((A).rbegin()) it=(A).rbegin(); it != (A).rend(); ++it) #define REP_S(i, str) for (char*i=str;*i;++i) #define REP_L(i, hd, suc) for (int i=hd;i;i=suc[i]) #define REP_G(i, u) REP_L(i,hd[u],suc) #define REP_SS(x, s) for (int x=s;x;x=(x-1)&s) #define DO(n) for ( int ____n = n; ____n-->0; ) #define ALL(A) A.begin(), A.end() #define LLA(A) A.rbegin(), A.rend() #define CPY(A, B) memcpy(A, B, sizeof(A)) #define INS(A, P, B) A.insert(A.begin() + P, B) #define ERS(A, P) A.erase(A.begin() + P) #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin()) #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin()) #define CTN(T, x) (T.find(x) != T.end()) #define SZ(A) int((A).size()) #define PB push_back #define MP(A, B) make_pair(A, B) #define PTT pair<T, T> #define Ts *this #define rTs return Ts #define fi first #define se second #define re real() #define im imag() #define Rush for(int ____T=RD(); ____T--;) #define Display(A, n, m) { \ REP(i, n){ \ REP(j, m-1) cout << A[i][j] << " "; \ cout << A[i][m-1] << endl; \ } \ } #define Display_1(A, n, m) { \ REP_1(i, n){ \ REP_1(j, m-1) cout << A[i][j] << " "; \ cout << A[i][m] << endl; \ } \ } typedef long long LL; typedef double DB; typedef unsigned uint; typedef unsigned long long uLL; typedef vector<int> VI; typedef vector<char> VC; typedef vector<string> VS; typedef vector<LL> VL; typedef vector<DB> VF; typedef set<int> SI; typedef set<string> SS; typedef map<int, int> MII; typedef map<string, int> MSI; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; template<class T> inline T& RD(T &); template<class T> inline void OT(const T &); inline LL RD(){LL x; return RD(x);} inline DB& RF(DB &); inline DB RF(){DB x; return RF(x);} inline char* RS(char *s); inline char& RC(char &c); inline char RC(); inline char& RC(char &c){scanf(" %c", &c); return c;} inline char RC(){char c; return RC(c);} template<class T0, class T1> inline T0& RD(T0 &x0, T1 &x1){RD(x0), RD(x1); return x0;} template<class T0, class T1, class T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2){RD(x0), RD(x1), RD(x2); return x0;} template<class T0, class T1, class T2, class T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3); return x0;} template<class T0, class T1, class T2, class T3, class T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0;} template<class T0, class T1, class T2, class T3, class T4, class T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0;} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6){RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0;} template<class T0, class T1> inline void OT(const T0 &x0, const T1 &x1){OT(x0), OT(x1);} template<class T0, class T1, class T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2){OT(x0), OT(x1), OT(x2);} template<class T0, class T1, class T2, class T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3){OT(x0), OT(x1), OT(x2), OT(x3);} template<class T0, class T1, class T2, class T3, class T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6){OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);} inline char& RC(char &a, char &b){RC(a), RC(b); return a;} inline char& RC(char &a, char &b, char &c){RC(a), RC(b), RC(c); return a;} inline char& RC(char &a, char &b, char &c, char &d){RC(a), RC(b), RC(c), RC(d); return a;} inline char& RC(char &a, char &b, char &c, char &d, char &e){RC(a), RC(b), RC(c), RC(d), RC(e); return a;} inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a;} inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g){RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a;} inline DB& RF(DB &a, DB &b){RF(a), RF(b); return a;} inline DB& RF(DB &a, DB &b, DB &c){RF(a), RF(b), RF(c); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d){RF(a), RF(b), RF(c), RF(d); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e){RF(a), RF(b), RF(c), RF(d), RF(e); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a;} inline DB& RF(DB &a, DB &b, DB &c, DB &d, DB &e, DB &f, DB &g){RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a;} inline void RS(char *s1, char *s2){RS(s1), RS(s2);} inline void RS(char *s1, char *s2, char *s3){RS(s1), RS(s2), RS(s3);} template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));} template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));} template<class T> inline void CLR(T &A){A.clear();} template<class T0, class T1> inline void RST(T0 &A0, T1 &A1){RST(A0), RST(A1);} template<class T0, class T1, class T2> inline void RST(T0 &A0, T1 &A1, T2 &A2){RST(A0), RST(A1), RST(A2);} template<class T0, class T1, class T2, class T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3){RST(A0), RST(A1), RST(A2), RST(A3);} template<class T0, class T1, class T2, class T3, class T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);} template<class T0, class T1> inline void FLC(T0 &A0, T1 &A1, int x){FLC(A0, x), FLC(A1, x);} template<class T0, class T1, class T2> inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x);} template<class T0, class T1, class T2, class T3> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);} template<class T0, class T1, class T2, class T3, class T4> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x){FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x), FLC(A6, x);} template<class T> inline void CLR(priority_queue<T> &Q){while (!Q.empty()) Q.pop();} template<class T> inline void CLR(stack<T> &S){while (!S.empty()) S.pop();} template<class T> inline void CLR(queue<T> &Q){while (!Q.empty()) Q.pop();} template<class T0, class T1> inline void CLR(T0 &A0, T1 &A1){CLR(A0), CLR(A1);} template<class T0, class T1, class T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2){CLR(A0), CLR(A1), CLR(A2);} template<class T0, class T1, class T2, class T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3){CLR(A0), CLR(A1), CLR(A2), CLR(A3);} template<class T0, class T1, class T2, class T3, class T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);} template<class T0, class T1, class T2, class T3, class T4, class T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);} template<class T0, class T1, class T2, class T3, class T4, class T5, class T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6){CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);} template<class T> inline void CLR(T &A, int n){REP(i, n) CLR(A[i]);} template<class T> inline bool EPT(T &a){return a.empty();} template<class T> inline T& SRT(T &A){sort(ALL(A)); return A;} template<class T, class C> inline T& SRT(T &A, C cmp){sort(ALL(A), cmp); return A;} template<class T> inline T& RVS(T &A){reverse(ALL(A)); return A;} template<class T> inline T& UNQQ(T &A){A.resize(unique(ALL(A))-A.begin());return A;} template<class T> inline T& UNQ(T &A){SRT(A);return UNQQ(A);} template<class T, class C> inline T& UNQ(T &A, C cmp){SRT(A, cmp);return UNQQ(A);} /** Constant List .. **/ //{ int MOD = int(1e9) + 7; const int INF = 0x3f3f3f3f; const LL INFF = 0x3f3f3f3f3f3f3f3fLL; const DB EPS = 1e-9; const DB OO = 1e20; const DB PI = acos(-1.0); //M_PI; const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, 1, -1}; /** Add On .. **/ //{ template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;} template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;} template <class T, class C> inline bool checkUpd(T& a, const T b, C c){return c(b,a) ? a = b, 1 : 0;} template<class T> inline T min(T a, T b, T c){return min(min(a, b), c);} template<class T> inline T max(T a, T b, T c){return max(max(a, b), c);} template<class T> inline T min(T a, T b, T c, T d){return min(min(a, b), min(c, d));} template<class T> inline T max(T a, T b, T c, T d){return max(max(a, b), max(c, d));} template<class T> inline T sqr(T a){return a*a;} template<class T> inline T cub(T a){return a*a*a;} template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;} template<class T> T abs(T x){return x>0?x:-x;} inline int sgn(DB x){return x < -EPS ? -1 : x > EPS;} inline int sgn(DB x, DB y){return sgn(x - y);} template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& a) { in >> a.fi >> a.se; return in; } template<typename T, size_t N> istream& operator>>(istream& in, array<T, N>& a) { REP(i, N) cin >> a[i]; return in; } template<typename T> istream& operator>>(istream& in, vector<T>& a) { REP(i, SZ(a)) in >> a[i]; return in; } template<typename T1, typename T2> ostream& operator<<(ostream& out, pair<T1, T2>& a) { out << a.fi << " " << a.se; return out; } template<typename T, size_t N> ostream& operator<<(ostream& out, array<T, N>& a) { REP(i, N-1) out << a[i] << " "; if (N) out << a.back(); return out; } template<typename T> ostream& operator<<(ostream& out, vector<T>& a) { REP(i, SZ(a)-1) out << a[i] << " "; if (SZ(a)) out << a.back(); return out; } /** I/O Accelerator Interface .. **/ //{ #define g (c=getchar()) #define d isdigit(g) #define p x=x*10+c-'0' #define n x=x*10+'0'-c #define pp l/=10,p #define nn l/=10,n template<class T> inline T& RD(T &x){ char c;while(g,c!='-'&&!isdigit(c)); if (c=='-'){x='0'-g;while(d)n;} else{x=c-'0';while(d)p;} return x; } inline DB& RF(DB &x){ char c;while(g,c!='-'&&c!='.'&&!isdigit(c)); if(c=='-')if(g=='.'){x=0;DB l=1;while(d)nn;x*=l;} else{x='0'-c;while(d)n;if(c=='.'){DB l=1;while(d)nn;x*=l;}} else if(c=='.'){x=0;DB l=1;while(d)pp;x*=l;} else{x=c-'0';while(d)p;if(c=='.'){DB l=1;while(d)pp;x*=l;}} return x; } #undef nn #undef pp #undef n #undef p #undef d #undef g inline char* RS(char *s){ scanf("%s", s); return s; } LL last_ans; int Case; template<class T> inline void OT(const T &x){ cout << x << endl; } namespace lastweapon {} namespace lastweapon { namespace NT{ inline LL gcd(LL a, LL b){return b?gcd(b,a%b):a;} inline LL lcm(LL a, LL b){return a*b/gcd(a,b);} inline void INC(int &a, int b){a += b; if (a >= MOD) a -= MOD;} inline int sum(int a, int b){a += b; if (a >= MOD) a -= MOD; return a;} inline void DEC(int &a, int b){a -= b; if (a < 0) a += MOD;} inline int dff(int a, int b){a -= b; if (a < 0) a += MOD; return a;} inline void MUL(int &a, int b){a = (LL)a * b % MOD;} inline int pdt(int x,int y) { int ret; __asm__ __volatile__ ("\tmull %%ebx\n\tdivl %%ecx\n":"=d"(ret):"a"(x),"b"(y),"c"(MOD)); return ret; } inline int gcd(int m, int n, int &x, int &y){ x = 1, y = 0; int xx = 0, yy = 1, q; while (1){ q = m / n, m %= n; if (!m){x = xx, y = yy; return n;} DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy)); q = n / m, n %= m; if (!n) return m; DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y)); } } inline int sum(int a, int b, int c){return sum(a, sum(b, c));} inline int sum(int a, int b, int c, int d){return sum(sum(a, b), sum(c, d));} inline int pdt(int a, int b, int c){return pdt(a, pdt(b, c));} inline int pdt(int a, int b, int c, int d){return pdt(pdt(a, b), pdt(c, d));} inline int pow(int a, LL b){ int c(1); while (b){ if (b&1) MUL(c, a); MUL(a, a), b >>= 1; } return c; } template<class T> inline T pow(T a, LL b){ T c(1); while (b){ if (b&1) c *= a; a *= a, b >>= 1; } return c; } template<class T> inline T pow(T a, int b){ return pow(a, (LL)b); } inline int _I(int b){ int a = MOD, x1 = 0, x2 = 1, q; while (1){ q = a / b, a %= b; if (!a) return x2; DEC(x1, pdt(q, x2)); q = b / a, b %= a; if (!b) return x1; DEC(x2, pdt(q, x1)); } } inline void DIV(int &a, int b){MUL(a, _I(b));} inline int qtt(int a, int b){return pdt(a, _I(b));} struct Int{ int val; operator int() const{return val;} Int(int _val = 0):val(_val){ val %= MOD; if (val < 0) val += MOD; } Int(LL _val):val(_val){ _val %= MOD; if (_val < 0) _val += MOD; val = _val; } Int& operator +=(const int& rhs){INC(val, rhs);rTs;} Int operator +(const int& rhs) const{return sum(val, rhs);} Int& operator -=(const int& rhs){DEC(val, rhs);rTs;} Int operator -(const int& rhs) const{return dff(val, rhs);} Int& operator *=(const int& rhs){MUL(val, rhs);rTs;} Int operator *(const int& rhs) const{return pdt(val, rhs);} Int& operator /=(const int& rhs){DIV(val, rhs);rTs;} Int operator /(const int& rhs) const{return qtt(val, rhs);} Int operator-()const{return MOD-*this;} }; } using namespace NT;//} } // namespace lastweapon #include <bits/stdc++.h> using namespace lastweapon; // 256 = 2^8 * 3 // 3*4 = 12 const int N = 50, M = 3; const int offset = 2, mask = (1 << offset) - 1, offset2 = 8, mask2 = (1 << offset2) - 1; int A[N][M], B[N*M]; int n, m, d; const int MaxSZ = 186796, Prime = 109973; struct hashTable { int head[Prime], next[MaxSZ], sz; uint state[MaxSZ]; int key[MaxSZ]; void clear() { sz = 0; memset(head, -1, sizeof(head)); } void push(uint s) { int x = s % Prime; for (int i = head[x]; ~i; i = next[i]) { if (state[i] == s) { key[i] += d; if (key[i] > MOD) key[i] -= MOD; return; } } state[sz] = s, key[sz] = d; next[sz] = head[x]; head[x] = sz++; } void roll() { for (int i = 0; i < sz; i++) { int s0 = state[i] & ((1 << (offset2*m)) - 1), s1 = state[i] ^ s0; state[i] = (s1 << offset) | s0; } } } H[2][3], *H0, *H1; int b[M + 1]; int b2[M]; int encode() { uint s = 0; for (int i = m; i >= 0; --i) { s <<= offset; s |= b[i]; } for (int i = m-1; i >= 0; --i) { s <<= offset2; s |= b2[i]; } return s; } void decode(uint s) { for (int i = 0; i < m; i++) { b2[i] = s & mask2; s >>= offset2; } for (int i = 0; i < m + 1; i++) { b[i] = s & mask; s >>= offset; } } bool onTheEdge(int x, int y) { return !x || !y || (x == n-1) || (y == m-1); } int i, j; void push(int c, int j, int dn, int rt, int o) { if (o < 0 || n*m <= o) return; if (!o && !onTheEdge(i, j)) return; if (A[i][j] != B[o]) return; b[j] = dn; b[j + 1] = rt; b2[j] = o; H1[c].push(encode()); } void init() { cin >> n >> m; swap(n, m); H0 = H[0], H1 = H[1]; for (int c = 0; c < 3; c++) H1[c].clear(); for (int j = 0; j < m; j++) for (int i = 0; i < n; i++) cin >> A[i][j]; REP(i, n*m) RD(B[i]); } Int solve() { if (n == 1 & m == 1) { // 特判 return A[0][0] = B[0]; } d = 1; H1[0].push(encode()); for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { swap(H0, H1); for (int c = 0; c < 3; c++) H1[c].clear(); // c 表示生成和消失事件发生的总次数,最多不超过 2 次 for (int c = 0; c < 3; c++) for (int ii = 0; ii < H0[c].sz; ii++) { decode(H0[c].state[ii]); d = H0[c].key[ii]; //cout << i << " " << j << " " << d << ": " << endl; //REP(i, m) cout << b2[i] << " "; cout << endl; //REP(i, m+1) cout << b[i] << " "; cout << endl; int lt = b[j], up = b[j + 1]; bool dn = i != n-1, rt = j != m-1; if (lt && up) { if (lt == up) // 在一条路径问题中,我们不能合并相同的插头。 { // Cannot deploy here... } else // 有可能参与合并的两者中有独立插头,但是也可以用同样的代码片段处理 { //for (int i = 0; i < m + 1; i++) if (b[i] == lt) b[i] = up; if ((b2[j-1] + 2 == b2[j] && lt == 1 && up == 2) || (b2[j] + 2 == b2[j-1] && up == 1 && lt == 2)) { push(c, j, 0, 0, (b2[j] + b2[j-1])/2); } } } else if (lt || up) { int t = lt | up; int o = lt ? b2[j-1] : b2[j]; if (dn) { if (t == 1) push(c, j, t, 0, o+1); else push(c, j, t, 0, o-1); } if (rt) { if (t == 1) push(c, j, 0, t, o+1); else push(c, j, 0, t, o-1); } // 一个插头消失的情况,如果是独立插头则意味着消失,如果是成对出现的插头则相当于生成了一个独立插头, // 无论哪一类事件都需要将 c + 1。 if (c < 2) { if (o == 1 && t == 2) push(c + 1, j, 0, 0, 0); else if (o == n*m-2 && t == 1) push(c + 1, j, 0, 0, n*m-1); } } else { if (dn && rt) // 生成一对插头 { FOR(o, 1, n*m-1) { push(c, j, 1, 2, o); push(c, j, 2, 1, o); } } if (c < 2) // 生成一个独立插头 { //cout << dn << " " << rt << "???" << " " << onTheEdge(i, j) << endl; if (dn) { push(c + 1, j, 1, 0, 0); push(c + 1, j, 2, 0, n*m-1); } if (rt) { push(c + 1, j, 0, 1, 0); push(c + 1, j, 0, 2, n*m-1); } } } } } for (int c = 0; c < 3; c++) H1[c].roll(); // 一行结束,调整轮廓线 } LL ans = 0; for (int ii = 0; ii < H1[2].sz; ii++) ans += H1[2].key[ii]; return ans % MOD; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout); #endif MOD = 11192869; init(); cout << solve() << endl; }