結果
問題 | No.533 Mysterious Stairs |
ユーザー |
![]() |
提出日時 | 2021-02-14 21:14:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 5,000 ms |
コード長 | 21,494 bytes |
コンパイル時間 | 2,242 ms |
コンパイル使用メモリ | 196,024 KB |
実行使用メモリ | 57,968 KB |
最終ジャッジ日時 | 2024-07-22 08:21:28 |
合計ジャッジ時間 | 3,413 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
// #pragma GCC optimize ("O3")// #pragma GCC target("avx512f")// #pragma GCC optimize("unroll-loops")#ifndef ONLINE_JUDGE#define _GLIBCXX_DEBUG#endif#include<bits/stdc++.h>// #include<atcoder/all>using namespace std;#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/#define pb push_back#define pf push_front#define fi first#define se second#define eb emplace_back#define endl '\n'#define SZ(x) ((ll)(x).size())#define all(x) (x).begin(),(x).end()#define rall(x) (x).rbegin(),(x).rend()#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define PI 3.14159265359const double eps = 1e-12;const long long INF= 1e+18+1;typedef double D; // 座標値の型。doubleかlong doubleを想定typedef complex<D> Point; // Pointtypedef long long ll;typedef vector<ll> vl;typedef vector<vl>vvl;typedef vector<vvl>vvvl;typedef vector<vvvl>vvvvl;typedef vector<vvvvl>vvvvvl;typedef pair<ll,ll> P;typedef tuple<ll,ll,ll> T;template<class T> using minpq=priority_queue<T,vector<T>,greater<T>>;const ll MOD=1000000007LL;// const ll MOD=998244353LL;const ll mod=MOD;string abc="abcdefghijklmnopqrstuvwxyz";string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";vl dx={0,0,1,-1,1,1,-1,-1};vl dy={1,-1,0,0,-1,1,-1,1};template<class T> vector<T> make_vec(size_t a) { return vector<T>(a); }template<class T, class... Ts> auto make_vec(size_t a, Ts... ts) {return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}//素因数分解O(√n)map<ll,ll>prime_factor(ll n){map<ll,ll>res;for(ll i=2;i*i<=n;i++){while(n%i==0){res[i]++;n/=i;}}if(n!=1)res[n]=1;return res;}const ll MAX = 5000010;long long fac[MAX], finv[MAX], inv[MAX];//finvが階乗の逆元// テーブルを作る前処理void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (ll i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}// 二項係数計算long long COM(ll n, ll k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}ll modpow(ll a, ll n,ll mod=MOD) {ll res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}/*Eratosthenes()ll N=2000010;vl arr(N);void Eratosthenes(){for(ll i = 0; i < N; i++){arr[i] = 1;}arr[1]=0;for(ll i = 2; i < sqrt(N); i++){if(arr[i]){for(ll j = 0; i * (j + 2) < N; j++){arr[i *(j + 2)] = 0;}}}}*///素数判定O(√n)bool is_prime(ll n){for(ll i=2;i*i<=n;i++){if(n%i==0)return false;}return n!=1;}//約数の列挙O(√n)vector<ll>divisor(ll n){vector<ll>res;for(ll i=1;i*i<=n;i++){if(n%i==0){res.push_back(i);if(i != n/i) res.push_back(n/i);}}return res;}/* Trie 木: 文字の種類(char_size)、int型で0に対応する文字(base)insert(word): 単語 word を Trie 木に挿入するsearch(word): 単語 word が Trie 木にあるか判定するstart_with(prefix): prefix が一致する単語が Trie 木にあるか判定するcount(): 挿入した単語の数を返すsize(): Trie 木の頂点数を返す計算量:insert, search ともに O(M)(Mは単語の長さ)*/template <int char_size, int base>struct Trie {struct Node { // 頂点を表す構造体vector<int> next; // 子の頂点番号を格納。存在しなければ-1vector<int> accept; // 末端がこの頂点になる単語の word_id を保存int c; // base からの間隔をint型で表現したものint common; // いくつの単語がこの頂点を共有しているかNode(int c_) : c(c_), common(0) {next.assign(char_size, -1);}};vector<Node> nodes; // trie 木本体int root;Trie() : root(0) {nodes.push_back(Node(root));}// 単語の挿入void insert(const string &word, int word_id) {int node_id = 0;for (int i = 0; i < (int)word.size(); i++) {int c = (int)(word[i] - base);int &next_id = nodes[node_id].next[c];if (next_id == -1) { // 次の頂点が存在しなければ追加next_id = (int)nodes.size();nodes.push_back(Node(c));}++nodes[node_id].common;node_id = next_id;}++nodes[node_id].common;nodes[node_id].accept.push_back(word_id);}void insert(const string &word) {insert(word, nodes[0].common);}// 単語とprefixの検索bool search(const string &word, bool prefix = false) {int node_id = 0;for (int i = 0; i < (int)word.size(); i++) {int c = (int)(word[i] - base);int &next_id = nodes[node_id].next[c];if (next_id == -1) { // 次の頂点が存在しなければ終了return false;}node_id = next_id;}return (prefix) ? true : nodes[node_id].accept.size() > 0;}// prefix を持つ単語が存在するかの検索bool start_with(const string &prefix) {return search(prefix, true);}// 挿入した単語の数int count() const {return (nodes[0].common);}// Trie木のノード数int size() const {return ((int)nodes.size());}};// //Lowest Common Ancestor// struct Edge{// int to;// Edge(int to):to(to){}// };// using Graph = vector<vector<Edge>>;// class lca {// public:// const int n = 0;// const int log2_n = 0;// vector<vector<int>> parent;// vector<int> depth;// lca() {}// //g:グラフ root:根// lca(const Graph &g, int root)// : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, vector<int>(n)), depth(n) {// dfs(g, root, -1, 0);// for (int k = 0; k + 1 < log2_n; k++) {// for (int v = 0; v < (int)g.size(); v++) {// if (parent[k][v] < 0)// parent[k + 1][v] = -1;// else// parent[k + 1][v] = parent[k][parent[k][v]];// }// }// }// void dfs(const Graph &g, int v, int p, int d) {// parent[0][v] = p;// depth[v] = d;// for (auto &e : g[v]) {// if (e.to != p) dfs(g, e.to, v, d + 1);// }// }// //uとvのlcaを取得// int get(int u, int v) {// if (depth[u] > depth[v]) swap(u, v);// for (int k = 0; k < log2_n; k++) {// if ((depth[v] - depth[u]) >> k & 1) {// v = parent[k][v];// }// }// if (u == v) return u;// for (int k = log2_n - 1; k >= 0; k--) {// if (parent[k][u] != parent[k][v]) {// u = parent[k][u];// v = parent[k][v];// }// }// return parent[0][u];// }// int dep(int i) {// return depth[i];// }// int dist(int u,int v){// return depth[u]+depth[v]-depth[get(u,v)]*2;// }// };// union by size + path havingclass UnionFind {public:vector <ll> par; // 各元の親を表す配列vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)// ConstructorUnionFind(ll sz_): par(sz_), siz(sz_, 1LL) {for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}void init(ll sz_) {par.resize(sz_);siz.assign(sz_, 1LL); // resize だとなぜか初期化されなかったfor (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身}// Member Function// Findll root(ll x) { // 根の検索while (par[x] != x) {x = par[x] = par[par[x]]; // x の親の親を x の親とする}return x;}// Union(Unite, Merge)bool merge(ll x, ll y) {x = root(x);y = root(y);if (x == y) return false;// merge technique(データ構造をマージするテク.小を大にくっつける)if (siz[x] < siz[y]) swap(x, y);siz[x] += siz[y];par[y] = x;return true;}bool issame(ll x, ll y) { // 連結判定return root(x) == root(y);}ll size(ll x) { // 素集合のサイズreturn siz[root(x)];}};// 0-indexed parmutation onlyvvl cycle_partition(const vl &p){ll n=p.size();vvl ret;vector<bool> check(n,false);rep(i,n)if(!check[p[i]]){vl v;ll pos=p[i];v.pb(i);check[i]=true;while(pos!=i){v.pb(pos);check[pos]=true;pos=p[pos];}ret.pb(v);}return ret;}vl Z_algorithm(vl s){ll c=0,n=s.size();vl Z(n,0);for(ll i=1;i<n;i++){ll l=i-c;if(i+Z[l]<c+Z[c]){Z[i]=Z[l];}else{ll j=max(0LL,c+Z[c]-i);while(i+j<n && s[j]==s[i+j])j++;Z[i]=j;c=i;}}Z[0]=n;return Z;}//Manachar 修理中// vl Manachar(string S){// ll c=0,n=S.size();// vl R(n,1);// for(ll i=0;i<n;i++){// ll l=c-(i-c);// if(i+R[l]<c+R[c]){// R[i]=R[l];// }else{// ll j=c+R[c]-i;// while(i-j>=0 && i+j<n && S[i-j] == S[i+j])j++;// R[i]=j;// c=i;// }// }// return R;// }template <typename T>T pow(T a, long long n, T e = 1) {T ret = e;while (n) {if (n & 1) ret *= a;a *= a;n >>= 1;}return ret;}template <int mod>struct ModInt {int x;ModInt() : x(0) {}ModInt(long long x_) {if ((x = x_ % mod + mod) >= mod) x -= mod;}ModInt& operator+=(ModInt rhs) {if ((x += rhs.x) >= mod) x -= mod;return *this;}ModInt& operator-=(ModInt rhs) {if ((x -= rhs.x) < 0) x += mod;return *this;}ModInt& operator*=(ModInt rhs) {x = (unsigned long long)x * rhs.x % mod;return *this;}ModInt& operator/=(ModInt rhs) {x = (unsigned long long)x * rhs.inv().x % mod;return *this;}ModInt operator-() const { return -x < 0 ? mod - x : -x; }ModInt operator+(ModInt rhs) const { return ModInt(*this) += rhs; }ModInt operator-(ModInt rhs) const { return ModInt(*this) -= rhs; }ModInt operator*(ModInt rhs) const { return ModInt(*this) *= rhs; }ModInt operator/(ModInt rhs) const { return ModInt(*this) /= rhs; }bool operator==(ModInt rhs) const { return x == rhs.x; }bool operator!=(ModInt rhs) const { return x != rhs.x; }ModInt inv() const { return pow(*this, mod - 2); }friend ostream& operator<<(ostream& s, ModInt<mod> a) {s << a.x;return s;}friend istream& operator>>(istream& s, ModInt<mod>& a) {s >> a.x;return s;}};using mint = ModInt<MOD>;typedef vector<mint> vm;typedef vector<vector<mint> >vvm;typedef vector<vector<vector<mint> > >vvvm;template <typename T>struct segment_tree_beats{int N;vector<T> max1, max2, min1, min2, add, sum;vector<int> maxc, minc, len;void update_max(int i, T x){sum[i] += (x - max1[i]) * maxc[i];if (max1[i] == min1[i]){min1[i] = x;} else if (max1[i] == min2[i]){min2[i] = x;}max1[i] = x;}void update_min(int i, T x){sum[i] += (x - min1[i]) * minc[i];if (min1[i] == max1[i]){max1[i] = x;} else if (min1[i] == max2[i]){max2[i] = x;}min1[i] = x;}void update_add(int i, T x){max1[i] += x;if (max2[i] != -INF){max2[i] += x;}min1[i] += x;if (min2[i] != INF){min2[i] += x;}sum[i] += x * len[i];add[i] += x;}void push(int i){if (i >= N - 1){return;}int l = i * 2 + 1;int r = i * 2 + 2;if (add[i] != 0){update_add(l, add[i]);update_add(r, add[i]);add[i] = 0;}if (max1[i] < max1[l]){update_max(l, max1[i]);}if (min1[i] > min1[l]){update_min(l, min1[i]);}if (max1[i] < max1[r]){update_max(r, max1[i]);}if (min1[i] > min1[r]){update_min(r, min1[i]);}}void update(int i){int l = i * 2 + 1;int r = i * 2 + 2;sum[i] = sum[l] + sum[r];if (max1[l] > max1[r]){max1[i] = max1[l];max2[i] = max(max2[l], max1[r]);maxc[i] = maxc[l];} else if (max1[l] < max1[r]){max1[i] = max1[r];max2[i] = max(max1[l], max2[r]);maxc[i] = maxc[r];} else {max1[i] = max1[l];max2[i] = max(max2[l], max2[r]);maxc[i] = maxc[l] + maxc[r];}if (min1[l] < min1[r]){min1[i] = min1[l];min2[i] = min(min2[l], min1[r]);minc[i] = minc[l];} else if (min1[l] > min1[r]){min1[i] = min1[r];min2[i] = min(min1[l], min2[r]);minc[i] = minc[r];} else {min1[i] = min1[l];min2[i] = min(min2[l], min2[r]);minc[i] = minc[l] + minc[r];}}segment_tree_beats(vector<T> A){int n = A.size();N = 1;while (N < n){N *= 2;}max1 = vector<T>(N * 2 - 1, -INF);max2 = vector<T>(N * 2 - 1, -INF);min1 = vector<T>(N * 2 - 1, INF);min2 = vector<T>(N * 2 - 1, INF);add = vector<T>(N * 2 - 1, 0);sum = vector<T>(N * 2 - 1, 0);maxc = vector<int>(N * 2 - 1, 1);minc = vector<int>(N * 2 - 1, 1);len = vector<int>(N * 2 - 1, 1);for (int i = 0; i < n; i++){max1[N - 1 + i] = A[i];min1[N - 1 + i] = A[i];sum[N - 1 + i] = A[i];}for (int i = N - 2; i >= 0; i--){len[i] = len[i * 2 + 1] + len[i * 2 + 2];update(i);}}void range_chmin(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l || x >= max1[i]){return;} else if (L <= l && r <= R && x > max2[i]){update_max(i, x);return;}push(i);int m = (l + r) / 2;range_chmin(L, R, x, i * 2 + 1, l, m);range_chmin(L, R, x, i * 2 + 2, m, r);update(i);}void range_chmax(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l || x <= min1[i]){return;} else if (L <= l && r <= R && x < min2[i]){update_min(i, x);return;}push(i);int m = (l + r) / 2;range_chmax(L, R, x, i * 2 + 1, l, m);range_chmax(L, R, x, i * 2 + 2, m, r);update(i);}void range_add(int L, int R, T x, int i, int l, int r){if (r <= L || R <= l){return;} else if (L <= l && r <= R){update_add(i, x);return;}push(i);int m = (l + r) / 2;range_add(L, R, x, i * 2 + 1, l, m);range_add(L, R, x, i * 2 + 2, m, r);update(i);}T range_sum(int L, int R, int i, int l, int r){if (r <= L || R <= l){return 0;} else if (L <= l && r <= R){return sum[i];}push(i);int m = (l + r) / 2;return range_sum(L, R, i * 2 + 1, l, m) + range_sum(L, R, i * 2 + 2, m, r);}void range_chmin(int L, int R, T x){range_chmin(L, R, x, 0, 0, N);}void range_chmax(int L, int R, T x){range_chmax(L, R, x, 0, 0, N);}void range_add(int L, int R, T x){range_add(L, R, x, 0, 0, N);}T range_sum(int L, int R){return range_sum(L, R, 0, 0, N);}};struct PartiallyPersistentUnionFind {vector<ll> par, last;vector<vector<P> > history;PartiallyPersistentUnionFind(ll n) : par(n, -1), last(n, -1), history(n) {for (auto &vec : history) vec.emplace_back(-1, -1);}void init(ll n) {par.assign(n, -1); last.assign(n, -1); history.assign(n, vector<P>());for (auto &vec : history) vec.emplace_back(-1, -1);}ll root(ll t, ll x) {if (last[x] == -1 || t < last[x]) return x;return root(t, par[x]);}bool issame(ll t, ll x, ll y) {return root(t, x) == root(t, y);}bool merge(ll t, ll x, ll y) {x = root(t, x); y = root(t, y);if (x == y) return false;if (par[x] > par[y]) swap(x, y); // merge techniquepar[x] += par[y];par[y] = x;last[y] = t;history[x].emplace_back(t, par[x]);return true;}ll size(ll t, ll x) {x = root(t, x);return -prev(lower_bound(history[x].begin(), history[x].end(), make_pair(t, 0LL)))->second;}};// matrixtemplate<class T> struct Matrix {vector<vector<T> > val;Matrix(int n = 1, int m = 1, T v = 0) : val(n, vector<T>(m, v)) {}void init(int n, int m, T v = 0) {val.assign(n, vector<T>(m, v));}void resize(int n, int m) {val.resize(n);for (int i = 0; i < n; ++i) val[i].resize(m);}Matrix<T>& operator = (const Matrix<T> &A) {val = A.val;return *this;}size_t size() const {return val.size();}vector<T>& operator [] (int i) {return val[i];}const vector<T>& operator [] (int i) const {return val[i];}friend ostream& operator << (ostream& s, const Matrix<T>& M) {s << endl;for (int i = 0; i < (int)M.size(); ++i) s << M[i] << endl;return s;}};template<class T> Matrix<T> operator * (const Matrix<T> &A, const Matrix<T> &B) {Matrix<T> R(A.size(), B[0].size());for (int i = 0; i < A.size(); ++i)for (int j = 0; j < B[0].size(); ++j)for (int k = 0; k < B.size(); ++k)R[i][j] += A[i][k] * B[k][j];return R;}template<class T> Matrix<T> pow(const Matrix<T> &A, long long n) {Matrix<T> R(A.size(), A.size());auto B = A;for (int i = 0; i < A.size(); ++i) R[i][i] = 1;while (n > 0) {if (n & 1) R = R * B;B = B * B;n >>= 1;}return R;}template<class T> vector<T> operator * (const Matrix<T> &A, const vector<T> &B) {vector<T> v(A.size());for (int i = 0; i < A.size(); ++i)for (int k = 0; k < B.size(); ++k)v[i] += A[i][k] * B[k];return v;}template<class T> Matrix<T> operator + (const Matrix<T> &A, const Matrix<T> &B) {Matrix<T> R(A.size(), A[0].size());for (int i = 0; i < A.size(); ++i)for (int j = 0; j < A[0].size(); ++j)R[i][j] = A[i][j] + B[i][j];return R;}template<class T> Matrix<T> operator - (const Matrix<T> &A, const Matrix<T> &B) {Matrix<T> R(A.size(), A[0].size());for (int i = 0; i < A.size(); ++i)for (int j = 0; j < A[0].size(); ++j)R[i][j] = A[i][j] - B[i][j];return R;}const int MAX_ROW = 510; // to be set appropriatelyconst int MAX_COL = 510; // to be set appropriatelystruct BitMatrix {int H, W;bitset<MAX_COL> val[MAX_ROW];BitMatrix(int m = 1, int n = 1) : H(m), W(n) {}inline bitset<MAX_COL>& operator [] (int i) {return val[i];}};int GaussJordan(BitMatrix &A, bool is_extended = false) {int rank = 0;for (int col = 0; col < A.W; ++col) {if (is_extended && col == A.W - 1) break;int pivot = -1;for (int row = rank; row < A.H; ++row) {if (A[row][col]) {pivot = row;break;}}if (pivot == -1) continue;swap(A[pivot], A[rank]);for (int row = 0; row < A.H; ++row) {if (row != rank && A[row][col]) A[row] ^= A[rank];}++rank;}return rank;}int linear_equation(BitMatrix A, vector<int> b, vector<int> &res) {int m = A.H, n = A.W;BitMatrix M(m, n + 1);for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) M[i][j] = A[i][j];M[i][n] = b[i];}int rank = GaussJordan(M, true);// check if it has no solutionfor (int row = rank; row < m; ++row) if (M[row][n]) return -1;// answerres.assign(n, 0);for (int i = 0; i < rank; ++i) res[i] = M[i][n];return rank;}// struct edge{// ll to;// ll cost;// };// using graph = vector<vector<edge> >;// const ll MAX_V=200200;// graph G(MAX_V);// vl d(MAX_V);// void dijkstra(ll n,ll s) {// minpq<P>q;// rep(i,n)d[i]=INF;// d[s]= 0LL;// q.push({0LL, s});// while (!q.empty()) {// auto p = q.top();// q.pop();// ll cur = p.second;// //d[cur]が二度以上更新されている場合に、初期のものをskipする// //これがないと一つの頂点につき高々一回更新されるという前提が破滅// if(d[cur]<p.first)continue;// for(auto e:G[cur]) {// if (d[e.to] > d[cur]+e.cost) {// d[e.to]=d[cur]+e.cost;// q.push({d[e.to], e.to});// }// }// }// }int main(){ios::sync_with_stdio(false);std::cin.tie(nullptr);cout << fixed << setprecision(12);/*--------------------------------*/ll n;cin>>n;vvm dp(n+5,vm(4));dp[0][0]=1;rep(i,n){rep(j,4){rep(k,4){if(k==0)continue;if(j==k)continue;dp[i+k][k]+=dp[i][j];}}}cout<<dp[n][0]+dp[n][1]+dp[n][2]+dp[n][3]<<endl;}