結果
問題 | No.344 ある無理数の累乗 |
ユーザー | kopricky |
提出日時 | 2017-09-12 00:17:10 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 8,357 bytes |
コンパイル時間 | 1,489 ms |
コンパイル使用メモリ | 167,188 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-07 15:58:17 |
合計ジャッジ時間 | 2,647 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 1 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 2 ms
5,248 KB |
testcase_14 | AC | 2 ms
5,248 KB |
testcase_15 | AC | 2 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | AC | 1 ms
5,248 KB |
testcase_18 | AC | 2 ms
5,248 KB |
testcase_19 | AC | 2 ms
5,248 KB |
testcase_20 | AC | 1 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 2 ms
5,248 KB |
testcase_24 | AC | 2 ms
5,248 KB |
testcase_25 | AC | 1 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 1 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
testcase_29 | AC | 2 ms
5,248 KB |
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000 #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; 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; mat<ll> mt(2,2); mt[0][0] = mt[1][0] = mt[1][1] = 1,mt[0][1] = 3; mat<ll> mt2 = mod_pow(mt,n); ll ans = 2*mt2[0][0] % MOD; if(n % 2 == 0){ ans = (ans + MOD - 1) % MOD; } cout << ans << endl; }