結果
問題 | No.147 試験監督(2) |
ユーザー | threepipes_s |
提出日時 | 2015-02-10 22:33:45 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 5,984 bytes |
コンパイル時間 | 2,503 ms |
コンパイル使用メモリ | 89,480 KB |
実行使用メモリ | 75,392 KB |
最終ジャッジ日時 | 2024-06-23 18:23:49 |
合計ジャッジ時間 | 10,369 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
ソースコード
import java.io.BufferedReader; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList; import java.util.Comparator; import java.util.List; public class Main { public static long mod = 1000000007; public static void main(String[] args) throws NumberFormatException, IOException{ ContestScanner in = new ContestScanner(); int n = in.nextInt(); long res = 1; for(int i=0; i<n; i++){ long c = in.nextLong(); String dst = in.nextToken(); long d = 0; int len = dst.length(); for(int j=0; j<len; j++){ d = d*10 + dst.charAt(j)-'0'; if(d > mod-1) d %= mod-1; } res *= MyMath.modpow(fibo(c+1), d, mod); if(res >= mod) res %= mod; } System.out.println(res); } public static long fibo(long n){ if(n == 0 || n == 1) return 1; long[][] a = { {1}, {1} }; long[][] b = { {0, 1}, {1, 1} }; MatLong fibmat = new MatLong(a); fibmat.setMod(mod); MatLong multmat = new MatLong(b); multmat.setMod(mod); return multmat.pow(n).mult(fibmat).get(0, 0); } } class MatLong{ long[][] matrix; int x; int y; long mod; public MatLong(int x, int y){ matrix = new long[y][x]; this.x = x; this.y = y; } public MatLong(long[][] mat){ matrix = mat; x = mat[0].length; y = mat.length; } public void init(long[][] mat){ matrix = mat; x = mat[0].length; y = mat.length; } public void setMod(long m){ mod = m; } public MatLong add(MatLong m){ if(m.x != x || m.y != y) return null; long[][] newm = new long[y][x]; for(int i=0; i<y; i++){ for(int j=0; j<x; j++){ newm[i][j] = matrix[i][j] + m.matrix[i][j]; if(mod > 0 && newm[i][j] >= mod) newm[i][j] %= mod; } } return new MatLong(newm); } public MatLong addTo(MatLong m){ if(m.x != x || m.y != y) return null; for(int i=0; i<y; i++){ for(int j=0; j<x; j++){ matrix[i][j] = matrix[i][j] + m.matrix[i][j]; if(mod > 0 && matrix[i][j] >= mod) matrix[i][j] %= mod; } } return this; } public MatLong mult(MatLong m){ if(m.y != x) return null; long[][] newm = new long[y][m.x]; for(int i=0; i<y; i++){ for(int j=0; j<m.x; j++){ for(int k=0; k<x; k++){ newm[i][j] += matrix[i][k]*m.matrix[k][j]; if(mod > 0 && newm[i][j] >= mod) newm[i][j] %= mod; } } } return new MatLong(newm); } public MatLong multTo(MatLong m){ if(m.y != x) return null; long[][] newm = new long[y][m.x]; for(int i=0; i<y; i++){ for(int j=0; j<m.x; j++){ for(int k=0; k<x; k++){ newm[i][j] += matrix[i][k]*m.matrix[k][j]; if(mod > 0 && newm[i][j] >= mod) newm[i][j] %= mod; } } } init(newm); return this; } public MatLong clone(){ return new MatLong(matrix.clone()); } public void toUnit(){ int max = Math.min(x, y); for(int i=0; i<max; i++){ matrix[i][i] = 1; } } public MatLong pow(long n){ if(x != y) return null; MatLong res = new MatLong(x, x); res.toUnit(); MatLong a = this.clone(); while(n > 0){ if((n&1) == 1){ res = res.mult(a); } a = a.mult(a); n >>= 1; } return res; } public long get(int x, int y){ return matrix[y][x]; } public String toString(){ StringBuilder sb = new StringBuilder(); for(long[] i : matrix){ for(long j : i){ sb.append(j+"\t"); } sb.append("\n"); } return sb.toString(); } } class MyComp implements Comparator<int[]>{ public int compare(int[] a, int[] b) { return a[0] - b[0]; } } // //class Reverse implements Comparator<Integer>{ // public int compare(Integer arg0, Integer arg1) { // return arg1 - arg0; // } //} class Node{ int id; List<Node> edge = new ArrayList<Node>(); public Node(int id){ this.id = id; } public void createEdge(Node node){ edge.add(node); } } class MyMath{ public final static double PIhalf = Math.PI/2.0; public static double pAngle(double x, double y){ // ベクトル(1, 0)と(x, y)とのなす角を返す(rad:0 to 2pi) if(x == 0){ if(y == 0){ System.err.println("pAngle error: zero vector."); return 0; }else if(y < 0){ return PIhalf*3.0; }else{ return PIhalf; } } double rad = Math.atan(y/x); if(rad < 0){ rad += Math.PI*2.0; } return rad; } public static long fact(long n){ long res = 1; while(n > 0){ res *= n--; } return res; } public static long[][] pascalT(int n){ long[][] tri = new long[n][]; for(int i=0; i<n; i++){ tri[i] = new long[i+1]; for(int j=0; j<i+1; j++){ if(j == 0 || j == i){ tri[i][j] = 1; }else{ tri[i][j] = tri[i-1][j-1] + tri[i-1][j]; } } } return tri; } public static long modpow(long a, long x, long mod){ long res = 1; while(x > 0){ if((x & 1) == 1) res *= a; if(res >= mod) res %= mod; a *= a; if(a >= mod) a %= mod; x >>= 1; } return res; } // 最大公約数 static int gcd(int a, int b){ return b == 0 ? a : gcd(b, a % b); } // 最小公倍数 static int lcm(int a, int b){ return a * b / gcd(a, b); } } class ContestScanner{ private BufferedReader reader; private String[] line; private int idx; public ContestScanner() throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(System.in)); } public ContestScanner(String filename) throws FileNotFoundException{ reader = new BufferedReader(new InputStreamReader(new FileInputStream(filename))); } public String nextToken() throws IOException{ if(line == null || line.length <= idx){ line = reader.readLine().trim().split(" "); idx = 0; } return line[idx++]; } public long nextLong() throws IOException, NumberFormatException{ return Long.parseLong(nextToken()); } public int nextInt() throws NumberFormatException, IOException{ return (int)nextLong(); } public double nextDouble() throws NumberFormatException, IOException{ return Double.parseDouble(nextToken()); } }