BZOJ1297: [SCOI2009]迷路 矩阵乘法

  1 //{HEADS
  2 #define FILE_IN_OUT
  3 #define debug
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <ctime>
  9 #include <algorithm>
 10 #include <iostream>
 11 #include <fstream>
 12 #include <vector>
 13 #include <stack>
 14 #include <queue>
 15 #include <deque>
 16 #include <map>
 17 #include <set>
 18 #include <bitset>
 19 #include <complex>
 20 #include <string>
 21 #define REP(i, j) for (int i = 1; i <= j; ++i)
 22 #define REPI(i, j, k) for (int i = j; i <= k; ++i)
 23 #define REPD(i, j) for (int i = j; 0 < i; --i)
 24 #define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i)
 25 #define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i)
 26 #define CLR(s) memset(s, 0, sizeof s)
 27 #define SET(s, v) memset(s, v, sizeof s)
 28 #define mp make_pair
 29 #define pb push_back
 30 #define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl
 31 #define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endl
 32 using namespace std;
 33 #ifdef debug
 34 #ifndef ONLINE_JUDGE
 35     const int OUT_PUT_DEBUG_INFO = 1;
 36 #endif
 37 #endif
 38 #ifdef ONLINE_JUDGE
 39     const int OUT_PUT_DEBUG_INFO = 0;
 40 #endif
 41 #define DG if(OUT_PUT_DEBUG_INFO)
 42 void FILE_INIT(string FILE_NAME) {
 43 #ifdef FILE_IN_OUT
 44 #ifndef ONLINE_JUDGE 
 45     freopen((FILE_NAME + ".in").c_str(), "r", stdin);
 46     freopen((FILE_NAME + ".out").c_str(), "w", stdout);
 47 
 48 #endif
 49 #endif
 50 }
 51 typedef long long LL;
 52 typedef double DB;
 53 typedef pair<int, int> i_pair;
 54 const int INF = 0x3f3f3f3f;
 55 //}
 56 /*{ 获取字符*/
 57 char gchar() {
 58     char ret = getchar();
 59     for(; ret == ‘\n‘ || ret == ‘\r‘ || ret == ‘ ‘; ret = getchar());
 60     return ret;
 61 }
 62 /*}*/
 63 const int maxn = 10 * 10;
 64 const int mod = 2009;
 65 int n, T, S;
 66 
 67 struct Matrix {
 68     int d[maxn][maxn];
 69     Matrix(int t = 0) {
 70         if(t == 1) {
 71             REP(i, S) {
 72                 d[i][i] = 1;
 73             }
 74         } else {
 75             CLR(d);
 76         }
 77     }
 78 }G, ans;
 79 
 80 Matrix operator * (const Matrix & a, const Matrix &b) {
 81     Matrix ret;
 82     REP(i, S) {
 83         REP(j, S) {
 84             REP(k, S) {
 85                 ret.d[i][j] = (ret.d[i][j] + a.d[i][k] * b.d[k][j] % mod) % mod;
 86             }
 87         }
 88     }
 89     return ret;
 90 }
 91 
 92 int main() {
 93     FILE_INIT("BZOJ1297");
 94 
 95     scanf("%d %d", &n, &T);
 96     S = n * 9;
 97     REP(i, n) {
 98         REP(j, n) {
 99             int t = gchar() - ‘0‘;
100             if(t != 0) {
101                 G.d[i * 9][j * 9 - t + 1] = 1;
102                 for(int k = j * 9 - t + 2; k <= j * 9; ++k) {
103                     G.d[k - 1][k] = 1;
104                 }
105             }
106         }
107     }
108     /*
109     REP(i, S) {
110         REP(j, S) {
111             printf("%d ", G.d[i][j]);
112         }
113         puts("");
114     }
115     */
116     for(ans = 1; T; T >>= 1, G = G * G) {
117         if(T & 1) {
118             ans = ans * G;
119         }
120     }
121     printf("%d\n", ans.d[9][S]);
122 
123 
124     return 0;
125 }