結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:12:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,326 bytes |
コンパイル時間 | 2,132 ms |
コンパイル使用メモリ | 174,320 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 15:41:46 |
合計ジャッジ時間 | 2,792 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; using vec = vector<int64_t>; using mat = vector<vec>; mat mul_mod(mat &a, mat &b, int64_t mod) { mat c(a.size(), vec(b[0].size(), 0)); for (int k = 0; k < a[0].size(); k++) { for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b[0].size(); j++) { (c[i][j] += a[i][k] * b[k][j] % mod) %= mod; } } } return c; } mat pow_mod(mat a, int64_t n, int64_t mod) { mat r(a.size(), vec(a.size(), 0)); for (int i = 0; i < a.size(); i++) { r[i][i] = 1; } for (; n; n >>= 1) { if (n & 1) { r = mul_mod(r, a, mod); } a = mul_mod(a, a, mod); } return r; } int main() { int64_t n; cin >> n; int64_t mod = 1000000007; auto mod_rev = [](int64_t a, int64_t mod) { auto ext_gcd = [](auto &f, int64_t a, int64_t b, int64_t &x, int64_t &y) { if (b == 0) { x = 1; y = 0; return a; } int64_t g = f(f, b, a % b, x, y); int64_t z = x; x = y; y = z - y * a / b; return g; }; int64_t x, y; ext_gcd(ext_gcd, a, mod, x, y); if (x < 0) { x += mod; } return x; }; mat arr(6, vec(6, 0)); for (int64_t j = 0; j < 6; j++) { arr[0][j] = mod_rev(6, mod); } for (int64_t i = 1; i < 6; i++) { arr[i][i - 1] = 1; } arr = pow_mod(arr, n, mod); cout << arr[0][0] << endl; return 0; }