还有一类数学题目，那就是置换，其本质就是一一映射，具体参看训练指南144页。可能正如同书中所说的，我们一般处理置换时常常将它们写成循环乘积的形式，这样便于理解和计算。可是如果当我们进行的置换的次数非常多，那么循环乘积可能就会变得比较繁杂，即使任然可以计算，但是在时间上也是不允许的。那么有没有什么方法可以加速置换运算呢？那就是矩阵。首先想这样一个事实，任何置换都可以写成矩阵的形式，如图所示：
上图利用矩阵将{1；2；3；4}置换成了{3；1；2；4}，的确是这样的，只要变换第一个矩阵，那么乘上第二个矩阵后的结果就会随着改变，如果我们精心构造，那么有一定会出现我们想要的结果。到这里，方法就很明显了，类是于矩阵求解递推式，我们将第一个矩阵开n次幂，代表数据被置换了n次，然后乘上初始矩阵（原始数据），记为A^n * B = C，最终得到的矩阵里就会出现原始数据被置换了n次之后的数据，那就是我们想要的答案，时间复杂度上依然使用快速幂算法优化，至于如何构造矩阵，这是由题目给出的置换矩阵决定的。下面我们就具体看一道例题，来掌握矩阵求解置换的思想，HDOJ：2371，时空转移（
点击打开链接
），题目如下：
Decode the Strings
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 768 Accepted Submission(s): 233
Let x
1
,x
2
,…,x
n
be the sequence of characters of the string to be encoded.
1. Choose an integer m and n pairwise distinct numbers p
1
,p
2
,…,p
n
from the set {1, 2, …, n} (a permutation of the numbers 1 to n).
2. Repeat the following step m times.
3. For 1 ≤ i ≤ n set y
i
to x
pi
, and then for 1 ≤ i ≤ n replace x
i
by y
i
.
For example, when we want to encode the string “hello”, and we choose the value m = 3 and the permutation 2, 3, 1, 5, 4, the data would be encoded in 3 steps: “hello” -> “elhol” -> “lhelo” -> “helol”.
Bruce gives you the encoded strings, and the numbers m and p
1
, …, p
n
used to encode these strings. He claims that because he used huge numbers m for encoding, you will need a lot of time to decode the strings. Can you disprove this claim by quickly decoding the strings?
9
). The following line consists of n pairwise different numbers p
1
,…,p
n
(1 ≤ p
i
≤ n). The third line of each test case consists of exactly n characters, and represent the encoded string. The last test case is followed by a line containing two zeros.
5 3 2 3 1 5 4 helol 16 804289384 13 10 2 7 8 1 16 12 15 6 5 14 3 4 11 9 scssoet tcaede n 8 12 5 3 4 2 1 8 6 7 encoded? 0 0
hello second test case encoded?
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 100;
const int MOD = 1e5;
struct Mat
{
int n, m;
int mat[MAXN][MAXN];
Mat()
{
memset(mat, 0, sizeof(mat));
n = m = MAXN;
};
void init() // 初始化为单位矩阵
{
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
mat[i][j] = (i==j);
}
Mat operator * (Mat b) // 重载乘法
{
Mat c;
c = Mat();
c.n = n;
c.m = b.m;
for(int i=1; i<=n; ++i) // 注意这里从1开始
for(int j=1; j<=b.m; ++j)
{
//if(mat[j][i] <= 0) continue; // 剪枝
for(int k=1; k<=m; ++k)
{
//if(b.mat[i][k] <= 0) continue; // 剪枝
c.mat[i][j] += (mat[i][k]*b.mat[k][j]); //% MOD;
//c.mat[i][j] %= MOD;
}
}
return c;
}
Mat QuickPow(Mat a, int k) // 快速幂
{
Mat c;
c.n = a.n;
c.m = a.n;
c.init(); // 初始化为单位矩阵
while(k)
{
if(k & 1)
c = c*a;
a = a*a;
k >>= 1;
}
return c;
}
Mat transpose() // 求矩阵的转置
{
Mat c;
c.n = m;
c.m = n;
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j)
c.mat[j][i] = mat[i][j];
return c;
}
};
int main()
{//freopen("sample.txt", "r", stdin);
int n, m;
char ch[100];
while(~scanf("%d%d", &n, &m) && (n||m))
{
Mat ini, base, ans;
base.n = base.m = n;
for(int i=1; i<=n; ++i) // 初始矩阵
base.mat[i][1] = i;
ini.n = ini.m = n;
for(int i=1; i<=n; ++i) // 构造矩阵
{
int a;
scanf("%d", &a);
ini.mat[i][a] = 1;
}
getchar();
gets(ch+1);
ini = ini.transpose(); // 取转置
ini = ini.QuickPow(ini, m); // 求幂次
ans = ini * base;
for(int i=1; i<=n; ++i)
printf("%c", ch[ans.mat[i][1]]); // 答案为第一列
puts("");
}
return 0;
}
需要说明的是，在这道题目中，虽然中间结果不会很大，但是我为了保险，在最开始的时候还是取了模，但结果是超时，去掉模运算后就过了，说明模还是比较费时的，需慎用。其它类似的题目还有，VOJ：1049。