結果
問題 | No.658 テトラナッチ数列 Hard |
ユーザー | uchiiii |
提出日時 | 2020-08-14 14:32:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 478 ms / 2,000 ms |
コード長 | 3,497 bytes |
コンパイル時間 | 3,138 ms |
コンパイル使用メモリ | 235,644 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-04-27 03:20:48 |
合計ジャッジ時間 | 5,771 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 3 ms
6,944 KB |
testcase_04 | AC | 164 ms
6,944 KB |
testcase_05 | AC | 194 ms
6,940 KB |
testcase_06 | AC | 246 ms
6,944 KB |
testcase_07 | AC | 259 ms
6,940 KB |
testcase_08 | AC | 327 ms
6,940 KB |
testcase_09 | AC | 478 ms
6,940 KB |
testcase_10 | AC | 477 ms
6,944 KB |
ソースコード
#pragma GCC target("avx2") #pragma GCC optimize("03") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; #define endl "\n" #define FOR(i,a,b) for(int i=(a);i<=(b);i++) #define rep(i,n) for(int i=0;i<(n);i++) #define PII pair<int, int> #define PLL pair<ll, ll> #define ALL(x) (x).begin(), (x).end() constexpr int INF=1<<30; constexpr ll LINF=1LL<<60; constexpr ll mod=17; constexpr int NIL = -1; template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; } template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; } template<class T>inline int popcount(T a) {return __builtin_popcount(a);} template<class T>inline T emod(T a, T p) { return (a%p + p) % p;} //------------------- 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) { return (*this) *= a.inv(); } 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 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 square if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2); } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; //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; } template<class T> void print(Matrix<T> &A) { for(int i=0; i<A.size(); i++) { for(int j=0; j<A[0].size(); j++) { cout << A[i][j] << " "; } cout << endl; } } int main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); int N; cin >> N; Matrix<mint> A; init_mat(A, 4,4); rep(i, 4) A[0][i] = mint(1); rep(i, 3) A[i+1][i] = mint(1); // print(A); Matrix<mint> B; init_mat(B,4,1); B[0][0] = 1; while(N--) { ll n; cin >> n; n--; auto C = dot_mat(pow_mat(A, n), B); cout << C[3][0] << endl; } return 0; }