結果
問題 | No.344 ある無理数の累乗 |
ユーザー |
![]() |
提出日時 | 2016-04-08 06:09:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,619 bytes |
コンパイル時間 | 1,927 ms |
コンパイル使用メモリ | 174,932 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-10 23:54:51 |
合計ジャッジ時間 | 2,867 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,a,b) for (int i=(a);i<(b);i++) #define rrep(i,n) for (int i=(n)-1;i>=0;i--) #define rrep2(i,a,b) for (int i=(b)-1;i>=(a);i--) #define all(a) (a).begin(),(a).end() typedef long long ll; typedef pair<int, int> P; typedef vector<int> vi; typedef vector<P> vp; typedef vector<ll> vll; typedef vector<ll> Vec; typedef vector<Vec> Mat; const ll mod = 1000; Mat mulMatMat(Mat A, Mat B) { int n = A.size(); Mat C(n, Vec(n, 0)); rep(i, n) { rep(j, n) { rep(k, n) { C[i][j] += A[i][k] * B[k][j]; C[i][j] %= mod; } } } return C; } Vec mulMatVec(Mat A, Vec vec) { int n = A.size(); Vec res(n, 0); // reverse(all(vec)); // 添え字の大きい要素を上に持ってくるため rep(i, n) { rep(j, n) { res[i] += A[i][j] * vec[j]; res[i] %= mod; } } return res; } Mat powMat(Mat A, ll p) { int n = A.size(); Mat R(n, Vec(n, 0)); rep(i, n) R[i][i] = 1; // 単位行列 for (; p >= 1; p /= 2) { if (p & 1) { R = mulMatMat(A, R); } A = mulMatMat(A, A); } return R; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); ll n; cin >> n; if (n == 0) { cout << 1 << endl; return 0; } Mat A(2, Vec(2, 1)); A[0][1] = 3; A = powMat(A, n); auto vec = mulMatVec(A, {1, 0}); cout << (2 * vec[0] - (n % 2 == 0)) % mod << endl; }