結果
問題 | No.147 試験監督(2) |
ユーザー | ttkkggww |
提出日時 | 2022-07-23 20:45:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 474 ms / 2,000 ms |
コード長 | 3,797 bytes |
コンパイル時間 | 3,767 ms |
コンパイル使用メモリ | 270,800 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2024-07-05 11:23:13 |
合計ジャッジ時間 | 6,471 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 472 ms
10,496 KB |
testcase_01 | AC | 474 ms
10,496 KB |
testcase_02 | AC | 470 ms
10,624 KB |
testcase_03 | AC | 2 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; using mint = modint1000000007; template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector< T > &operator[](int k) const { return (A.at(k)); } inline vector< T > &operator[](int k) { return (A.at(k)); } static Matrix I(size_t n) { Matrix mat(n); for(int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix &operator-=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix &operator*=(const Matrix &B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); A.swap(C); return (*this); } Matrix &operator^=(long long k) { Matrix B = Matrix::I(height()); while(k > 0) { if(k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } friend ostream &operator<<(ostream &os, Matrix &p) { size_t n = p.height(), m = p.width(); for(int i = 0; i < n; i++) { os << "["; for(int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() { Matrix B(*this); assert(width() == height()); T ret = 1; for(int i = 0; i < width(); i++) { int idx = -1; for(int j = i; j < width(); j++) { if(B[j][i] != 0) idx = j; } if(idx == -1) return (0); if(i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for(int j = 0; j < width(); j++) { B[i][j] /= vv; } for(int j = i + 1; j < width(); j++) { T a = B[j][i]; for(int k = 0; k < width(); k++) { B[j][k] -= B[i][k] * a; } } } return (ret); } }; int n; vector<ll> c; vector<string> s; mint calc(ll x){ Matrix<mint> m; m.A = vector<vector<mint>>(2,vector<mint>(2)); m.A[0][0] = 1; m.A[0][1] = 1; m.A[1][0] = 1; mint res = 0; x--; m^=x; for(int i =0;i<2;i++) for(int j = 0;j<2;j++)res += m.A[i][j]; return res; } mint pow(mint x,string s){ reverse(s.begin(),s.end()); mint cur = x; mint res = 1; for(int i = 0;i<s.size();i++){ res *= cur.pow(s[i]-'0'); cur = cur.pow(10); } return res; } void solve(){ mint ans = 1; for(int i = 0;i<n;i++){ ans *= pow(calc(c[i]),s[i]); } cout<<ans.val()<<endl; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n; c = vector<ll>(n); s = vector<string>(n); for(int i = 0;i<n;i++){ cin >> c[i] >> s[i]; } solve(); }