首页 > 代码库 > 【HDOJ】2371 Decode the Strings
【HDOJ】2371 Decode the Strings
快速矩阵乘法。注意,原始字符串即为decode后的字符串。题目是要找到原始串。
1 #include <cstdio> 2 #include <cstring> 3 4 #define MAXN 85 5 6 typedef struct { 7 char m[MAXN][MAXN]; 8 } mat_st; 9 10 int n, m;11 char buf[MAXN];12 mat_st e;13 14 mat_st mat_mult(mat_st a, mat_st b) {15 int i, j, k;16 mat_st c;17 memset(c.m, 0, sizeof(c.m));18 19 for (i=1; i<=n; ++i) {20 for (j=1; j<=n; ++j) {21 for (k=1; k<=n; ++k)22 c.m[i][j] += a.m[i][k] & b.m[k][j];23 }24 }25 return c;26 }27 28 mat_st mat_power(mat_st a, int r) {29 mat_st ret;30 31 memset(ret.m, 0, sizeof(ret.m));32 for (int i=1; i<=n; ++i)33 ret.m[i][i] = 1;34 35 while (r) {36 if (r & 1)37 ret = mat_mult(ret, a);38 a = mat_mult(a, a);39 r >>= 1;40 }41 return ret;42 }43 44 int main() {45 mat_st org;46 int i, j;47 48 while (scanf("%d %d",&n,&m)!=EOF && n) {49 memset(org.m, 0, sizeof(org.m));50 for (i=1; i<=n; ++i) {51 scanf("%d", &j);52 org.m[i][j] = 1;53 }54 getchar();55 gets(buf+1);56 mat_st ans = mat_power(org, m);57 for (i=1; i<=n; ++i) {58 for (j=1; j<=n; ++j) {59 if (ans.m[j][i]) {60 printf("%c", buf[j]);61 break;62 }63 }64 }65 printf("\n");66 }67 68 return 0;69 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。