結果
問題 | No.147 試験監督(2) |
ユーザー | paruki |
提出日時 | 2016-09-12 20:39:11 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 415 ms / 2,000 ms |
コード長 | 4,874 bytes |
コンパイル時間 | 1,611 ms |
コンパイル使用メモリ | 177,848 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-17 04:05:35 |
合計ジャッジ時間 | 4,464 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 409 ms
5,248 KB |
testcase_01 | AC | 415 ms
5,248 KB |
testcase_02 | AC | 392 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i)) #define rep(i,j) FOR(i,0,j) #define each(x,y) for(auto &(x):(y)) #define mp make_pair #define all(x) (x).begin(),(x).end() #define debug(x) cout<<#x<<": "<<(x)<<endl #define smax(x,y) (x)=max((x),(y)) #define smin(x,y) (x)=min((x),(y)) #define MEM(x,y) memset((x),(y),sizeof (x)) #define sz(x) (int)(x).size() typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<ll> vll; template<int MOD> class ModInt{ public: ModInt():value(0){} ModInt(long long val):value((int)(val<0?MOD+val%MOD:val%MOD)){ } ModInt& operator+=(ModInt that){ value = value+that.value; if(value>=MOD)value-=MOD; return *this; } ModInt& operator-=(ModInt that){ value -= that.value; if(value<0)value+=MOD; return *this; } ModInt& operator*=(ModInt that){ value = (int)((long long)value * that.value % MOD); return *this; } ModInt &operator/=(ModInt that){ return *this *= that.inverse(); } ModInt operator+(ModInt that) const{ return ModInt(*this)+=that; } ModInt operator-(ModInt that) const{ return ModInt(*this)-=that; } ModInt operator*(ModInt that) const{ return ModInt(*this)*=that; } ModInt operator/(ModInt that) const { return ModInt(*this) /= that; } ModInt pow(long long k) const{ if(value == 0)return 0; ModInt n = *this, res = 1; while(k){ if(k & 1)res *= n; n *= n; k >>= 1; } return res; } ModInt inverse() const { long long a = value, b = MOD, u = 1, v = 0; while(b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } return ModInt(u); } int toi() const{ return value; } private: int value; }; typedef ModInt<1000000007> mint; ostream& operator<<(ostream& os, const mint& x){ os << x.toi(); return os; } template<class Val> class Matrix{ public: int n, m; Matrix(){ } Matrix(int n_, int m_):n(n_), m(m_), A(n, vector<Val>(m)){ } #define ITER(a,b) for(int i=0;i<a;++i)for(int j=0;j<b;++j) Matrix operator +(Matrix &B){ assert(n == B.n && m == B.m); Matrix C(n, m); ITER(n,m) C(i, j) = A[i][j] + B(i, j); return C; } Matrix operator -(Matrix &B){ assert(n == B.n && m == B.m); Matrix C(n, m); ITER(n, m) C(i, j) = A[i][j] - B(i, j); return C; } Matrix* operator +=(Matrix &B){ assert(n == B.n && m == B.m); ITER(n, m) A[i][j] += B(i, j); return this; } Matrix* operator -=(Matrix &B){ assert(n == B.n && m == B.m); ITER(n, m) A[i][j] -= B(i, j); return this; } Matrix operator *(Matrix &B){ assert(m == B.n); Matrix C(n, B.m); ITER(C.n, B.m) for(int k = 0; k < m; ++k) C(i, j) += A[i][k] * B(k, j); return C; } Matrix* operator *=(Matrix &B){ return &(*this = *this*B); } Matrix* operator ^=(long long k){ return &(*this = *this^k); } #undef ITER Matrix operator ^(long long k){ assert(n == m); Matrix C(n, n), D = *this; for(int i = 0; i < n; ++i)C(i, i) = 1; while(k > 0){ if(k & 1) C *= D; D *= D; k >>= 1; } return C; } Val& operator()(int i, int j){ return A[i][j]; } vector<Val>& operator[](int i){ return A[i]; } vector<Val> mulVec(const vector<Val> & u){ assert((int)u.size() == m); Matrix v(m, 1); for(int i = 0; i < m; ++i)v[i][0] = u[i]; v = (*this)*v; vector<Val> w(n); for(int i = 0; i < n; ++i)w[i] = v[i][0]; return w; } private: vector<vector<Val>> A; }; typedef Matrix<mint> mat; template<class Val> Val fibonacci(long long n){ if(n == 0)return 0; Matrix<Val> A(2, 2); A[0][0] = A[1][0] = A[0][1] = 1; A ^= n - 1; vector<Val> v{1, 0}; v = A.mulVec(v); return v[0]; } string nstr(){ static const int MAX_LEN = 210; static char res_[MAX_LEN]; scanf("%s",res_); return string(res_); } int main(){ const int MOD = (int)1e9 + 7; int N; cin >> N; mint ans = 1; rep(ii, N){ ll C, D = 0; scanf("%lld", &C); string s = nstr(); auto x = fibonacci<mint>(C + 2); for(int base = 1, i = sz(s) - 1; i >= 0; base = base * 10ll % (MOD - 1), i--){ D += (ll)base * (s[i] - '0'); D %= MOD - 1; } x = x.pow(D); ans *= x; } cout << ans << endl; }