結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 22:02:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,316 bytes |
コンパイル時間 | 944 ms |
コンパイル使用メモリ | 92,472 KB |
実行使用メモリ | 8,160 KB |
最終ジャッジ日時 | 2024-12-17 15:03:11 |
合計ジャッジ時間 | 2,141 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <algorithm>#include <iomanip>#include <vector>#include <queue>#include <set>#include <map>#define N_MAX 200002using namespace std;typedef long long ll;const ll MOD = 1000000007;template <typename T>struct matrix{int n, m;vector<vector<T>> dat;matrix(int n_, int m_){n = n_; m = m_;for(int i = 0; i < n; i++){dat.push_back(vector<T>(m));}}};template <typename T>bool prod(matrix<T> a, matrix<T> b, matrix<T> &ans){if(a.m != b.n) return false;for(int i = 0; i < a.n; i++){for(int j = 0; j < a.m; j++){ans.dat[i][j] = 0;for(int k = 0; k < b.m; k++){ans.dat[i][j] += a.dat[i][k]*b.dat[k][j];ans.dat[i][j] %= MOD;}}}return true;}template <typename T>void copy_mat(matrix<T> a, matrix<T> &b){for(int i = 0; i < a.n; i++){for(int j = 0; j < a.m; j++){b.dat[i][j] = a.dat[i][j];}}}template <typename T>void pow(matrix<T> a, ll n, matrix<T> &ans){matrix<T> buf(a.n, a.n);matrix<T> tmp(a.n, a.n);copy_mat(a, tmp);for(int i = 0; i < a.n; i++) {for(int j = 0; j < a.n; j++){ans.dat[i][j] = 0;}ans.dat[i][i] = 1;}for(int i = 0; i <= 62; i++){ll m = (ll)1 << i;if(m&n){prod(tmp, ans, buf);copy_mat(buf, ans);}prod(tmp, tmp, buf);copy_mat(buf, tmp);}}ll inv[N_MAX],fac[N_MAX],finv[N_MAX];void init(){fac[0]=fac[1]=1;finv[0]=finv[1]=1;inv[1]=1;for(int i=2;i<N_MAX;i++){inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;fac[i]=fac[i-1]*(ll) i%MOD;finv[i]=finv[i-1]*inv[i]%MOD;}}int main(){ios::sync_with_stdio(false);cin.tie(0);cout << setprecision(10) << fixed;init();matrix<ll> mat(6, 6);matrix<ll> ans(6, 6);mat.dat[0][1] = 1; mat.dat[1][2] = 1; mat.dat[2][3] = 1; mat.dat[3][4] = 1; mat.dat[4][5] = 1;mat.dat[5][0] = inv[6]; mat.dat[5][1] = inv[6]; mat.dat[5][2] = inv[6]; mat.dat[5][3] = inv[6]; mat.dat[5][4] = inv[6]; mat.dat[5][5] = inv[6];ll N;cin >> N;pow(mat, N, ans);cout << ans.dat[5][5] << endl;}