# 挑战程序竞赛系列（30）：3.4矩阵的幂

## POJ 3734: Blocks

• a：红色和绿色均为偶数时
• b：红色和绿色恰为一个奇数（注意互斥）
• c：红色和绿色均为奇数

a = 2a + b;
b = 2a + 2b + 2c;
c = 2c + b;

⎛⎝⎜aibici⎞⎠⎟=⎛⎝⎜220121022⎞⎠⎟i⎛⎝⎜a0b0c0⎞⎠⎟

\begin{pmatrix} a_i \\ b_i \\ c_i \\ \end{pmatrix} = \begin{pmatrix} 2 & 1 & 0 \\ 2 & 2 & 2 \\ 0 & 1 & 2 \\ \end{pmatrix}^i \begin{pmatrix} a_0 \\ b_0 \\ c_0 \\ \end{pmatrix}

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/3734.txt";

static final int MOD = 10007;
void solve() {
int T = ni();
for (int t = 0; t < T; ++t){
int n = ni();
int[][] a = {{2, 1, 0},{2, 2, 2},{0, 1, 2}};
Mat A = new Mat(a);
A = A.pow(A, n, MOD);
out.println(A.mat[0][0]);
}
}

class Mat{
int[][] mat;
int n;
int m;

public Mat(int[][] arra){
this.mat = arra;
this.n = arra.length;
this.m = arra[0].length;
}

public Mat mul(Mat A, Mat B, int MOD){
int[][] a = A.mat;
int[][] b = B.mat;
int[][] res = new int[A.n][B.m];
for (int i = 0; i < A.n; ++i){
for (int j = 0; j < B.m; ++j){
for (int ll = 0; ll < A.m; ++ll){
res[i][j] = (res[i][j] + a[i][ll] * b[ll][j]) % MOD;
}
}
}
return new Mat(res);
}

public Mat pow(Mat A, int n, int MOD){
int[][] one = new int[A.n][A.m];
for (int i = 0; i < A.n; ++i) one[i][i] = 1;
Mat res = new Mat(one);

while (n > 0){
if (n % 2 != 0){
res = mul(res, A, MOD);
}
n >>= 1;
A = mul(A, A, MOD);
}
return res;
}
}

void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}

public static void main(String[] args) throws Exception {
new Main().run();
}

private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;

if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}

private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}

private double nd() {
return Double.parseDouble(ns());
}

private char nc() {
return (char) skip();
}

private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}

private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}

private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}

an+1=an+bn+cn+dxn+dyn

a_{n + 1} = a_n + b_n + c_n + dx_n + dy_n

bn+1=an

b_{n + 1} = a_n

cn+1=an+e

c_{n + 1} = a_n + e

dxn+1=an+dyn

dx_{n + 1} = a_n + dy_n

dyn+1=an+dxn

dy_{n + 1} = a_n + dx_n

en+1=cn

e_{n + 1} = c_n

dn+1=2an+dn

d_{n + 1} = 2a_n + d_n

A=⎛⎝⎜⎜⎜⎜⎜⎜1112010000100011001000100⎞⎠⎟⎟⎟⎟⎟⎟

A = \begin{pmatrix} 1 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1\\ 2 & 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 0\\ \end{pmatrix}

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/3420.txt";

void solve() {
while (true){
int N = ni();
int M = ni();
if (N + M == 0) break;
int[][] a = {{1,1,1,1,0},{1,0,0,0,0},{1,0,0,0,1},{2,0,0,1,0},{0,0,1,0,0}};
Mat A = new Mat(a);
A = A.pow(A, N, M);
out.println(A.mat[0][0]);
}

}

class Mat{
int[][] mat;
int n;
int m;

public Mat(int[][] mat){
this.mat = mat;
this.n = mat.length;
this.m = mat[0].length;
}

public Mat mul(Mat A, Mat B, int MOD){
int[][] a = A.mat;
int[][] b = B.mat;
int[][] res = new int[A.n][B.m];
for (int i = 0; i < A.n; ++i){
for (int j = 0; j < B.m; ++j){
for (int ll = 0; ll < A.m; ++ll){
res[i][j] = (res[i][j] + a[i][ll] * b[ll][j]) % MOD;
}
}
}
return new Mat(res);
}

public Mat pow(Mat A, int n, int MOD){
int[][] one = new int[A.n][A.n];
for (int i = 0; i < A.n; ++i) one[i][i] = 1;
Mat res = new Mat(one);
while (n > 0){
if ((n & 1) != 0){
res = mul(res, A, MOD);
}
n >>= 1;
A = mul(A, A, MOD);
}
return res;
}
}

void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}

public static void main(String[] args) throws Exception {
new Main().run();
}

private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;

if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}

private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}

private double nd() {
return Double.parseDouble(ns());
}

private char nc() {
return (char) skip();
}

private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}

private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}

private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}

## POJ 3735: Training Little cats

3 1 6
g 1
g 2
g 2
s 1 2
g 3
e 2
0 0 0

g 1 : a = a + 1

a   1 0 0 1   0
b = 0 1 0 0 * 0
c   0 0 1 0   0
1   0 0 0 1   1

a   0 1 0 1   0
b = 1 0 0 0 * 0
c   0 0 1 0   0
1   0 0 0 1   1

e 2

a   0 1 0 1   0
b = 1 0 0 0 * 0
c   0 0 0 0   0
1   0 0 0 1   1

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Stack;

