結果

問題 No.147 試験監督（2）
ユーザー koyumeishikoyumeishi
提出日時 2015-02-09 00:32:13
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,742 bytes
コンパイル時間 881 ms
コンパイル使用メモリ 83,276 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 09:47:40
合計ジャッジ時間 3,308 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;

#define MOD 1000000007

//[n*p] * [p*m] => [n*m]
vector<vector<long long> > multmat(vector<vector<long long> > &A, vector<vector<long long> > &B, int n, int p, int m){
	vector<vector<long long> > C(n, vector<long long>(m,0));
	for(int i=0; i<n; i++){
		for(int k=0; k<p; k++){
			for(int j=0; j<m; j++){
				C[i][j] += A[i][k] * B[k][j];
				C[i][j] %= MOD;
			}
		}
	}
	return C;
}

//A[n*n]^k 
vector<vector<long long> > mat_pow(vector<vector<long long> > A, long long k){
	int n = A.size();
	vector<vector<long long> > ret(n, vector<long long>(n, 0) );
	for(int i=0; i<n; i++){
		ret[i][i] = 1;
	}
	while(k>0){
		if(k&1LL) ret = multmat(A,ret, n,n,n);
		A = multmat(A,A, n,n,n);
		k>>=1LL;
	}
	return ret;
}

// X%Y
long long rem(string X, long long Y){
	long long tmp = 0;
	for(int i=0; i<X.size(); i++){
		tmp *= 10;
		tmp += X[i] - '0';
		tmp %= Y;
	}
	return tmp;
}

long long mypow(long long X, long long k){
	long long ret = 1;
	while(k>0){
		if(k&1){
			ret *= X;
			ret %= MOD;
		}

		X *= X;
		X %= MOD;
		k >>= 1LL;
	}
	return ret;
}

int main(){
	int n;
	cin >> n;

	long long ans = 1;
	for(int i=0; i<n; i++){
		long long c;
		string d;
		cin >> c >> d;


		vector<vector<long long>> A(2, vector<long long>(2, 1));
		A[1][1] = 0;
		A = mat_pow(A, c+1);
		vector<vector<long long>> B(2, vector<long long>(1, 0));
		B[0][0] = 1;
		auto X = multmat(A,B, 2,2,1);

		long long x = X[0][0];
		long long D = rem(d, MOD);

		//cerr << x << " " << D << endl;

		ans *= mypow(x,D)%MOD;
		ans %= MOD;
	}
	cout << ans << endl;
	return 0;
}
0