結果
問題 | No.1073 無限すごろく |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:49:10 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,383 bytes |
コンパイル時間 | 764 ms |
コンパイル使用メモリ | 83,904 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-17 14:15:58 |
合計ジャッジ時間 | 1,854 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <cstdio> #include <cmath> #include <ctime> #include <cstdlib> #include <cassert> #include <vector> #include <list> #include <stack> #include <queue> #include <deque> #include <map> #include <set> #include <bitset> #include <string> #include <algorithm> #include <utility> #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define mod 1000000007 using namespace std; typedef pair<llint, llint> P; struct Matrix{ int h, w; vector<llint> mat; Matrix(){ h = w = 0; } Matrix(int h, int w){ this->h = h, this->w = w; mat.resize(h*w); } llint& at(int i, int j){ return mat[w*(i-1)+(j-1)]; } static Matrix ident(int size){ Matrix ret(size, size); for(int i = 1; i <= size; i++) ret.at(i, i) = 1; return ret; } Matrix operator*(Matrix& ope){ Matrix ret(h, ope.w); for(int i = 1; i <= h; i++){ for(int j = 1; j <= ope.w; j++){ for(int k = 1; k <= w; k++){ ret.at(i, j) += at(i, k) * ope.at(k, j) % mod; ret.at(i, j) %= mod; } } } return ret; } Matrix pow(llint n){ if(n == 0) return ident(h); if(n % 2){ return pow(n-1) * (*this); } else{ Matrix tmp = pow(n/2); return tmp * tmp; } } void print(){ for(int i = 1; i <= h; i++){ for(int j = 1; j <= w; j++){ cout << at(i, j) << " "; } cout << endl; } } }; llint modpow(llint a, llint n) { if(n == 0) return 1; if(n % 2){ return ((a%mod) * (modpow(a, n-1)%mod)) % mod; } else{ return modpow((a*a)%mod, n/2) % mod; } } llint n; llint p[6]; llint inv6; Matrix mat; int main(void) { ios::sync_with_stdio(0); cin.tie(0); inv6 = modpow(6, mod-2); cin >> n; p[0] = 1; for(int i = 1; i < 6; i++){ for(int j = 0; j < i; j++) p[i] += p[j], p[i] %= mod; p[i] *= inv6, p[i] %= mod; } if(n < 6){ cout << p[n] << endl; return 0; } mat = Matrix(6, 6); for(int i = 1; i <= 6; i++){ for(int j = 1; j <= 6; j++){ mat.at(i, j) = 0; } } for(int i = 1; i <= 6; i++) mat.at(1, i) = inv6; for(int i = 1; i <= 5; i++) mat.at(i+1, i) = 1; Matrix pmat = mat.pow(n-5); llint ans = 0; for(int i = 1; i <= 6; i++) ans += pmat.at(1, i) * p[6-i] % mod, ans %= mod; cout << ans << endl; return 0; }