結果
問題 | No.793 うし数列 2 |
ユーザー |
|
提出日時 | 2019-04-27 23:41:17 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 142 ms / 2,000 ms |
コード長 | 2,068 bytes |
コンパイル時間 | 3,740 ms |
コンパイル使用メモリ | 78,092 KB |
実行使用メモリ | 41,724 KB |
最終ジャッジ日時 | 2024-11-30 02:08:35 |
合計ジャッジ時間 | 7,765 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
import java.io.*;import java.util.Scanner;public class Main_yukicoder793 {private static Scanner sc;private static Printer pr;private static void solve() {final int MOD = 1_000_000_007;long n = sc.nextLong();int[] a = {10, 1};int[][] x = {{10, 0},{1, 0},};long ans = f(x, a, n, MOD);int[] b = {3, 0, 1};int[][] xx = {{10, 0, 3},{0, 10, 3},{0, 0, 1},};ans += f(xx, b, n, MOD);ans %= MOD;pr.println(ans);}private static long f(int[][] x, int[] a, long n, int MOD) {long loop = n;while (loop > 0) {if (loop % 2 == 1) {a = Matrix.mul(x, a, MOD);}x = Matrix.mul(x, x, MOD);loop /= 2;}return a[1];}static class Matrix {static int[] mul(int[][] a, int[] x, int MOD) {int m = a.length;int n = a[0].length;if (n != x.length) {throw new IllegalArgumentException();}int[] y = new int[m];for (int i = 0; i < m; i++) {long tmp = 0;for (int j = 0; j < n; j++) {tmp += (long)a[i][j] * x[j];tmp %= MOD;}y[i] = (int)tmp;}return y;}static int[][] mul(int[][] a, int[][] a2, int MOD) {int m = a.length;int n = a2[0].length;int l = a[0].length;if (l != a2.length) {throw new IllegalArgumentException();}int[][] y = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {long tmp = 0;for (int k = 0; k < l; k++) {tmp += (long)a[i][k] * a2[k][j];tmp %= MOD;}y[i][j] = (int)tmp;}}return y;}static int[][] getI(int n) {int[][] mat = new int[n][];for (int i = 0; i < n; i++) {mat[i] = new int[n];mat[i][i] = 1;}return mat;}}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}static class Printer extends PrintWriter {Printer(OutputStream out) {super(out);}}}