Codeforces - 185A. Plant

Question

题目

解析

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

  static class Matrix {
    public int row;
    public int col;
    public long[][] m;

    public Matrix(int row, int col) {
      this.row = row;
      this.col = col;
      m = new long[row][col];
    }
  }

  static final int mod = 1000000007;

  static Matrix mul(Matrix a, Matrix b) {
    Matrix c = new Matrix(a.row, b.col); //注意这里

    for (int i = 0; i < a.row; i++) {
      for (int j = 0; j < b.col; j++) {
        for (int k = 0; k < a.col; k++)
          c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
      }
    }
    return c;
  }

  static Matrix pow(Matrix a, long k) {
    Matrix res = new Matrix(a.row, a.col); // 方阵
    for (int i = 0; i < a.row; i++)
      res.m[i][i] = 1;
    while (k > 0) {
      if ((k & 1) != 0)
        res = mul(res, a);
      a = mul(a, a);
      k >>= 1;
    }
    return res;
  }

  public static void main(String[] args) {
    Scanner cin = new Scanner(new BufferedInputStream(System.in));

    long n = cin.nextLong();

    Matrix a = new Matrix(2, 2);
    a.m[0][0] = a.m[1][1] = 3;
    a.m[0][1] = a.m[1][0] = 1;

    Matrix res = pow(a, n);

    System.out.println(res.m[0][0] % mod);
  }
}

题目链接

http://codeforces.com/problemset/problem/185/A