結果
| 問題 | No.147 試験監督（2） |
| ユーザー |
 kopricky
|
| 提出日時 | 2017-07-29 09:43:36 |
| 言語 | C++11 (gcc 11.4.0) |
| 結果 |
AC
|
| 実行時間 | 645 ms / 2,000 ms |
| コード長 | 8,936 bytes |
| コンパイル時間 | 1,535 ms |
| コンパイル使用メモリ | 168,880 KB |
| 実行使用メモリ | 6,820 KB |
| 最終ジャッジ日時 | 2024-10-10 21:27:38 |
| 合計ジャッジ時間 | 4,882 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 627 ms
6,816 KB |
| testcase_01 | AC | 643 ms
6,816 KB |
| testcase_02 | AC | 645 ms
6,820 KB |
| testcase_03 | AC | 2 ms
6,816 KB |
ソースコード
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a, b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define pb push_back
#define show(x) cout <<#x<<" = "<<(x)<<endl
#define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl
using namespace std;
typedef pair<int,int>P;
const int MAX_N = 100005;
ll mod_pow(ll a,ll b)
{
a %= MOD;
ll res = 1;
while(b){
if(b & 1){
res = res * a % MOD;
}
a = a * a %MOD;
b >>= 1;
}
return res;
}
ll pow_string(ll a,string& s)
{
ll nw = 1;
rep(i,s.length()){
int val = s[i]-'0';
nw = mod_pow(nw,10);
nw = nw*mod_pow(a,val)%MOD;
}
return nw;
}
template<typename T> class mat : public vector<vector<T> > {
private:
int r,c; //行,列
public:
int row() const {
return r;
}
int column() const {
return c;
}
mat(int n,int m,T val = 0){
this->r = n,this->c = m;
rep(i,n){
this->push_back(vector<T>(m,val));
}
}
mat operator+(const mat& another){
if(this->r != another.r && this->c != another.c){
cout << "足し算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] + another[i][j];
}
}
return X;
}
mat operator+(const T val){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] + val;
}
}
return X;
}
mat operator-(const mat& another){
if(this->r != another.r && this->c != another.c){
cout << "引き算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] - another[i][j];
}
}
return X;
}
mat operator-(const T val){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = (*this)[i][j] - val;
}
}
return X;
}
vector<T> operator*(const vector<T>& another){
if(this->c != another.size()){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
vector<T> vec(this->r,0);
rep(i,this->r){
rep(j,this->c){
vec[i] += (*this)[i][j] * another[j];
}
}
return vec;
}
mat operator*(const mat& another){
if(this->c != another.r){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(this->r,another.c);
rep(i,this->r){
rep(k,this->c){
rep(j,another.c){
X[i][j] += (*this)[i][k]*another[k][j];
}
}
}
return X;
}
mat operator-(){
mat<T> X(this->r,this->c);
rep(i,this->r){
rep(j,this->c){
X[i][j] = -(*this)[i][j];
}
}
return X;
}
int rank(){
int n = this->r;
int res = 0;
mat B(n,n);
rep(i,n){
rep(j,n){
B[i][j] = (*this)[i][j];
}
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
continue;
}
swap(B[i],B[pivot]);
for(int j=i+1;j<n;j++){
B[i][j] /= B[i][i];
}
for(int j=i+1;j<n;j++){
for(int k=i+1;k<n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
res++;
}
return res;
}
T det(){
if(this->r != this->c){
cout << "正方行列でない(行列式定義不可)" << endl;
exit(1);
}
T ans = 1;
int n = this->r;
mat B(n,n);
rep(i,n){
rep(j,n){
B[i][j] = (*this)[i][j];
}
}
rep(i,n) {
for(int j=i+1;j<n;j++){
for (; B[j][i] != 0; ans = -ans) {
T r = B[i][i] / B[j][i];
for(int k=i;k<n;k++) {
T t = B[i][k] - r * B[j][k];
B[i][k] = B[j][k];
B[j][k] = t;
}
}
}
ans *= B[i][i];
}
return ans;
}
mat inverse(){
if(this->r != this->c){
cout << "正方行列でない(逆行列定義不可)" << endl;
exit(1);
}
int n = this->r;
mat B(n,2*n);
rep(i,n){
rep(j,n){
B[i][j] = (*this)[i][j];
}
}
rep(i,n){
B[i][n+i] = 1;
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
cout << "解なしor不定" << endl;
exit(1);
}
swap(B[i],B[pivot]);
for(int j=i+1;j<=2*n;j++){
B[i][j] /= B[i][i];
}
rep(j,n){
if(i != j){
for(int k=i+1;k<=2*n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
}
}
mat res(n,n);
rep(i,n){
rep(j,n){
res[i][j] = B[i][n+j];
}
}
return res;
}
void print(){
rep(i,this->r){
rep(j,(this->c)-1){
cout << (*this)[i][j] << ",";
}
cout << (*this)[i][(this->c)-1] << endl;
}
}
};
template<typename T> vector<T> eq_solve(const mat<T>& A,const vector<T>& b){
if(A.row() != A.column()){
cout << "正方行列でない(解なしor不定)" << endl;
exit(1);
}
int n = A.row();
mat<T> B(n,n+1);
rep(i,n){
rep(j,n){
B[i][j] = A[i][j];
}
}
rep(i,n){
B[i][n] = b[i];
}
rep(i,n){
int pivot = i;
for(int j=i;j<n;j++){
if(abs(B[j][i]) > abs(B[pivot][i])){
pivot = j;
}
}
if(abs(B[pivot][i]) < EPS){
cout << "解なしor不定" << endl;
exit(1);
}
swap(B[i],B[pivot]);
for(int j=i+1;j<=n;j++){
B[i][j] /= B[i][i];
}
rep(j,n){
if(i != j){
for(int k=i+1;k<=n;k++){
B[j][k] -= B[j][i] * B[i][k];
}
}
}
}
vector<T> res(n);
rep(i,n){
res[i] = B[i][n];
}
return res;
}
template<typename T> mat<T> pow(mat<T> A,ll cnt)
{
if(A.row() != A.column()){
cout << "累乗不可" << endl;
}
int n = A.row();
mat<T> B(n,n);
rep(i,n){
B[i][i] = 1;
}
while(cnt>0){
if(cnt & 1){
B = B*A;
}
A = A*A;
cnt >>= 1;
}
return B;
}
template<typename T> mat<T> mod_mul(mat<T>& A,mat<T>& B)
{
if(A.column() != B.row()){
cout << "掛け算失敗(サイズ不一致)" << endl;
exit(1);
}
mat<T> X(A.row(),B.column());
rep(i,A.row()){
rep(k,A.column()){
rep(j,B.column()){
X[i][j] = (X[i][j] + A[i][k]*B[k][j]) % MOD;
}
}
}
return X;
}
template<typename T> mat<T> mod_pow(mat<T> A,ll cnt)
{
if(A.row() != A.column()){
cout << "累乗不可" << endl;
}
int n = A.row();
mat<T> B(n,n);
rep(i,n){
B[i][i] = 1;
}
while(cnt>0){
if(cnt & 1){
B = mod_mul(B,A);
}
A = mod_mul(A,A);
cnt >>= 1;
}
return B;
}
int main()
{
int n;
cin >> n;
ll ans = 1;
mat<ll> a(2,2);
a[0][1] = 1,a[1][0] = 1,a[1][1] = 1;
vector<ll> vec(2);
vec[0] = 1,vec[1] = 2;
rep(i,n){
ll num;
string s;
cin >> num >> s;
ll tt;
mat<ll> b = mod_pow(a,num-1);
vector<ll> res = b*vec;
tt = res[1] % MOD;
ll t = pow_string(tt,s);
ans = ans*t % MOD;
}
cout << ans << endl;
return 0;
}