public class Main{
InputStream is;
PrintWriter out;
String INPUT = "./data/judge/201707/3735.txt";

int N;
void solve() {
while (true){
N = ni();
int M = ni();
int K = ni();
if (N + M + K == 0) break;
Stack<Mat> stack = new Stack<Mat>();
for (int i = 0; i < K; ++i){
char c = nc();
if (c == 'g'){
stack.push(createMat(c, ni() - 1, 0));
}
else if (c == 's'){
stack.push(createMat(c, ni() - 1, ni() - 1));
}
else{
stack.push(createMat(c, ni() - 1, 0));
}
}

long[][] one = new long[N + 1][N + 1];
for (int i = 0; i < N + 1; ++i) one[i][i] = 1;
Mat A = new Mat(one);
while (!stack.isEmpty()){
A = mul(A, stack.pop());
}
A = pow(A, M);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < N; ++i){
sb.append(" " + A.mat[i][N]);
}
out.println(sb.deleteCharAt(0).toString());
}
}

public Mat createMat(char command, int i, int j){
long[][] one = new long[N + 1][N + 1];
for (int l = 0; l < one.length; ++l) one[l][l] = 1;
switch (command) {
case 'g':
one[i][N] = 1;
break;
case 's':
one[i][i] = 0;
one[j][j] = 0;
one[i][j] = 1;
one[j][i] = 1;
break;
case 'e':
one[i][i] = 0;
break;
default:
break;
}
return new Mat(one);
}

class Mat{
long[][] mat;
int n;
int m;
public Mat(long[][] mat){
this.mat = mat;
this.n = mat.length;
this.m = mat[0].length;
}
}

public Mat mul(Mat A, Mat B){
long[][] a = A.mat;
long[][] b = B.mat;
long[][] res = new long[A.n][B.m];
for (int i = 0; i < A.n; ++i){
for (int ll = 0; ll < A.m; ++ll){
if (a[i][ll] != 0){
for (int j = 0; j < B.m; ++j){
res[i][j] += a[i][ll] * b[ll][j];
}
}
}
}
return new Mat(res);
}

public Mat pow(Mat A, int n){
long[][] one = new long[A.n][A.n];
for (int i = 0; i < A.n; ++i) one[i][i] = 1;
Mat res = new Mat(one);
while (n > 0){
if ((n & 1) != 0){
res = mul(res, A);
}
n >>= 1;
A = mul(A, A);
}
return res;
}

void run() throws Exception {
is = oj ? System.in : new FileInputStream(new File(INPUT));
out = new PrintWriter(System.out);

long s = System.currentTimeMillis();
solve();
out.flush();
tr(System.currentTimeMillis() - s + "ms");
}

public static void main(String[] args) throws Exception {
new Main().run();
}

private byte[] inbuf = new byte[1024];
public int lenbuf = 0, ptrbuf = 0;

if (lenbuf == -1)
throw new InputMismatchException();
if (ptrbuf >= lenbuf) {
ptrbuf = 0;
try {
} catch (IOException e) {
throw new InputMismatchException();
}
if (lenbuf <= 0)
return -1;
}
return inbuf[ptrbuf++];
}

private boolean isSpaceChar(int c) {
return !(c >= 33 && c <= 126);
}

private int skip() {
int b;
while ((b = readByte()) != -1 && isSpaceChar(b))
;
return b;
}

private double nd() {
return Double.parseDouble(ns());
}

private char nc() {
return (char) skip();
}

private String ns() {
int b = skip();
StringBuilder sb = new StringBuilder();
while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != '
// ')
sb.appendCodePoint(b);
}
return sb.toString();
}

private char[] ns(int n) {
char[] buf = new char[n];
int b = skip(), p = 0;
while (p < n && !(isSpaceChar(b))) {
buf[p++] = (char) b;
}
return n == p ? buf : Arrays.copyOf(buf, p);
}

private char[][] nm(int n, int m) {
char[][] map = new char[n][];
for (int i = 0; i < n; i++)
map[i] = ns(m);
return map;
}

private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}

private int ni() {
int num = 0, b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private long nl() {
long num = 0;
int b;
boolean minus = false;
while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
;
if (b == '-') {
minus = true;
}

while (true) {
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
}

private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

private void tr(Object... o) {
if (!oj)
System.out.println(Arrays.deepToString(o));
}
}

0 条评论

• ### 挑战程序竞赛系列（26）：3.5二分图匹配（1）

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.n...

• ### K-th Smallest Prime Fraction

思路1： 一种聪明的做法，如果A = [1, 7, 23, 29, 47]，那么有：

• ### 挑战程序竞赛系列（81）：4.3 LCA（1）

挑战程序竞赛系列（81）：4.3 LCA（1） 传送门：POJ 2763: Housewife Wind 题意： XX村里有n个小屋，小屋之间有双向可达的道...

• ### 2019 CCPC 重现赛 1006 基环树

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 ...

• ### Python3 基础学习之数值进制转换

这个函数在上篇里表示强转，并没有输入n这个参数。当n不输入的时候默认是n=10。

• ### 剑指OFFER之重建二叉树（九度OJ1385）

题目描述： 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

• ### 【优秀题解】题号：1179

关注我们 今天给大家带来一份优秀题解（题号：1179）： ? 解题思路 1 设共n=7个站，第一站上车a=5人，最后一站下车32人，设第二站上车人数为x（其...

• ### 每日算法系列【EOJ 3031】二进制倒置

给定一个整数 、将 的 334 位二进制表示形式（不包括开头可能的值为 0 的位， 表示为 1 位 0）前后倒置，输出倒置后的二进制数对应的整数。

• ### zoj 2521 LED Display

题意：开灯，每个数字都由好几个灯组成，其中一些数字灭掉某些灯可以成为另一个数字，如0灭掉3个灯可以变成7，         现给你一组数字，如何组合可以形成最少...