結果
問題 |
No.44 DPなすごろく
|
ユーザー |
|
提出日時 | 2025-08-25 14:33:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 1,289 bytes |
コンパイル時間 | 922 ms |
コンパイル使用メモリ | 96,104 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-25 14:33:41 |
合計ジャッジ時間 | 2,129 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 |
ソースコード
#include <iostream> #include <vector> #include <set> #include <map> #include <queue> #include <algorithm> #include <cstring> #include <cstdio> #include <fstream> #include <sstream> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> matrix; matrix identity(int n) { matrix A(n, vec(n)); for (int i = 0; i < n; ++i) A[i][i] = 1; return A; } matrix mul(const matrix &A, const matrix &B) { matrix C(A.size(), vec(B[0].size())); for (int i = 0; i < C.size(); ++i) for (int j = 0; j < C[i].size(); ++j) for (int k = 0; k < A[i].size(); ++k) C[i][j] += A[i][k] * B[k][j]; return C; } vec mul(const matrix &A, const vec &x) { vec y(A.size()); for (int i = 0; i < A.size(); ++i) for (int j = 0; j < A[0].size(); ++j) y[i] += A[i][j] * x[j]; return y; } matrix pow(const matrix &A, int e) { return e == 0 ? identity((int)A.size()) : e % 2 == 0 ? pow(mul(A, A), e/2) : mul(A, pow(A, e-1)); } int main(){ int N; cin >> N; matrix A(2, vec(2)); A[0][0] = 0; A[0][1] = 1; A[1][0] = 1; A[1][1] = 1; vec init(2); init[0] = init[1] = 1; vec res = mul(pow(A, N), init); cout << res[0] << endl; return 0; }