結果

問題 No.147 試験監督（2）
ユーザー koyumeishikoyumeishi
提出日時 2015-02-09 01:25:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 573 ms / 2,000 ms
コード長 2,487 bytes
コンパイル時間 1,325 ms
コンパイル使用メモリ 85,268 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 11:21:22
合計ジャッジ時間 3,817 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 567 ms
6,812 KB
testcase_01 AC 568 ms
6,944 KB
testcase_02 AC 573 ms
6,944 KB
testcase_03 AC 2 ms
6,940 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, 0LL));
	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, 0LL) );
	for(int i=0; i<n; i++){
		ret[i][i] = 1LL;
	}
	while(k>0LL){
		if(k&1LL) ret = multmat(A,ret, n,n,n);
		A = multmat(A,A, n,n,n);
		k>>=1LL;
	}
	return ret;
}

// X = a*Y + b
pair<string, long long> divide(string X, long long Y){
	string a = "";
	long long b = 0;

	for(int i=0; i<X.size(); i++){
		b *= 10;
		b += X[i] - '0';
		if(a.size() == 0){
			if(b/Y > 0) a.push_back(b/Y + '0');
		}else{
			a.push_back(b/Y + '0');
		}
		
		b %= Y;
	}
	return {a,b};
}

// 
string string_to_binary(string X, long long base){
	string ret = "";
	while(true){
		auto tmp = divide(X, base);
		X = tmp.first;
		ret.push_back(tmp.second + '0');
		
		//cerr << X.size() << " " << X[0] << endl;

		if(X.size() == 0){
			break;
		}
	}
	reverse(ret.begin(), ret.end());
	return ret;
}

long long mypow(long long X, long long k){
	if(X==0) return 0;

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

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

long long mypow(long long X, string k){
	if(X==0) return 0;

	long long ret = 1;

	for(int i=k.size()-1; i>=0; i--){
		if(k[i] == '1'){
			ret *= X;
			ret %= MOD;
		}

		X *= X;
		X %= MOD;
	}
	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 rem = divide(d, MOD-1).second;
		
		//string p = string_to_binary(d, 2);

		//cerr << x << " " << p << endl;

		ans *= mypow(x,rem)%MOD;
		ans %= MOD;
	}

	cout << ans << endl;

	return 0;
}
0