結果
問題 | No.147 試験監督(2) |
ユーザー | IL_msta |
提出日時 | 2015-08-07 19:28:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 511 ms / 2,000 ms |
コード長 | 2,747 bytes |
コンパイル時間 | 964 ms |
コンパイル使用メモリ | 89,852 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-18 05:01:35 |
合計ジャッジ時間 | 3,461 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 492 ms
5,248 KB |
testcase_01 | AC | 502 ms
5,376 KB |
testcase_02 | AC | 511 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <sstream> #include <algorithm> #include <cmath> #include <string> //#include <array> #include <list> #include <queue> #include <vector> #include <complex> #include <set> #include <map> ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)<<endl; #define PII pair<int,int> ///////// typedef long long LL; typedef long double LD; ///////// using namespace::std; ///////// const LL mod = (LL)1e9+7; int keta[201]; LL powStrMod(LL n,string num){//n^num % mod LL ans = 1; LL mul = n; int ketamax = num.size(); for(int i=num.size();i>0;--i){ keta[ketamax-i+1] = num[i-1]-'0'; } while( ketamax ){ if(keta[1]%2){ ans = (ans * mul)%mod; } //p /= 2; for(int i= ketamax;i>0;--i){ int ks=0; if( keta[i] % 2 ) ks = 10; keta[i] /= 2; if( i == ketamax && keta[i]==0) --ketamax; if(i>1){ keta[i-1] += ks; } } mul = (mul * mul)%mod; } return ans; } LL keta2[20];//200<=10*20 LL powStrMod2(LL n,string num){//n^num % mod if( n % mod == 0){ return 0; } LL ans = 1; LL mul = n; int ketamax;// = num.size(); int count = 0; int nowketa = (num.size()-1)/10; rep(i,20)keta2[i] = 0; for(int i=0;i<num.size();++i){ keta2[nowketa] = keta2[nowketa]*10 + num[i]-'0'; ++count; if( (num.size()-i-1)%10 == 0 ){ count = 0; keta2[nowketa] = keta2[nowketa]%(mod-1); --nowketa; } } ketamax = (num.size()-1)/10; LL ks=0; while( ketamax>=0 ){ if(keta2[0]%2){ ans = (ans * mul)%mod; } //p /= 2; for(int i= ketamax;i>=0;--i){ ks=0; if( keta2[i] % 2 ) ks = (LL)1e10; keta2[i] /= 2; //keta2[i] %= mod-1; if( i == ketamax && keta2[i]==0) --ketamax; if(i>0){ keta2[i-1] += ks; } } mul = (mul * mul)%mod; } return ans; } const int FMax = (int)1e5-1; int f[FMax+1]; void finit(){ f[0] = 0; f[1] = 1; for(int i=2;i<(FMax+1);++i){ f[i] = (f[i-2]+f[i-1])%mod; } } LL fmod(LL n,LL *a,LL *b){ if( n < FMax){ *a = f[n]; *b = f[n+1]; return *a; } LL A,B; fmod(n/2,&A,&B); if(n%2 == 0){ *a = (A*((2*B)%mod+mod-A)%mod)%mod; *b = ((B*B)%mod+(A*A)%mod)%mod; }else{ *a = ((B*B)%mod+(A*A)%mod)%mod; *b = (B*((2*A)%mod+B)%mod)%mod; } return *a; } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// //cout << setprecision(16);// int N; finit(); cin >> N;//机の種類 LL C,ans,tans,A,B; string D; ans = 1; rep(i,N){//3*10^4 //Ck 椅子の数 D個(D乗) cin>>C>>D; tans = fmod(C+2,&A,&B);//63 //tans = powStrMod(tans,D);//200 tans = powStrMod2(tans,D);//200 ans = (ans * tans)% mod; }//12600 //3.78*10^8 P(ans); return 0; }