結果
| 問題 | No.639 An Ordinary Sequence |
| ユーザー |
 warabi0906
|
| 提出日時 | 2023-07-02 10:57:26 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 44 ms / 1,000 ms |
| コード長 | 28,839 bytes |
| コンパイル時間 | 3,305 ms |
| コンパイル使用メモリ | 218,580 KB |
| 実行使用メモリ | 85,960 KB |
| 最終ジャッジ日時 | 2024-07-16 07:01:58 |
| 合計ジャッジ時間 | 3,975 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 29 ms
85,876 KB |
| testcase_01 | AC | 29 ms
85,816 KB |
| testcase_02 | AC | 29 ms
85,820 KB |
| testcase_03 | AC | 28 ms
85,820 KB |
| testcase_04 | AC | 30 ms
85,848 KB |
| testcase_05 | AC | 28 ms
85,760 KB |
| testcase_06 | AC | 30 ms
85,760 KB |
| testcase_07 | AC | 30 ms
85,760 KB |
| testcase_08 | AC | 44 ms
85,776 KB |
| testcase_09 | AC | 30 ms
85,864 KB |
| testcase_10 | AC | 29 ms
85,748 KB |
| testcase_11 | AC | 29 ms
85,888 KB |
| testcase_12 | AC | 29 ms
85,760 KB |
| testcase_13 | AC | 29 ms
85,760 KB |
| testcase_14 | AC | 29 ms
85,888 KB |
| testcase_15 | AC | 30 ms
85,740 KB |
| testcase_16 | AC | 29 ms
85,776 KB |
| testcase_17 | AC | 30 ms
85,920 KB |
| testcase_18 | AC | 30 ms
85,960 KB |
ソースコード
/*
Hi,I am warabi.
Welcome to my coding space.
Let me give you a great word of advice.
"The pen is mightier than the sword"
-by Edward Bulwer-Lytton
_,,....,,_ ＿人人人人人人人人人人人人人人人人人人＿
-''":::::::::::::｀''＞ ゆっくりできるとでも? ＜
ヽ:::::::::::::::::::::￣^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ^Ｙ￣
|::::::;ノ´￣＼:::::::::::＼_,. -‐ｧ ＿_ _____ ＿_____
|::::ﾉ ヽ､ヽr-r'"´ （.__ ,´ _,, '-´￣￣｀-ゝ 、_ イ、
_,.!イ_ _,.ﾍｰｧ'二ﾊ二ヽ､へ,_7 'r ´ ヽ、ﾝ、
::::::rｰ''7ｺ-‐'"´ ; ', ｀ヽ/｀7 ,'＝=─- -─=＝', i
r-'ｧ'"´/ /! ﾊ ハ ! iヾ_ﾉ i ｲ iゝ、ｲ人レ／_ルヽｲ i |
!イ´ ,' | /__,.!/ V ､!__ﾊ ,' ,ゝ ﾚﾘｲi (ﾋ_] ﾋ_ﾝ ).| .|、i .||
`! !/ﾚi' (ﾋ_] ﾋ_ﾝ ﾚ'i ﾉ !Y!"" ,＿__, "" 「 !ﾉ i |
,' ﾉ !'" ,＿__, "' i .ﾚ' L.',. ヽ _ﾝ L」 ﾉ| .|
（ ,ﾊ ヽ _ﾝ 人! | ||ヽ、 ,ｲ| ||ｲ| /
,.ﾍ,）､ ）＞,､ _____, ,.イ ハ レ ル｀ ー--─ ´ルﾚ ﾚ´
Take your time.
GIVE ME AC!!!!!!!!!!!!!!!!!!!!!!!!!
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define V vector
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define brep(i,a,b) for(ll i=a;i>=b;i--)
#define reph(i,vec) for(auto &i:vec)
#define FI first
#define SE second
#define P pair
#define PB push_back
#define EB emplace_back
#define INS insert
#define all(vec) vec.begin(),vec.end()
#define in(name) ll name;cin >> name
#define ins(name) string name;cin >> name;
#define inc(name) char name;cin >> name
#define ing(name,size,E) vector<vector<ll>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);name[b].PB(a);}
#define ing_on(name,size,E) vector<vector<long long>> name(size);rep(i,0,E){in(a);in(b);a--;b--;name[a].PB(b);}
#define ing_cost(name,size,E) vector<vector<P<ll,ll>>> name(size);rep(i,0,E){in(a);in(b);in(c);a--;b--;name[a].PB({b,c});name[b].PB({a,c});}
#define invll(name,size) vector<ll> name(size);reph(i,name)cin >> i
#define invvll(name,size1,size2) vector<vector<long long>> name(size1,vector<long long>(size2));reph(v,name)reph(i,v)cin>>i;
#define invp(name,size) vector<P<ll,ll>> name(size);for(ll i=0;i<size;i++)cin >> name[i].FI >> name[i].SE
#define out(n) cout << (n) << endl
#define _out(n) cout << " " << (n) << endl;
#define notout(n) cout << (n)
#define out_(n) cout << (n) << " "
#define set_out(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_notout(n,k) cout << fixed << setprecision(k) << (n) << endl;
#define set_out_(n,k) cout << fixed << setprecision(k) << (n) << " ";
#define vout(vec) for(int i=0;i<vec.size();i++)cout<<(i?" ":"")<<(vec[i]);cout<<endl;
#define nel cout<<endl;
#define getbit(n,k) (((1LL<<(k))&(n))>0)
#define g_t(t,a) get<a>(t)
#define INF 1000000000000000000ll
#define MOD 1000000007
#define MOD2 998244353
#define CMOD MOD2
#define EPS 0.00000001
//debug
#define bug assert(false);
#define debug cout<<"OK Line "<<__LINE__<<endl;
//
//constexpr long double PI=3.14159265358979323846;
//template
template<typename T>
inline bool chmax(T& a, const T b) { if (a < b) { a = b; return true; }return false; }
template<typename T>
inline bool chmin(T& a, const T b) { if (a > b) { a = b; return true; }return false; }
//
namespace Warabi {
//常備変数のコーナー
V<bool> primes(1e7+5, true);
V<ll> prime_list;
V<ll> prime_rui(1e7+5, 0LL);
V<bool> visiteded(300100);
V<bool> afed(300100, false);
V<ll> k1(200100, 0ll);
V<ll> k2(200100, 0ll);
//
//常備構造体宣言のコーナー
class UnionFind {
private:
ll NumberOfElements;
ll Not1NumberOfelements;
public:
vector<ll> par;
vector<ll> SIZE;
void init(ll sz) {
par.resize(sz, -1LL);
SIZE.resize(sz, 1LL);
NumberOfElements = sz;
Not1NumberOfelements = 0ll;
}
ll root(ll pos) {
if (par[pos] == -1) return pos;
par[pos] = root(par[pos]);
return par[pos];
}
bool same(ll u, ll v) {
if (root(u) == root(v)) return true;
return false;
}
ll SZ(ll u) {
return SIZE[root(u)];
}
ll noe() {
return NumberOfElements;
}
ll nnoe() {
return Not1NumberOfelements;
}
bool unite(ll u, ll v) {
u = root(u); v = root(v);
if (u == v) {
return false;
}
if (SZ(u) == 1LL and SZ(v) == 1LL)Not1NumberOfelements++;
if (u < v)swap(u, v);
par[u] = v;
SIZE[v] += SIZE[u];
NumberOfElements--;
return true;
}
};
class SCC {
public:
V<V<ll>> G;
V<V<ll>> UG;
V<ll> order;
V<ll> GROUP;
V<bool> visited;
ll sz_count;
V<ll> groupsize;
void init(ll sz) {
G.resize(sz, V<ll>(0));
UG.resize(sz, V<ll>(0));
GROUP.resize(sz, -1ll);
visited.resize(sz, false);
sz_count = 0LL;
return;
}
void dfs(ll now) {
visited[now] = true;
reph(i, G[now]) {
if (visited[i])continue;
dfs(i);
}
order.PB(now);
return;
}
void dfs2(ll now, ll group) {
GROUP[now] = group;
sz_count++;
reph(i, UG[now]) {
if (GROUP[i] != -1ll and GROUP[i] != group)continue;
if (GROUP[i] != -1ll)continue;
dfs2(i, group);
}
return;
}
void make_group(V<V<ll>> Graph_function) {
G = Graph_function;
rep(i, 0, (ll)G.size()) {
reph(j, G[i]) {
UG[j].PB(i);
}
}
rep(i, 0, (ll)G.size()) {
if (visited[i])continue;
dfs(i);
}
reverse(all(order));
ll now_group = 0LL;
reph(i, order) {
if (GROUP[i] != -1)continue;
ll prev = sz_count;
dfs2(i, now_group);
now_group++;
groupsize.PB(sz_count - prev);
}
return;
}
};
template<typename X, typename M>
class SegmentTree {
public:
long long sz;
using FX = function<X(X, X)>;
using FA = function<X(X, M)>;
using FM = function<M(M, M)>;
const FX fx;
const FA fa;
const FM fm;
const X ex;
const M em;
vector<X> node;
vector<M> lazy;
SegmentTree(long long sz_, FX fx_, FA fa_, FM fm_, X ex_, M em_) :sz(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_) {
long long n = 1LL;
while (n < sz_)n *= 2;
sz = n;
node.resize(sz * 2 - 1, ex);
lazy.resize(sz * 2 - 1, em);
}
void set(long long index, X x) {
node[index + sz - 1] = x;
return;
}
void build() {
for (int i = sz - 2; i >= 0; i--)node[i] = fx(node[i * 2 + 1], node[i * 2 + 2]);
return;
}
void eval(long long k) {
if (lazy[k] == em)return;
if (k < sz - 1) {
lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
}
node[k] = fa(node[k], lazy[k]);
lazy[k] = em;
}
void update_sub(long long a, long long b, M x, long long k, long long l, long long r) {
//cout << " " << a << " " << b << " " << l << " " << r << endl;
eval(k);
if (a <= l and r <= b) {
lazy[k] = fm(lazy[k], x);
//cout<<" "<<lazy[k]<<endl;
eval(k);
return;
}
else if (a < r and l < b) {
update_sub(a, b, x, k * 2 + 1, l, (l + r) / 2);
update_sub(a, b, x, k * 2 + 2, (l + r) / 2, r);
node[k] = fx(node[k * 2 + 1], node[k * 2 + 2]);
return;
}
return;
}
void update(long long a, long long b, M x) {
update_sub(a, b, x, 0LL, 0LL, sz);
return;
}
void add_sub(long long a, X x, long long k, long long l, long long r) {
eval(k);
node[k] += x;
if (k < sz - 1) {
long long mid = (l + r) / 2;
if (a < mid)add_sub(a, x, k * 2 + 1, l, mid);
else add_sub(a, x, k * 2 + 2, mid, r);
}
return;
}
void add(long long a, X x) {
add_sub(a, x, 0LL, 0LL, sz);
}
X query_sub(long long a, long long b, long long k, long long l, long long r) {
eval(k);
if (r <= a or b <= l)return ex;
else if (a <= l and r <= b)return node[k];
else {
X Xl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X Xr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
//cout<<" / "<<Xl<<" "<<Xr<<endl;
return fx(Xl, Xr);
}
}
X query(long long a, long long b) {
return query_sub(a, b, 0LL, 0LL, sz);
}
inline X operator [] (long long index) {
return query(index, index + 1);
}
};
template<typename T>
class multimap {
private:
map<T, ll> mp;
public:
void add(ll x) {
mp[x]++;
return;
}
void del(ll x) {
mp[x]--;
if (mp[x] < 1)mp.erase(x);
return;
}
T maximum() {
return mp.rbegin()->first;
}
T minimum() {
return mp.begin()->first;
}
};
class LCA {
public:
vector<vector<long long>> parent;
vector<long long> dist;
vector<vector<long long>> G;
LCA(const vector<vector<long long>>& gr) { init(gr); }
void dfs(long long v, long long p, long long d) {
parent[0][v] = p;
dist[v] = d;
for (long long next : G[v]) {
if (next == p)continue;
dfs(next, v, d + 1);
}
return;
}
void init(const vector<vector<long long>>& gr) {
G = gr;
parent.assign(33, vector<long long>(G.size(), -1LL));
dist.assign(G.size(), -1LL);
dfs(0LL, -1LL, 0LL);
for (int i = 0; i < 32; i++) {
for (int j = 0; j < (int)G.size(); j++) {
if (parent[i][j] < 0LL) {
parent[i + 1][j] = -1LL;
}
else {
parent[i + 1][j] = parent[i][parent[i][j]];
}
}
}
return;
}
long long lca(long long u, long long v) {
if (dist[u] < dist[v])swap(u, v);
long long between = dist[u] - dist[v];
for (int i = 0; i < 33; i++) {
if (between & (1LL << i)) { u = parent[i][u]; }
}
if (u == v)return u;
for (int i = 32; i >= 0; i--) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
assert(parent[0][u] == parent[0][v]);
return parent[0][u];
}
long long get_dist(long long u, long long v) {
return dist[u] + dist[v] - 2 * dist[lca(u, v)];
}
bool on_path(long long u, long long v, long long a) {
return get_dist(u, v) == get_dist(u, a) + get_dist(v, a);
}
};
class nCk {
public:
const long long m;
const long long MAXIMUM = 2000005;
vector<long long> fac, facinv, inv;
nCk(long long m_);
~nCk();
long long com(long long n, long long k)const;
};
nCk::nCk(long long m_) :m(m_) {
fac.resize(MAXIMUM + 3);
facinv.resize(MAXIMUM + 3);
inv.resize(MAXIMUM + 3);
fac[0] = fac[1] = 1;
facinv[0] = facinv[1] = 1;
inv[1] = 1;
for (long long i = 2; i < MAXIMUM + 2; i++) {
fac[i] = fac[i - 1] * i % m;
inv[i] = m - inv[m % i] * (m / i) % m;
facinv[i] = facinv[i - 1] * inv[i] % m;
}
}
nCk::~nCk() {}
long long nCk::com(long long n, long long k)const {
if (k == 0)return 1;
if (n < k)return 0LL;
assert(!(n < 0 || k < 0));
return fac[n] * (facinv[k] * facinv[n - k] % m) % m;
}
//
//常備構造体宣言のコーナー
//
//常備関数のコーナー
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
//木の直径を求める
tuple<ll,ll,ll> Cdiameter(V<V<P<ll, ll>>> G, ll start, bool type) {
visiteded = afed;
queue<ll> sirabe;
sirabe.push(start);
V<ll> short_load(G.size(), 0LL);
while (!sirabe.empty()) {
ll s = sirabe.front();
sirabe.pop();
visiteded[s] = true;
reph(i, G[s]) {
if (visiteded[i.FI])continue;
short_load[i.FI] = short_load[s] + i.SE;
sirabe.push(i.FI);
}
}
ll far_max = -1LL;
ll element = -1LL;
rep(i, 0, (ll)G.size()) {
if (far_max >= short_load[i])continue;
far_max = short_load[i];
element = i;
}
if (type)return Cdiameter(G, element, false);
else return { start,element,far_max };
}
//素数の取得
void prime_init() {
const int Limit=1e7+5;
V<bool> at(Limit, true);
primes = at;
primes[0] = primes[1] = false;
rep(i, 2, Limit) {
if (!primes[i])continue;
for (ll j = i * 2; j <= Limit; j += i)primes[j] = false;
}
rep(i, 1, Limit) {
if (primes[i]) {
prime_list.PB(i);
prime_rui[i] = prime_rui[i - 1] + 1;
}
else {
prime_rui[i] = prime_rui[i - 1];
}
}
return;
}
//modpow
long long modpow(long long a, long long b, long long m) {
long long p = 1, q = a;
for (int i = 0; i < 63; i++) {
if ((b & (1LL << i)) != 0) {
p *= q;
p %= m;
}
q *= q;
q %= m;
}
return p;
}
//逆元
long long Div(long long a, long long b, long long m) {
return (a * modpow(b, m - 2, m)) % m;
}
//点と点の距離を返す
long double Dis(ll ax, ll ay, ll bx, ll by) {
return sqrt(pow(ax - bx, 2) + pow(ay - by, 2));
}
//二つのベクトルから平行四辺形の面積を返す
ll he(ll x0, ll y0, ll x1, ll y1, ll x2, ll y2) {//外積を二で割る
return abs((x1 - x0) * (y2 - y0) - (x2 - x0) * (y1 - y0));
}
//
template<typename T>
ll Lis_size(V<T> arr, ll sz) {
const T TINF = numeric_limits<T>::max();
V<T> DP(sz + 1, TINF);
DP[0] = -TINF;
rep(i, 0, sz) {
*lower_bound(all(DP), arr[i]) = arr[i];
}
ll ans = 0LL;
rep(i, 1, sz + 1) {
if (DP[i] != TINF)ans = i;
}
return ans;
}
string toBinary(ll n) {
string r;
while (n != 0LL) {
r += (n % 2LL == 0LL ? "0" : "1");
n /= 2LL;
}
return r;
}
template<typename T>
V<ll> press(V<T> arr) {
V<T> X = arr;
sort(all(X));
X.erase(unique(all(X)), X.end());
V<ll> ans(arr.size());
rep(i, 0LL, (ll)arr.size()) {
ans[i] = lower_bound(all(X), arr[i]) - X.begin();
}
return ans;
}
P<V<V<ll>>, V<V<P<ll, ll>>>> warshall_floyd(ll N, V<V<P<ll, ll>>> G) {
V<V<ll>> DP(N, V<ll>(N, INF));
rep(i, 0, N)DP[i][i] = 0LL;
V<V<P<ll, ll>>> prev(N, V<P<ll, ll>>(N, { INF,INF }));
rep(i, 0, N) {
reph(j, G[i]) {
DP[i][j.FI] = j.SE;
prev[i][j.FI] = { i,j.FI };
}
}
rep(k, 0, N) {
rep(i, 0, N) {
rep(j, 0, N) {
if (chmin(DP[i][j], DP[i][k] + DP[k][j])) {
prev[i][j] = prev[k][j];
}
}
}
}
return { DP,prev };
}
template<typename T>
void to_sum(V<T>& arr) {
rep(i, 0, (ll)arr.size() - 1LL) {
arr[i + 1] += arr[i];
}
return;
}
template<typename T>
void including_map(ll H, ll W, V<V<T>>& G, T c) {
V<V<T>> new_G(H + 2, V<T>(W + 2));
rep(i, 0, W + 2)new_G[0][i] = c;
rep(i, 1, H + 1) {
new_G[i][0] = c;
new_G[i][W + 1] = c;
rep(j, 1, W + 1) {
new_G[i][j] = G[i - 1][j - 1];
}
}
rep(i, 0, W + 2)new_G[H + 1][i] = c;
G = new_G;
return;
}
template<typename T> class BIT {
private:
int n;
vector<T> bit;
public:
// 0_indexed で i 番目の要素に x を加える
void add(int i, T x){
i++;
while(i < n){
bit[i] += x, i += i & -i;
}
}
// 0_indexed で [0,i] の要素の和(両閉区間！！)
T sum(int i){
i++;
T s = 0;
while(i > 0){
s += bit[i], i -= i & -i;
}
return s;
}
BIT(){}
//初期値がすべて0の場合
BIT(int sz) : n(sz+1), bit(n, 0){}
BIT(const vector<T>& v) : n((int)v.size()+1), bit(n, 0){
for(int i = 0; i < n-1; i++){
add(i,v[i]);
}
}
void print(){
for(int i = 0; i < n-1; i++){
cout << sum(i) - sum(i-1) << " ";
}
cout << "\n";
}
//-1スタート
void print_sum(){
for(int i = 0; i < n; i++){
cout << sum(i-1) << " ";
}
cout << "\n";
}
};
// u を昇順にソートするのに必要な交換回数(転倒数) (u は {0,..., n-1} からなる重複を許した長さ n の数列)
long long inv_count(const vector<long long>& u,const int Size)
{
int n=u.size();
int m=Size;
BIT<long long> bt(m);
long long ans = 0;
for(int i = 0; i < n; i++){
ans += i - bt.sum(u[i]);
bt.add(u[i], 1);
}
return ans;
}
set<ll> factor(ll N) {
set<ll> ans;
for (ll i = 1LL; i * i <= N; i++) {
if (N % i)continue;
ans.INS(i);
ans.INS(N / i);
}
return ans;
}
V<ll> dijkstra(ll sz, V<V<P<ll, ll>>> G, ll s) {
V<ll> ans(sz, INF); ans[s] = 0LL;
priority_queue<P<ll, ll>, vector<P<ll, ll>>, greater<P<ll, ll>>> examine;
examine.push({ 0LL,s });
while (examine.size()) {
P<ll, ll> p = examine.top();
examine.pop();
ll now = p.SE, dist = p.FI;
if (ans[now] < dist)continue;
reph(i, G[now]) {
ll next = i.FI, c = i.SE;
if (chmin(ans[next], dist + c)) {
examine.push({ dist + c,next });
}
}
}
return ans;
}
V<ll> pass(const V<V<ll>>& G, ll s, ll t) {
V<ll> ans, res;
function<void(ll,ll)> dfs = [&](ll now,ll p) {
res.PB(now);
if (now == t) {
ans = res;
}
reph(next, G[now]) {
if (next==p)continue;
dfs(next,now);
}
res.pop_back();
return;
};
dfs(s,-1);
return ans;
}
// 負の数にも対応した mod (a = -11 とかでも OK)
inline long long mod(long long a, long long m) {
long long res = a % m;
if (res < 0) res += m;
return res;
}
// 拡張 Euclid の互除法
long long extGCD(long long a, long long b, long long& p, long long& q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGCD(b, a % b, q, p);
q -= a / b * p;
return d;
}
long long extGcd(long long a, long long b, long long& p, long long& q) {
if (b == 0) { p = 1; q = 0; return a; }
long long d = extGcd(b, a % b, q, p);
q -= a / b * p;
return d;
}
// 逆元計算 (ここでは a と m が互いに素であることが必要)
long long modinv(long long a, long long m) {
long long x, y;
extGCD(a, m, x, y);
return mod(x, m); // 気持ち的には x % m だが、x が負かもしれないので
}
// Garner のアルゴリズム, x%MOD, LCM%MOD を求める (m は互いに素でなければならない)
// for each step, we solve "coeffs[k] * t[k] + constants[k] = b[k] (mod. m[k])"
// coeffs[k] = m[0]m[1]...m[k-1]
// constants[k] = t[0] + t[1]m[0] + ... + t[k-1]m[0]m[1]...m[k-2]
long long Garner(vector<long long> b, vector<long long> m, long long Mmod) {
m.push_back(Mmod); // banpei
vector<long long> coeffs((int)m.size(), 1);
vector<long long> constants((int)m.size(), 0);
for (int k = 0; k < (int)b.size(); ++k) {
long long t = mod((b[k] - constants[k]) * modinv(coeffs[k], m[k]), m[k]);
for (int i = k + 1; i < (int)m.size(); ++i) {
(constants[i] += t * coeffs[i]) %= m[i];
(coeffs[i] *= m[k]) %= m[i];
}
}
return constants.back();
}
pair<long long, long long> ChineseRem(const vector<long long>& b, const vector<long long>& m) {
long long r = 0, M = 1;
for (int i = 0; i < (int)b.size(); ++i) {
long long p, q;
long long d = extGcd(M, m[i], p, q); // p is inv of M/d (mod. m[i]/d)
if ((b[i] - r) % d != 0) return make_pair(0, -1);
long long tmp = (b[i] - r) / d * p % (m[i] / d);
r += M * tmp;
M *= m[i] / d;
}
return make_pair(mod(r, M), M);
}
map<ll, ll> bunkai(ll n) {
map<ll, ll> ans;
ll Nn = n;
for (int i = 2; i * i <= Nn; i++) {
while (n % i == 0) {
n /= i;
ans[i]++;
}
}
if (n > 1) { ans[n]++; }
return ans;
}
template<typename T>
void RLE(vector<T>& arr) {
vector<T> res;
res.push_back(arr[0]);
for (const T t : arr) {
if (res.back() != t)res.push_back(t);
}
arr = res;
return;
}
vector<pair<long long, long long>> EulerTour(const vector<vector<long long>>& G) {
long long N = (long long)G.size();
vector<pair<long long, long long>> res(N);
long long now = 0ll;
function<void(long long, long long)> dfs = [&](long long v, long long p) {
res[v].first = now;
++now;
for (const long long next : G[v]) {
if (next == p)continue;
dfs(next, v);
}
res[v].second = now;
++now;
return;
};
dfs(0, -1ll);
return res;
}
template <typename T>
struct BIT2D {
int H, W;
vector<vector<T>> bit; // データの格納先
BIT2D(int H_, int W_) { init(H_, W_); }
void init(int H_, int W_) {
H = H_ + 1;
W = W_ + 1;
bit.assign(H, vector<T>(W, 0));
}
void add(int h, int w, T x) {
for (int i = h; i < H; i += (i & -i)) {
for (int j = w; j < W; j += (j & -j)) {
bit[i][j] += x;
}
}
}
// 1≦i≦h かつ 1≦j≦w
T sum(int h, int w) {
T s(0);
for (int i = h; i > 0; i -= (i & -i)) {
for (int j = w; j > 0; j -= (j & -j)) {
s += bit[i][j];
}
}
return s;
}
// h1≦i<h2 かつ w1≦j<w2
T query(int h1, int w1, int h2, int w2) {
return sum(h2 - 1, w2 - 1) - sum(h2 - 1, w1 - 1) - sum(h1 - 1, w2 - 1) + sum(h1 - 1, w1 - 1);
}
};
}
namespace Guest {
const int MAX_VAL = 300000;
int a[MAX_VAL]; //要素
int cnt[MAX_VAL]; //区間内のiの個数
int res; //区間内の種類の数
class Mo {
private:
vector<int> left, right;
const int width;
void add(const int id);
void del(const int id);
public:
vector<int> ans;
Mo(const int n) : width((int)sqrt(n)) {}
//クエリ[l,r)
void insert(const int l, const int r) {
left.push_back(l), right.push_back(r);
}
void solve() {
const int sz = (int)left.size();
int nl = 0, nr = 0;
vector<int> ord(sz);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](const int a, const int b) {
const int c = left[a] / width, d = left[b] / width;
return (c == d) ? ((c & 1) ? (right[b] < right[a]) : (right[a] < right[b])) : (c < d);
});
ans.resize(sz);
for (const int id : ord) {
while (nl > left[id]) add(--nl);
while (nr < right[id]) add(nr++);
while (nl < left[id]) del(nl++);
while (nr > right[id]) del(--nr);
ans[id] = res;
}
}
};
//idは元の配列のインデックス
void Mo::add(const int id)
{
res -= cnt[a[id]] / 2;
res += (++cnt[a[id]]) / 2;
}
void Mo::del(const int id)
{
res -= cnt[a[id]] / 2;
res += (--cnt[a[id]]) / 2;
}
constexpr long long mod=MOD2;
class mint {
long long x;
public:
mint(long long x=0) : x((x%mod+mod)%mod) {}
mint operator-() const {
return mint(-x);
}
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;
if (t&1) a *= *this;
return a;
}
// for prime mod
mint 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;
}
friend ostream& operator<<(ostream& os, const mint& m){
os << m.x;
return os;
}
};
}
//
long long gcd(long long a, long long b) {
if (b == 0LL)return a;
return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
return a * b / gcd(a, b);
}
signed main() {
/*
文章を読み落としていませんか?
制約も隅々まで読んでいますか?
注意
・セグ木のupdate関数はl,rの値を渡したときにl以上r未満の区間だからご注意を
rは含みません
・BITって1-indexedなんだぜ
イケてるよな
・using namespace Warabi??
*/
//using namespace Warabi;
//mintのMODは確認した?
in(N);
map<ll,ll> mp;
function<ll(ll)> f=[&](ll n){
if(mp.count(n))return mp[n];
else if(n)return mp[n]=f(n/3)+f(n/5);
else return 1ll;
};
out(f(N));
}