题目描述
Description
Facer’s pet cat just gave birth to a brood of little cats. Having considered the health of those lovely cats, Facer decides to make the cats to do some exercises. Facer has well designed a set of moves for his cats. He is now asking you to supervise the cats to do his exercises. Facer’s great exercise for cats contains three different moves:
g i : Let the ith cat take a peanut.
e i : Let the ith cat eat all peanuts it have.
s i j : Let the ith cat and jth cat exchange their peanuts.
All the cats perform a sequence of these moves and must repeat it m times! Poor cats! Only Facer can come up with such embarrassing idea.
You have to determine the final number of peanuts each cat have, and directly give them the exact quantity in order to save them.
Input
The input file consists of multiple test cases, ending with three zeroes “0 0 0”. For each test case, three integers n, m and k are given firstly, where n is the number of cats and k is the length of the move sequence. The following k lines describe the sequence.
(m≤1,000,000,000, n≤100, k≤100)
Output
For each test case, output n numbers in a single line, representing the numbers of peanuts the cats have.
Sample Input
3 1 6
g 1
g 2
g 2
s 1 2
g 3
e 2
0 0 0
Sample Output
2 0 1
题目链接
http://poj.org/problem?id=3735
解题思路
题目大意就是有N只猫，K次操作（得花生、吃花生、交换花生），重复M次。问最后每只猫各有多少花生剩余。
这道题目的巧妙之处就是构造单位矩阵，从而实现三种操作。之后便能用矩阵快速幂来求解了。
TLE代码
1 |
|
SB题，害得我T了N发。原因就在于进行矩阵乘法的时候，由于乘法的次数m次较多，而矩阵又过于稀疏，导致做了大量的无意义的计算：1
2
3
4
5
6
7
8
9
10
11
12
13
14Matrix operator *(const Matrix &b)
{
Matrix t(n, m);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
t.a[i][j] = 0;
for (int k = 0; k <= m; k++)
t.a[i][j] += a[i][k] * b.a[k][j];
}
}
return t;
}
将这段代码改成这样就好了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15Matrix operator *(const Matrix &b)
{
Matrix t(n, m);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
t.a[i][j] = 0;
for (int k = 0; k <= m; k++)
if (a[i][k] && b.a[k][j])
t.a[i][j] += a[i][k] * b.a[k][j];
}
}
return t;
}
AC代码
648K/1016MS/C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
typedef long long ll;
using namespace std;
const int N = 105;
struct Matrix
{
int n, m;
ll a[N][N];
Matrix(int n = N, int m = N)
{
this->n = n;
this->m = m;
memset(a, 0, sizeof(a));
}
Matrix unit()
{
Matrix t(n, n);
for (int i = 0; i <= n; i++)
t.a[i][i] = 1;
return t;
}
Matrix operator *(const Matrix &b)
{
Matrix t(n, m);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= m; j++)
{
t.a[i][j] = 0;
for (int k = 0; k <= m; k++)
if (a[i][k] && b.a[k][j])
t.a[i][j] += a[i][k] * b.a[k][j];
}
}
return t;
}
friend Matrix quickpow(Matrix &a, ll b)
{
if (b < 0) return a.unit();
Matrix ret = a.unit();
for (; b; b >>= 1, a = a * a)
{
if (b & 1)
ret = ret * a;
}
return ret;
}
};
int main()
{
int n, k;
ll m;
while (~scanf("%d%I64d%d", &n, &m, &k) && n + m + k != 0)
{
char c[5];
int x, y;
Matrix A(n, n);
Matrix B(n, 1);
A = A.unit();
B.a[n][0] = 1;
for (int i = 1; i <= k; i++)
{
scanf("%s", c);
if (c[0] == 'g')
{
scanf("%d", &x);
A.a[x - 1][n]++;
}
else if (c[0] == 'e')
{
scanf("%d", &x);
for (int j = 0; j <= n; j++)
A.a[x - 1][j] = 0;
}
else if (c[0] == 's')
{
scanf("%d%d", &x, &y);
for (int j = 0; j <= n; j++)
swap(A.a[x - 1][j], A.a[y - 1][j]);
}
}
A = quickpow(A, m);
for (int i = 0; i < n; i++)
{
if (i) printf(" ");
printf("%I64d", A.a[i][n]);
}
printf("\n");
}
return 0;
}