結果
問題 | No.1073 無限すごろく |
ユーザー |
|
提出日時 | 2020-07-16 13:42:46 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,761 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 206,532 KB |
最終ジャッジ日時 | 2025-01-11 21:33:41 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std; typedef long double ld; typedef long long ll;typedef unsigned long long ull;#define endl "\n"#define MP make_pair#define FOR(i,a,b) for(int i=(a);i<=(b);i++)#define FORR(x,arr) for(auto& x:arr)#define VI vector<int>#define PII pair<int, int>#define ALL(x) (x).begin(), (x).end()const int INF=1<<30; const ll LINF=1LL<<60 ; const ll mod=1e9+7 ;template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }//-------------------struct mint {ll x;mint(ll x=0):x(x%mod){}bool operator==(const mint a)const{return x==a.x;}bool operator!=(const mint a)const{return x!=a.x;}bool operator>=(const mint a){return (x >= a.x)? 1: 0;}bool operator<(const mint a){return !(*this>=a);}bool operator>(const mint a){return (x > a.x)? 1:0;}bool operator<=(const mint a){return !(*this>a);}mint& operator+=(const mint a) {if ((x += a.x) >= mod) x -= mod;return *this;}mint& operator-=(const mint a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}mint& operator*=(const mint a) {(x *= a.x) %= mod;return *this;}mint operator+(const mint a) const {mint res(*this);return res+=a;}mint operator-(const mint a) const {mint res(*this);return res-=a;}mint operator*(const mint a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a; //2 squareif (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(mod-2);}mint& operator/=(const mint a) {return (*this) *= a.inv();}mint operator/(const mint a) const {mint res(*this);return res/=a;}};//here below is Matrix library.template <class T>using Matrix = vector< vector<T> >;template <class T>void init_mat(Matrix<T> &A, int h, int w){A.resize(h, vector<T>(w,0));}template <class T>Matrix<T> dot_mat(Matrix<T> A, Matrix<T> B){Matrix<T> C(A.size(), vector<T>(B[0].size()));for(int i=0; i<A.size(); i++){for(int k=0; k<B.size(); k++){for(int j=0; j<B[0].size(); j++){C[i][j] = C[i][j] + A[i][k]*B[k][j];}}}return C;}template <class T>Matrix<T> pow_mat(Matrix<T> A, ll n){Matrix<T> B(A.size(), vector<T>(A.size()));for(int i=0; i<A.size(); i++) B[i][i] = 1;while(n){if(n&1) B = dot_mat(B,A);A = dot_mat(A,A);n >>= 1;}return B;}//testint main(){ll n; cin >> n;Matrix<mint> A,B;init_mat(A,6,6);init_mat(B,6,1);B[0][0] = mint(1);FOR(i,0,5) A[0][i] = mint(1)/mint(6);FOR(i,1,5) A[i][i-1] = mint(1);auto ans = dot_mat(pow_mat(A,n), B);cout << ans[0][0].x << endl;return 0;}