首页 > 代码库 > 【HDOJ】2371 Decode the Strings

【HDOJ】2371 Decode the Strings

2024-07-13 13:48:34   223人阅读

快速矩阵乘法。注意，原始字符串即为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 }


联系
我们