結果
| 問題 | No.344 ある無理数の累乗 |
| ユーザー |
 kopricky
|
| 提出日時 | 2017-09-12 00:17:10 |
| 言語 | C++11 (gcc 13.3.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 30 |
ソースコード
#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<<endlusing 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;}