結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:14:42 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 59 ms / 2,000 ms |
コード長 | 8,723 bytes |
コンパイル時間 | 2,425 ms |
コンパイル使用メモリ | 79,536 KB |
実行使用メモリ | 52,376 KB |
最終ジャッジ日時 | 2024-12-17 15:49:27 |
合計ジャッジ時間 | 5,412 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
import java.io.*;import java.math.BigDecimal;import java.util.*;@SuppressWarnings("unused")public class Main {FastScanner in;PrintWriter out;final static int MOD = (int)1e9+7;void solve(){long N = in.nextLong();long m = 166666668;long[] a = {0, 0, 0, 0, 0, 1};long[][] b = {{0, 1, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0},{0, 0, 0, 1, 0, 0},{0, 0, 0, 0, 1, 0},{0, 0, 0, 0, 0, 1},{m, m, m, m, m, m}};a = multiplyMatrix(powMatrix(b, N), a);out.println(a[5]);}public long[][] powMatrix(long[][] a, long n){if(n == 0){int size = a.length;long[][] e = new long[size][size];for(int i = 0; i < size; i++){for(int j = 0; j < size; j++){if(i == j)e[i][j] = 1;elsee[i][j] = 0;}}return e;}if(n % 2 == 0){return powMatrix(multiplyMatrix(a, a), n / 2);}else{return multiplyMatrix(a, powMatrix(multiplyMatrix(a, a), (n - 1) / 2));}}public long[] multiplyMatrix(long[][] a, long[] x){int size = a.length;long[] y = new long[size];for(int i = 0; i < size; i++){for(int j = 0; j < size; j++){y[i] = ((y[i] + (a[i][j] * x[j]) % MOD) % MOD);}}return y;}public long[][] multiplyMatrix(long[][] a, long[][] b){int size = a.length;long[][] c = new long[size][size];for(int i = 0; i < size; i++){for(int j = 0; j < size; j++){for(int k = 0; k < size; k++){c[i][j] = ((c[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD);}}}return c;}public void printMatrix(long[] a){int size = a.length;for(int j = 0; j < size; j++){System.out.println(a[j]);}}public void printMatrix(long[][] a){int size = a.length;for(int i = 0; i < size; i++){for(int j = 0; j < size; j++){System.out.print(a[i][j]);if(j == size-1)System.out.println();elseSystem.out.print(" ");}}}public static void main(String[] args) {new Main().m();}private void m() {in = new FastScanner(System.in);out = new PrintWriter(System.out);/*try {String path = "input.txt";out = new PrintWriter(new BufferedWriter(new FileWriter(new File(path))));}catch (IOException e){e.printStackTrace();}*/solve();out.flush();in.close();out.close();}static class FastScanner {private Reader input;public FastScanner() {this(System.in);}public FastScanner(InputStream stream) {this.input = new BufferedReader(new InputStreamReader(stream));}public void close() {try {this.input.close();} catch (IOException e) {e.printStackTrace();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();return (int) nl;}public long nextLong() {try {int sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}long ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) return ret * sign;ret *= 10;ret += b - '0';}} catch (IOException e) {e.printStackTrace();return -1;}}public double nextDouble() {try {double sign = 1;int b = input.read();while ((b < '0' || '9' < b) && b != '-' && b != '+') {b = input.read();}if (b == '-') {sign = -1;b = input.read();} else if (b == '+') {b = input.read();}double ret = b - '0';while (true) {b = input.read();if (b < '0' || '9' < b) break;ret *= 10;ret += b - '0';}if (b != '.') return sign * ret;double div = 1;b = input.read();while ('0' <= b && b <= '9') {ret *= 10;ret += b - '0';div *= 10;b = input.read();}return sign * ret / div;} catch (IOException e) {e.printStackTrace();return Double.NaN;}}public char nextChar() {try {int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}return (char) b;} catch (IOException e) {e.printStackTrace();return 0;}}public String nextStr() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (Character.isWhitespace(b)) {b = input.read();}while (b != -1 && !Character.isWhitespace(b)) {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public String nextLine() {try {StringBuilder sb = new StringBuilder();int b = input.read();while (b != -1 && b != '\n') {sb.append((char) b);b = input.read();}return sb.toString();} catch (IOException e) {e.printStackTrace();return "";}}public int[] nextIntArray(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt();}return res;}public int[] nextIntArrayDec(int n) {int[] res = new int[n];for (int i = 0; i < n; i++) {res[i] = nextInt() - 1;}return res;}public int[] nextIntArray1Index(int n) {int[] res = new int[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextInt();}return res;}public long[] nextLongArray(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong();}return res;}public long[] nextLongArrayDec(int n) {long[] res = new long[n];for (int i = 0; i < n; i++) {res[i] = nextLong() - 1;}return res;}public long[] nextLongArray1Index(int n) {long[] res = new long[n + 1];for (int i = 0; i < n; i++) {res[i + 1] = nextLong();}return res;}public double[] nextDoubleArray(int n) {double[] res = new double[n];for (int i = 0; i < n; i++) {res[i] = nextDouble();}return res;}}}