結果
問題 | No.147 試験監督(2) |
ユーザー |
![]() |
提出日時 | 2015-02-09 00:11:54 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,185 bytes |
コンパイル時間 | 1,420 ms |
コンパイル使用メモリ | 167,116 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-23 08:38:09 |
合計ジャッジ時間 | 5,769 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;unsigned long long mod = 1000000007;inline long long bpow(long long a,long long b,long long m=1000000007){return b ? bpow(a*a%m,b/2,m) * (b&1?a:1) % m : 1 % m;}typedef vector< vector<long long> > Mat;inline Mat mult(Mat &a,Mat &b){int n = a.size();Mat res(n,vector<long long>(n));for(int i = 0 ; i < n ; i++)for(int j = 0 ; j < n ; j++)for(int k = 0 ; k < n ; k++){res[i][j] += a[i][k] % mod * b[k][j] % mod;res[i][j] %= mod;}return res;}Mat E(int n){Mat res(n,vector<long long>(n));for(int i = 0 ; i < n ; i++) res[i][i] = 1;return res;}Mat speedy(Mat x,long long k){if( k == 0 ) return E(x.size());Mat res = speedy(mult(x,x),k/2);if( k & 1 ){res = mult(res,x);}return res;}int main(){ios_base::sync_with_stdio(false); //関数です。int N;cin >> N;long long ans = 1;for(int i = 0 ; i < N ; i++){long long C;cin >> C;string D;cin >> D;long long d = 0;for(int j = 0 ; j < D.size() ; j++){d = d * 10 + D[j] - '0';d %= (mod-1);}ans *= bpow( speedy({{1,1},{1,0}},C+1)[0][0] % mod , d) % mod;ans %= mod;}cout << ans << endl;}