結果
| 問題 |
No.147 試験監督（2）
|
| コンテスト | |
| ユーザー |
 threepipes_s
|
| 提出日時 | 2015-02-10 22:33:45 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | WA * 4 |
ソースコード
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());
}
}