首页 > 代码库 > BZOJ1297: [SCOI2009]迷路 矩阵乘法
BZOJ1297: [SCOI2009]迷路 矩阵乘法
如果边权都是1,那么直接对当前的邻接矩阵进行T次自乘,答案就是D[1][n]了。
证明:当进行1次自乘时,\(D^{1}_{i,j}\)显然代表从i到j的长度为1的路径条数。假设\(D^{k}_{i,j}\)表示从i到j长度为k的路径条数,那么\(D^{k + 1} = D^{k} \times D\)的\(D^{k + 1}_{i, j} = \sum_{k = 1}^{n}(D^{k}_{i,k} \times D^{1}_{k,j})\),易知假设成立。得证。
那么对于这道题有什么帮助呢?发现路径长度最长为9,我们可以把每个点拆成至多9个点连成一个链,对于边权为t的边{i, j}连上{I, J - t + 1},这样每条边的权值都是1,可以做了。
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。