結果
問題 | No.147 試験監督(2) |
ユーザー | kotatsugame |
提出日時 | 2020-03-04 08:38:27 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 814 bytes |
コンパイル時間 | 556 ms |
コンパイル使用メモリ | 66,952 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-22 00:57:14 |
合計ジャッジ時間 | 4,207 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 538 ms
5,376 KB |
testcase_01 | AC | 530 ms
5,376 KB |
testcase_02 | AC | 533 ms
5,376 KB |
testcase_03 | WA | - |
コンパイルメッセージ
main.cpp:17:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 17 | main() | ^~~~
ソースコード
#include<iostream> using namespace std; long mod=1e9+7; struct Mat{long A[2][2];}; Mat E; long power(long a,long b){return b?power(a*a%mod,b/2)*(b%2?a:1)%mod:1;} Mat Mmul(Mat a,Mat b){ Mat ret; for(int i=0;i<2;i++)for(int j=0;j<2;j++)ret.A[i][j]=0; for(int i=0;i<2;i++)for(int j=0;j<2;j++)for(int k=0;k<2;k++) { (ret.A[i][j]+=a.A[i][k]*b.A[k][j])%=mod; } return ret; } Mat Mpow(Mat a,long b){return b?Mmul(Mpow(Mmul(a,a),b/2),b%2?a:E):E;} main() { E.A[0][0]=E.A[1][1]=1; E.A[0][1]=E.A[1][0]=0; int N;cin>>N; long ans=1; for(;N--;) { long C;cin>>C; Mat f; f.A[0][0]=f.A[0][1]=f.A[1][0]=1; f.A[1][1]=0; f=Mpow(f,C); long T=(f.A[0][0]+f.A[1][0])%mod; string Ds;cin>>Ds; long D=0; for(int i=0;i<Ds.size();i++)D=(D*10+Ds[i]-'0')%(mod-1); ans=ans*power(T,D)%mod; } cout<<ans<<endl; }