結果
問題 | No.147 試験監督(2) |
ユーザー |
![]() |
提出日時 | 2015-02-08 23:50:41 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,896 bytes |
コンパイル時間 | 990 ms |
コンパイル使用メモリ | 96,488 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-23 08:14:54 |
合計ジャッジ時間 | 4,122 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 3 WA * 1 |
ソースコード
#define _USE_MATH_DEFINES#include <algorithm>#include <cstdio>#include <functional>#include <iostream>#include <cfloat>#include <climits>#include <cstring>#include <cmath>#include <map>#include <queue>#include <random>#include <set>#include <sstream>#include <stack>#include <string>#include <time.h>#include <vector>using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> i_i;typedef pair<ll, int> ll_i;typedef pair<double, int> d_i;typedef pair<ll, ll> ll_ll;typedef pair<double, double> d_d;struct edge { int u, v, w; };ll MOD = 1000000007;ll _MOD = 1000000009;double EPS = 1e-10;int INF = INT_MAX / 2;vector< vector<ll> > matmul(vector< vector<ll> >& A, vector< vector<ll> >& B) {int n = A.size();vector< vector<ll> > C(n, vector<ll>(n));for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;return C;}vector< vector<ll> > matpow(vector< vector<ll> > A, ll x) {int n = A.size();vector< vector<ll> > B(n, vector<ll>(n));for (int i = 0; i < n; i++) B[i][i] = 1;while (x > 0) {if (x % 2) B = matmul(B, A);x /= 2;A = matmul(A, A);}return B;}int pow_mod(ll x, ll n, int m) {ll res = 1;for (; n > 0; n >>= 1) {if (n & 1) res = (res * x) % m;x = (x * x) % m;}return res;}int main() {vector< vector<ll> > a(2, vector<ll>(2));a[0][0] = 1; a[0][1] = 1;a[1][0] = 1; a[1][1] = 0;vector<ll> b(202);b[0] = 1;for (int i = 1; i <= 201; i++)b[i] = b[i - 1] * 10 % (MOD - 1);int N; cin >> N;ll sum = 1;while (N--) {ll C; string D; cin >> C >> D;ll x = matpow(a, C + 1)[0][0] % MOD;ll y = 0;for (int i = 0; i < D.length(); i++)y += b[D.length() - i - 1] * (D[i] - '0');y %= MOD - 1;ll z = pow_mod(x, y, MOD);sum = sum * z % MOD;}cout << sum << endl;}