結果
問題 | No.147 試験監督(2) |
ユーザー |
![]() |
提出日時 | 2015-02-08 23:35:17 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,716 bytes |
コンパイル時間 | 1,027 ms |
コンパイル使用メモリ | 96,152 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-23 07:29:37 |
合計ジャッジ時間 | 4,617 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 3 |
ソースコード
#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 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(201);b[0] = 1;for (int i = 1; i <= 200; i++)b[i] = b[i - 1] * 2 % MOD;int N; cin >> N;ll sum = 1;while (N--) {ll C; string D; cin >> C >> D;ll x = matpow(a, C + 1)[0][0];ll y = 0;for (int i = 0; i < D.length(); i++)y += b[D.length() - i - 1] * (D[i] - '0');y %= MOD;sum = sum * x % MOD * y % MOD;}cout << sum << endl;}