結果
| 問題 |
No.1747 Many Formulae 2
|
| コンテスト | |
| ユーザー |
 094
|
| 提出日時 | 2022-01-03 20:30:44 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 34,008 bytes |
| コンパイル時間 | 2,553 ms |
| コンパイル使用メモリ | 202,572 KB |
| 実行使用メモリ | 5,248 KB |
| 最終ジャッジ日時 | 2024-10-13 08:28:57 |
| 合計ジャッジ時間 | 3,488 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
// made by https://github.com/094-gengar/add_lib_to_templ
#line 2 "cpplib/_other/bit.cpp"
#define LL long long
#define bitfor(bit, n) for (LL bit = 0; bit < (1 << n); bit++)
#define bitif(bit, a) if (bit & (1 << a))
LL bitsum(LL bit)
{
LL r = 0;
for(LL i = 1; i <= bit; i <<= 1)
if(i & bit)
r++;
return r;
}
#line 2 "cpplib/_other/caesar.hpp"
#include <iostream>
struct caesar
{
char c = 'a';
int to_i() { return (caesar::c - 'a'); }
int absolute(caesar& d) { return (d.c - caesar::c + 26) % 26; }
friend std::istream& operator>>(std::istream& is, caesar& c) { is >> c.c; return is; }
friend std::ostream& operator<<(std::ostream& os, caesar& c) { return os << c.c; }
};
struct Caesar
{
char c = 'A';
int to_i() { return (Caesar::c - 'A'); }
int absolute(Caesar& d) { return (d.c - Caesar::c + 26) % 26; }
friend std::istream& operator>>(std::istream& is, Caesar& c) { is >> c.c; return is; }
friend std::ostream& operator<<(std::ostream& os, Caesar& c) { return os << c.c; }
};
#line 2 "cpplib/_other/template.hpp"
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <random>
//#define INCLUDE_BOOST
#ifdef INCLUDE_BOOST
#if __has_include(<boost/range/irange.hpp>)
#include <boost/range/irange.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/classification.hpp>
#endif
#endif
#pragma GCC target("avx512f")
#pragma GCC optimize("O3")
//#define int long long
#define LL long long
#define UL unsigned long long
#define itn int
#define INT(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define LLL(...) \
LL __VA_ARGS__; \
in(__VA_ARGS__)
#define I32(...) \
i32 __VA_ARGS__; \
in(__VA_ARGS__)
#define I64(...) \
i64 __VA_ARGS__; \
in(__VA_ARGS__)
#define U32(...) \
u32 __VA_ARGS__; \
in(__VA_ARGS__)
#define U64(...) \
u64 __VA_ARGS__; \
in(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define CHR(...) \
char __VA_ARGS__; \
in(__VA_ARGS__)
#define DBL(...) \
double __VA_ARGS__; \
in(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define Sort(x) sort(all(x))
#define rSort(x) \
sort(all(x)); \
reverse(all(x))
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
#define uniq(v) \
sort(all(v)); \
UNIQUE(v)
#define l_b(c, x) distance(c.begin(), lower_bound(all(c), (x)))
#define u_b(c, x) distance(c.begin(), upper_bound(all(c), (x)))
#define fi first
#define se second
#define mkpr make_pair
#define pb push_back
#define eb emplace_back
#define pass
#define aauto auto &&
#define cauto const auto &
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (usize i = (a), __B_SIZE__ = (b); i < __B_SIZE__; i++)
#define _per(i, n) peri(i, n, 0)
#define peri(i, a, b) for (int i = (a), __B_SIZE__ = (b); i >= __B_SIZE__; i--)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define per(...) _overload3(__VA_ARGS__, peri, _per, )(__VA_ARGS__)
#define bitshift(n) (1LL << (n))
#define myceil(a, b) ((a) + ((b)-1)) / (b)
using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;
using vi = std::vector<int>;
using vvi = std::vector<vi>;
using vLL = std::vector<LL>;
using vvLL = std::vector<vLL>;
using vb = std::vector<bool>;
using vvb = std::vector<vb>;
using vd = std::vector<double>;
using vvd = std::vector<vd>;
using vc = std::vector<char>;
using vvc = std::vector<vc>;
using vs = std::vector<std::string>;
using P = std::pair<int, int>;
using vp = std::vector<P>;
using pi32 = std::pair<i32, i32>;
using pLL = std::pair<LL, LL>;
using vpi32 = std::vector<pi32>;
using vpLL = std::vector<pLL>;
template <class T>
inline bool chmin(T& a, const T& b)
{
if(b < a)
{
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T& a, const T& b)
{
if(a < b)
{
a = b;
return true;
}
return false;
}
int Scan() { return getchar(); }
void Scan(signed& a) { scanf("%d", &a); }
void Scan(unsigned& a) { scanf("%u", &a); }
void Scan(long& a) { scanf("%ld", &a); }
void Scan(long long& a) { scanf("%lld", &a); }
void Scan(unsigned long long& a) { scanf("%llu", &a); }
void Scan(char& a)
{
do
{
a = getchar();
} while(a == ' ' || a == '\n');
}
void Scan(float& a) { scanf("%f", &a); }
void Scan(double& a) { scanf("%lf", &a); }
void Scan(long double& a) { scanf("%Lf", &a); }
void Scan(std::string& a) { std::cin >> a; }
template <class T>
void Scan(std::vector<T>&);
template <class T, class U>
void Scan(std::pair<T, U>&);
template <class T>
void Scan(std::vector<T>& a)
{
for(auto&& i : a)
Scan(i);
}
template <class T, class U>
void Scan(std::pair<T, U>& a)
{
Scan(a.first);
Scan(a.second);
}
template <class T>
void Scan(T& a) { std::cin >> a; }
void in() {}
template <class Car, class... Cdr>
void in(Car&& car, Cdr &&...cdr)
{
Scan(car);
in(std::forward<Cdr>(cdr)...);
}
void Print() { putchar(' '); }
void Print(signed a) { printf("%d", a); }
void Print(bool a) { printf("%d", a); }
void Print(unsigned a) { printf("%u", a); }
void Print(long a) { printf("%ld", a); }
void Print(long long a) { printf("%lld", a); }
void Print(unsigned long long a) { printf("%llu", a); }
void Print(char a) { printf("%c", a); }
void Print(float a) { printf("%f", a); }
void Print(double a) { printf("%lf", a); }
void Print(long double a) { printf("%Lf", a); }
void Print(const std::string& a)
{
for(auto&& i : a)
Print(i);
}
template <class T>
void Print(const std::vector<T>&);
template <class T, class U>
void Print(const std::pair<T, U>&);
template <class T>
void Print(const std::vector<T>& a)
{
if(a.empty())
return;
Print(a[0]);
for(auto i = a.begin(); ++i != a.end();)
{
putchar(' ');
Print(*i);
}
}
template <class T, class U>
void Print(const std::pair<T, U>& a)
{
Print(a.first);
putchar(' ');
Print(a.second);
}
template <class T>
void Print(const T& a) { std::cout << a; }
void out() { putchar('\n'); }
template <class T>
void out(const T& t)
{
Print(t);
putchar('\n');
}
template <class Car, class... Cdr>
void out(Car& car, Cdr &...cdr)
{
Print(car);
putchar(' ');
out(std::forward<Cdr>(cdr)...);
}
void println() { printf("\n"); }
void println(signed x) { printf("%d\n", x); }
void println(bool x) { printf("%d\n", x); }
void println(unsigned x) { printf("%u\n", x); }
void println(long x) { printf("%ld\n", x); }
void println(long long x) { printf("%lld\n", x); }
void println(unsigned long long x) { printf("%llu\n", x); }
void println(char x) { printf("%c\n", x); }
void println(float x) { printf("%.15f\n", x); }
void println(double x) { printf("%.15lf\n", x); }
template <class T>
void println(T x) { std::cout << x << '\n'; }
#define writeln(x) println(x)
void yn(bool fl = true)
{
out(fl ? "Yes" : "No");
}
template <class T>
void drop(T x)
{
std::cout << (x) << std::endl;
exit(0);
}
void dYes()
{
std::flush(std::cout);
puts("Yes");
fflush(stdout);
exit(0);
}
void dNo()
{
std::flush(std::cout);
puts("No");
fflush(stdout);
exit(0);
}
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
LL fact(LL n, LL m)
{
LL f = n;
for(LL i = n - 1; i >= 1; i--)
{
f *= i;
f %= m;
}
return f;
}
constexpr LL inf = 0x1fffffffffffffff;
constexpr LL mod = 1000000007LL;
constexpr LL mod2 = 998244353LL;
constexpr double eps = 1e-8;
constexpr double pi = 3.141592653589793238462643383279;
#line 2 "cpplib/Graph/LCA.cpp"
#include <vector>
struct LCA
{
std::vector<std::vector<int>> par;
std::vector<int> dis;
LCA(const std::vector<std::vector<int>>& g, int root = 0) { init(g, root); }
void init(const std::vector<std::vector<int>>& g, int root = 0)
{
int v = g.size(), k = 1;
for(; 1 << k < v; k++)
;
par.assign(k, std::vector<int>(v, -1));
dis.assign(v, -1);
dfs(g, root, -1, 0);
for(int i = 0; i < k - 1; i++)
for(int j = 0; j < v; j++)
{
if(par[i][j] < 0)
par[i + 1][j] = -1;
else
par[i + 1][j] = par[i][par[i][j]];
}
}
void dfs(const std::vector<std::vector<int>>& g, int v, int p, int d)
{
par[0][v] = p;
dis[v] = d;
for(int e : g[v])
if(e != p)
dfs(g, e, v, d + 1);
}
int run(int u, int v)
{
if(dis[u] < dis[v])
std::swap(u, v);
int k = par.size();
for(int i = 0; i < k; i++)
if(dis[u] - dis[v] >> i & 1)
u = par[i][u];
if(u == v)
return u;
for(int i = k - 1; i >= 0; i--)
if(par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
return par[0][u];
}
int getdis(int u, int v) { return dis[u] + dis[v] - dis[run(u, v)] * 2; }
bool isonpath(int u, int v, int a) { return getdis(u, a) + getdis(a, v) == getdis(u, v); }
};
#line 2 "cpplib/Graph/oreore_graph.hpp"
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
/*
template <class T>
inline bool chmin(T& a, const T& b)
{
if(b < a)
{
a = b;
return true;
}
return false;
}
*/
template <class T>
struct oreore_graph
{
int _n;
bool _idx;
bool _drc;
std::vector<std::vector<T>> _g;
oreore_graph(int n, bool drc = false, bool idx = 1)
: _n(n), _drc(drc), _idx(idx), _g(n)
{
}
void init(int m)
{
T a, b;
for(int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
a -= _idx;
b -= _idx;
_g[a].emplace_back(b);
if(!_drc)
_g[b].emplace_back(a);
}
}
std::vector<T> bfs(T s, T t = -1)
{
std::vector<T> dis(_n, 1ll << 29);
std::vector<bool> vis(_n, false);
dis[s] = 0;
std::queue<T> q;
q.emplace(s);
while(q.size())
{
T cur = q.front();
q.pop();
for(auto e : _g[cur])
if(chmin(dis[e], dis[cur] + 1))
q.emplace(e);
}
if(t == -1)
return dis;
else
return std::vector<T>{dis[t]};
}
};
template <class T>
struct oreore_weighted_graph
{
using ptt = std::pair<T, T>;
int _n;
bool _idx;
bool _drc;
std::vector<std::vector<ptt>> _g;
oreore_weighted_graph(int n, bool drc = false, bool idx = 1)
: _n(n), _drc(drc), _idx(idx), _g(n)
{
}
void init(int m, bool cst = true)
{
T a, b, c = 1;
for(int i = 0; i < m; i++)
{
if(cst)
scanf("%d %d %d", &a, &b, &c);
else
scanf("%d %d", &a, &b);
a -= _idx;
b -= _idx;
_g[a].emplace_back(c, b);
if(!_drc)
_g[b].emplace_back(c, a);
}
}
std::vector<T> bfs(T s, T t = -1)
{
std::vector<T> dis(_n, 1ll << 29);
std::vector<bool> vis(_n, false);
dis[s] = 0;
std::queue<ptt> q;
q.emplace(0, s);
while(q.size())
{
ptt cur = q.front();
q.pop();
if(cur.first > dis[cur.second])
continue;
for(auto e : _g[cur.second])
if(chmin(dis[e.second], dis[cur.second] + e.first))
q.emplace(dis[e.second], e.second);
}
if(t == -1)
return dis;
else
return std::vector<T>{dis[t]};
}
std::vector<T> dijkstra(T s, T t = -1)
{
std::vector<T> dis(_n, 1ll << 29);
std::vector<bool> vis(_n, false);
dis[s] = 0;
std::priority_queue<ptt, std::vector<ptt>, std::greater<>> pq;
pq.emplace(0, s);
while(pq.size())
{
ptt cur = pq.top();
pq.pop();
if(cur.first > dis[cur.second])
continue;
for(auto e : _g[cur.second])
if(chmin(dis[e.second], dis[cur.second] + e.first))
pq.emplace(dis[e.second], e.second);
}
if(t == -1)
return dis;
else
return std::vector<T>{dis[t]};
}
};
#line 2 "cpplib/math/argsort.hpp"
#include <vector>
#include <algorithm>
struct Ray
{
long long x, y;
bool operator<(const Ray& r) const { return x * r.y > y * r.x; }
bool operator<=(const Ray& r) const { return x * r.y >= y * r.x; }
};
std::vector<std::pair<Ray, Ray>> argSort(std::vector<std::pair<long long, long long>> xy)
{
std::vector<std::pair<Ray, Ray>> p;
for(auto [x, y] : xy)
p.push_back(std::make_pair(Ray{x - 1, y}, Ray{x, y - 1}));
std::sort(p.begin(), p.end());
return p;
}
#line 2 "cpplib/math/comb.hpp"
#include <vector>
template <class T>
struct COMB
{
long long n;
std::vector<T> fa, ifa;
COMB(long long n_) : n(n_)
{
fa.resize(n + 1);
ifa.resize(n + 1);
fa[0] = 1;
for(long long i = 1; i <= n; i++)
fa[i] = fa[i - 1] * i;
ifa[n] = (T)(1) / fa[n];
for(long long i = n - 1; i >= 0; i--)
ifa[i] = ifa[i + 1] * (i + 1);
}
T comb(long long n, long long r)
{
return n < 0 || r < 0 || n < r ? (T)(0) : fa[n] * ifa[r] * ifa[n - r];
}
};
#line 2 "cpplib/math/ksb.hpp"
#include <vector>
#include <map>
std::map<long long, long long> ksb(std::vector<long long> ns)
{
std::map<long long, long long> m;
for(auto n : ns)
{
for(long long i = 2; i * i <= n; i++)
{
long long tmp = 0;
while(n % i == 0)
{
tmp++;
n /= i;
}
if(0 != tmp)
m[i]++;
if(n == 1)
break;
}
if(1 != n)
m[n]++;
}
return m;
}
#line 2 "cpplib/math/modint.hpp"
template <long long Mod>
struct modInt
{
long long x;
constexpr modInt() noexcept : x() {}
template <class T>
constexpr modInt(T v = 0) noexcept : x(v% Mod)
{
if(x < 0)
x += Mod;
}
constexpr long long getval() const noexcept { return x; }
constexpr modInt operator-() const noexcept { return x ? Mod - x : 0; }
constexpr modInt operator+(const modInt& r) const noexcept { return modInt(*this) += r; }
constexpr modInt operator-(const modInt& r) const noexcept { return modInt(*this) -= r; }
constexpr modInt operator*(const modInt& r) const noexcept { return modInt(*this) *= r; }
constexpr modInt operator/(const modInt& r) const noexcept { return modInt(*this) /= r; }
constexpr modInt& operator+=(const modInt& r) noexcept
{
x += r.x;
if(x >= Mod)
x -= Mod;
return *this;
}
constexpr modInt& operator-=(const modInt& r) noexcept
{
x -= r.x;
if(x < 0)
x += Mod;
return *this;
}
constexpr modInt& operator*=(const modInt& r) noexcept
{
x = x * r.x % Mod;
return *this;
}
constexpr modInt& operator/=(const modInt& r) noexcept
{
x = x * r.inv().getval() % Mod;
return *this;
}
constexpr modInt powm(long long n) noexcept
{
if(n < 0)
return powm(-n).inv();
modInt x = *this, r = 1;
for(; n; x *= x, n >>= 1)
if(n & 1)
r *= x;
return r;
}
constexpr modInt inv() const noexcept
{
long long a = x, b = Mod, u = 1, v = 0;
while(b)
{
long long t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return modInt(u);
}
constexpr modInt comb(long long a) noexcept
{
modInt n = *this, s = 1;
for(int i = 0; i < a; i++)
s *= (n - modInt(i));
modInt m = 1;
for(int i = 1; i <= a; i++)
m *= modInt(i);
return s * m.powm(Mod - 2); //Fermat's little thm
}
constexpr bool operator==(const modInt& r) { return this->x == r.x; }
constexpr bool operator!=(const modInt& r) { return this->x != r.x; }
friend std::ostream& operator<<(std::ostream& os, const modInt<Mod>& a) { return os << a.x; }
friend std::istream& operator>>(std::istream& is, modInt<Mod>& a)
{
long long v;
is >> v;
a = modInt<Mod>(v);
return is;
}
};
//const long long mod=1000000007;
//using mint=modInt<mod>;
using mint = modInt<1000000007>;
using mint2 = modInt<998244353>;
#line 2 "cpplib/math/modinv.hpp"
long long modpow(long long a, long long b, long long mod)
{
a %= mod;
long long r = 1;
while(b)
{
r = r * ((b % 2) ? a : 1) % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
long long modinv(long long a, long long mod)
{
return modpow(a, mod - 2, mod);
}
#line 2 "cpplib/math/primefact.hpp"
#include <vector>
template <class T>
std::vector<std::pair<T, T>> prime_factor(T n)
{
std::vector<std::pair<T, T>> ret;
for(T i = 2; i * i <= n; i++)
{
if(n % i != 0)
continue;
T tmp = 0;
while(n % i == 0)
{
tmp++;
n /= i;
}
ret.push_back(make_pair(i, tmp));
}
if(n != 1)
ret.push_back(make_pair(n, 1));
return ret;
}
#line 2 "cpplib/Structure/binaryheap.hpp"
#include <vector>
//bheap
struct bheap
{
std::vector<long> _a;
bheap() { _a.push_back(0L); }
void push(long _x)
{
_a.push_back(_x);
long pos = _a.size() - 1;
for(; pos > 1 && _a[pos] < _a[pos / 2]; std::swap(_a[pos], _a[pos / 2]), pos /= 2)
;
}
void pop()
{
_a[1] = _a[_a.size() - 1];
_a.pop_back();
if(_a.size() == 1)
return;
long pos = 1, lc, rc;
for(; (lc = pos * 2) < _a.size();)
{
rc = lc + 1;
if(lc == _a.size() - 1)
{
if(_a[pos] > _a[lc])
{
std::swap(_a[pos], _a[lc]);
pos = lc;
}
else
{
break;
}
}
else
{
if(_a[lc] < _a[rc])
{
if(_a[lc] < _a[pos])
{
std::swap(_a[pos], _a[lc]);
pos = lc;
}
else
{
break;
}
}
else
{
if(_a[rc] < _a[pos])
{
std::swap(_a[pos], _a[rc]);
pos = rc;
}
else
{
break;
}
}
}
}
}
long getmin() { return _a[1]; }
long siz() { return _a.size() - 1; }
void cl()
{
_a.clear();
_a.push_back(0L);
}
};
#line 2 "cpplib/Structure/BinaryIndexedTree.hpp"
#include <vector>
//BinaryIndexedTree(1-indexed)
template <class T>
struct BIT
{
int n;
std::vector<T> B_I_T;
BIT(int n_ = 0, T init = 0) : n(n_), B_I_T(n_ + 1, init) {}
T sum(int i)
{
T ans = 0;
for(; i > 0; i -= i & -i)
ans += B_I_T[i];
return ans;
}
void add(int i, T a)
{
if(!i)
return;
for(; i <= n; i += i & -i)
B_I_T[i] += a;
}
int l_b_B_I_T(T k)
{
if(k <= 0)
return 0;
int ret = 0, i = 1;
for(; (i << 1) <= n; i <<= 1)
;
for(; i; i >>= 1)
if(ret + i <= n && B_I_T[ret + i] < k)
k -= B_I_T[ret += i];
return (ret + 1);
}
};
#line 2 "cpplib/Structure/compress_vector.hpp"
template <class T>
struct compress_vector
{
int n;
std::vector<T> a;
compress_vector(int n_) : n(n_), a(n_) {};
void compress()
{
std::map<T, T> mp;
for(int i = 0; i < n; i++)
mp[a[i]] = -1;
int c = 0;
for(auto& p : mp)
p.second = c++;
for(int i = 0; i < n; i++)
a[i] = mp[a[i]];
}
};
#line 2 "cpplib/Structure/dynamic_connectivity.hpp"
#include <iostream>
#include <vector>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define LL long long
template<class T>
class dynamic_connectivity
{
class euler_tour_tree
{
public:
struct node;
using nodeP = node*;
struct node
{
nodeP ch[2] = {nullptr, nullptr};
nodeP p = nullptr;
int l, r, sz;
T val = et, sum = et;
bool exact;
bool child_exact;
bool edge_connected = false;
bool child_edge_connected = false;
node() {}
node(int l, int r) : l(l), r(r), sz(l == r), exact(l < r), child_exact(l < r) {}
bool is_root() { return !p; }
};
std::vector<std::unordered_map<int, nodeP>> ptr;
nodeP get_node(int l, int r)
{
if(ptr[l].find(r) == ptr[l].end()) ptr[l][r] = new node(l, r);
return ptr[l][r];
}
nodeP root(nodeP t)
{
if(!t) return t;
while(t->p) t = t->p;
return t;
}
bool same(nodeP s, nodeP t)
{
if(s) splay(s);
if(t) splay(t);
return root(s) == root(t);
}
nodeP reroot(nodeP t)
{
auto s = split(t);
return merge(s.second, s.first);
}
std::pair<nodeP, nodeP> split(nodeP s)
{
splay(s);
nodeP t = s->ch[0];
if(t) t->p = nullptr;
s->ch[0] = nullptr;
return std::make_pair(t, update(s));
}
std::pair<nodeP, nodeP> split2(nodeP s)
{
splay(s);
nodeP t = s->ch[0];
nodeP u = s->ch[1];
if(t) t->p = nullptr;
s->ch[0] = nullptr;
if(u) u->p = nullptr;
s->ch[1] = nullptr;
return std::make_pair(t, u);
}
std::tuple<nodeP, nodeP, nodeP> split(nodeP s, nodeP t)
{
auto u = split2(s);
if(same(u.first, t))
{
auto r = split2(t);
return std::make_tuple(r.first, r.second, u.second);
}
else
{
auto r = split2(t);
return std::make_tuple(u.first, r.first, r.second);
}
}
template<class Car, class... Cdr>
nodeP merge(Car car, Cdr... cdr)
{
return merge(car, merge(cdr...));
}
nodeP merge(nodeP s, nodeP t)
{
if(!s) return t;
if(!t) return s;
while(s->ch[1]) s = s->ch[1];
splay(s);
s->ch[1] = t;
if(t) t->p = s;
return update(s);
}
int size(nodeP t) { return t ? t->sz : 0; }
nodeP update(nodeP t)
{
t->sum = et;
if(t->ch[0]) t->sum = fn(t->sum, t->ch[0]->sum);
if(t->l == t->r) t->sum = fn(t->sum, t->val);
if(t->ch[1]) t->sum = fn(t->sum, t->ch[1]->sum);
t->sz = size(t->ch[0]) + (int)(t->l == t->r) + size(t->ch[1]);
t->child_edge_connected = (
t->ch[0] ? t->ch[0]->child_edge_connected : 0
) | (t->edge_connected) | (
t->ch[1] ? t->ch[1]->child_edge_connected : 0
);
t->child_exact = (
t->ch[0] ? t->ch[0]->child_exact : 0
) | (t->exact) | (
t->ch[1] ? t->ch[1]->child_exact : 0
);
return t;
}
void push(nodeP t) {}
void rot(nodeP t, bool b)
{
nodeP x = t->p, y = x->p;
if(x->ch[1 - b] = t->ch[b]) t->ch[b]->p = x;
t->ch[b] = x, x->p = t;
update(x);
update(t);
if(t->p = y)
{
if(y->ch[0] == x) y->ch[0] = t;
if(y->ch[1] == x) y->ch[1] = t;
update(y);
}
}
void splay(nodeP t)
{
push(t);
while(!t->is_root())
{
nodeP q = t->p;
if(q->is_root())
{
push(q);
push(t);
rot(t, (q->ch[0] == t));
}
else
{
nodeP r = q->p;
push(r);
push(q);
push(t);
bool b = (r->ch[0] == q);
if(q->ch[1 - b] == t)
{
rot(q, b);
rot(t, b);
}
else
{
rot(t, 1 - b);
rot(t, b);
}
}
}
}
void debug(nodeP t)
{
if(!t) return;
debug(t->ch[0]);
std::cerr << t->l << '-' << t->r << ' ';
debug(t->ch[1]);
}
public:
euler_tour_tree() {}
euler_tour_tree(int sz)
{
ptr.resize(sz);
for(int i = 0; i < sz; i++) ptr[i][i] = new node(i, i);
}
int size(int s)
{
nodeP t = get_node(s, s);
splay(t);
return t->sz;
}
bool same(int s, int t) { return same(get_node(s, s), get_node(t, t)); }
void set_size(int sz)
{
ptr.resize(sz);
for(int i = 0; i < sz; i++) ptr[i][i] = new node(i, i);
}
void update(int s, T x)
{
nodeP t = get_node(s, s);
splay(t);
t->val = fn(t->val, x);
update(t);
}
void edge_update(int s, auto g)
{
nodeP t = get_node(s, s);
splay(t);
std::function<void(nodeP)> dfs = [&](nodeP t)
{
assert(t);
if(t->l < t->r && t->exact)
{
splay(t);
t->exact = 0;
update(t);
g(t->l, t->r);
return;
}
if(t->ch[0] && t->ch[0]->child_exact) dfs(t->ch[0]);
else dfs(t->ch[1]);
};
while(t && t->child_exact)
{
dfs(t);
splay(t);
}
}
bool try_reconnect(int s, auto f)
{
nodeP t = get_node(s, s);
splay(t);
std::function<bool(nodeP)> dfs = [&](nodeP t) -> bool
{
assert(t);
if(t->edge_connected)
{
splay(t);
return f(t->l);
}
if(t->ch[0] && t->ch[0]->child_edge_connected) return dfs(t->ch[0]);
else return dfs(t->ch[1]);
};
while(t->child_edge_connected)
{
if(dfs(t)) return true;
splay(t);
}
return false;
}
void edge_connected_update(int s, bool b)
{
nodeP t = get_node(s, s);
splay(t);
t->edge_connected = b;
update(t);
}
bool link(int l, int r)
{
if(same(l, r)) return false;
merge(reroot(get_node(l, l)), get_node(l, r), reroot(get_node(r, r)), get_node(r, l));
return true;
}
bool cut(int l, int r)
{
if(ptr[l].find(r) == ptr[l].end()) return false;
nodeP s, t, u;
std::tie(s, t, u) = split(get_node(l, r), get_node(r, l));
merge(s, u);
nodeP p = ptr[l][r];
nodeP q = ptr[r][l];
ptr[l].erase(r);
ptr[r].erase(l);
delete p;
delete q;
return true;
}
T get_sum(int p, int v)
{
cut(p, v);
nodeP t = get_node(v, v);
splay(t);
T res = t->sum;
link(p, v);
return res;
}
T get_sum(int s)
{
nodeP t = get_node(s, s);
splay(t);
return t->sum;
}
};
int dep = 1;
std::vector<euler_tour_tree> ett;
std::vector<std::vector<std::unordered_set<int>>> edges;
int sz;
public:
dynamic_connectivity(int sz) : sz(sz)
{
ett.emplace_back(sz);
edges.emplace_back(sz);
}
bool link(int s, int t)
{
if(s == t) return false;
if(ett[0].link(s, t)) return true;
edges[0][s].insert(t);
edges[0][t].insert(s);
if(edges[0][s].size() == 1) ett[0].edge_connected_update(s, 1);
if(edges[0][t].size() == 1) ett[0].edge_connected_update(t, 1);
return false;
}
bool same(int s, int t) { return ett[0].same(s, t); }
int size(int s) { return ett[0].size(s); }
std::vector<int> get_vertex(int s) { return ett[0].vertex_list(s); }
void update(int s, T x) { ett[0].update(s, x); }
T get_sum(int s) { return ett[0].get_sum(s); }
bool cut(int s, int t)
{
if(s == t) return false;
for(int i = 0; i < dep; i++)
{
edges[i][s].erase(t);
edges[i][t].erase(s);
if(edges[i][s].size() == 0) ett[i].edge_connected_update(s, 0);
if(edges[i][t].size() == 0) ett[i].edge_connected_update(t, 0);
}
for(int i = dep - 1; i >= 0; i--)
{
if(ett[i].cut(s, t))
{
if(i == dep - 1)
{
dep++;
ett.emplace_back(sz);
edges.emplace_back(sz);
}
return !try_reconnect(s, t, i);
}
}
return false;
}
bool try_reconnect(int s, int t, int k)
{
for(int i = 0; i < k; i++) ett[i].cut(s, t);
for(int i = k; i >= 0; i--)
{
if(ett[i].size(s) > ett[i].size(t)) std::swap(s, t);
auto g = [&](int s, int t) { ett[i + 1].link(s, t); };
ett[i].edge_update(s, g);
auto f = [&](int x) -> bool
{
for(auto itr = edges[i][x].begin(); itr != edges[i][x].end();)
{
auto y = *itr;
itr = edges[i][x].erase(itr);
edges[i][y].erase(x);
if(edges[i][x].size() == 0) ett[i].edge_connected_update(x, 0);
if(edges[i][y].size() == 0) ett[i].edge_connected_update(y, 0);
if(ett[i].same(x, y))
{
edges[i + 1][x].insert(y);
edges[i + 1][y].insert(x);
if(edges[i + 1][x].size() == 1) ett[i + 1].edge_connected_update(x, 1);
if(edges[i + 1][y].size() == 1) ett[i + 1].edge_connected_update(y, 1);
}
else
{
for(int j = 0; j <= i; j++) ett[j].link(x, y);
return true;
}
}
return false;
};
if(ett[i].try_reconnect(s, f)) return true;
}
return false;
}
constexpr static T et = T();
constexpr static T fn(T s, T t) { return s + t; }
};
#line 2 "cpplib/Structure/HashMap.hpp"
#include <vector>
#include <string>
//hmap
struct hmap
{
std::vector<std::vector<std::pair<std::string, int>>> l_;
hmap() { l_.resize(10000, std::vector<std::pair<std::string, int>>(0)); }
int gethash(std::string key)
{
int r = 0;
for(int i = 0; i < key.length(); i++)
r += key[i];
return r % 10000 * 17 % 10000;
}
void put(std::string key, int val)
{
int id = gethash(key);
if(l_[id].empty())
l_[id].push_back(make_pair(key, val));
else
{
auto& ar = l_[id];
for(int i = 0; i < ar.size(); i++)
{
auto pr = ar[i];
if(pr.first == key)
{
ar.erase(ar.begin() + i);
break;
}
}
ar.push_back(make_pair(key, val));
}
}
int get(std::string key)
{
int id = gethash(key);
if(l_[id].empty())
return -1;
else
{
auto& ar = l_[id];
for(int i = 0; i < ar.size(); i++)
{
auto pr = ar[i];
if(pr.first == key)
return pr.second;
}
return -1;
}
}
void rm(std::string key)
{
int id = gethash(key);
if(l_[id].empty())
return;
auto& ar = l_[id];
for(int i = 0; i < ar.size(); i++)
{
auto pr = ar[i];
if(pr.first == key)
{
ar.erase(ar.begin() + i);
break;
}
}
}
};
#line 2 "cpplib/Structure/lazysegtree.hpp"
/*
TODO: 完成させる
//lazysegtree
template<typename X,typename M>struct lazyseg
{
int n;
std::function<X(X,X)>fx;
std::function<X(X,M)>fa;
std::function<X(M,M)>fm;
const X ex;
const M em;
std::vector<X>d;
std::vector<M>lazy;
lazyseg
(
int n_,
std::function<X(X,X)>fx_,
std::function<X(X,M)>fa_,
std::function<X(M,M)>fm_,
X ex_,
M em_
):n(),fx(fx_),fa(fa_),fm(fm_),ex(ex_),em(em_),d(n_*4,ex),lazy(n_*4,em)
{
int x=1;
while(n_>x)x*=2;
n=x;
}
void set(int i,X x){d[i+n-1]=x;}
void build(){for(int k=n-2;k>=0;k--)d[k]=fx(d[2*k+1],d[2*k+2]);}
void eval(int k)
{
if(lazy[k]==em)return;
if(k<n-1)
{
lazy[k*2+1]=fm(lazy[k*2+1],lazy[k]);
lazy[k*2+2]=fm(lazy[k*2+2],lazy[k]);
}
d[k]=fa(d[k],lazy[k]);
lazy[k]=em;
}
void update(int a,int b,M x,int k,int l,int r)
{
eval(k);
if(a<=l&&r<=b)lazy[k]=fm(lazy[k],x),eval(k);
else if(a<r&&l<b)
{
update(a,b,x,k*2+1,l,(l+r)/2);
update(a,b,x,k*2+2,(l+r)/2,r);
d[k]=fx(d[k*2+1],d[k*2+2]);
}
}
void update(int a,int b,M x){update(a,b,x,0,0,n);}
X qsub(int a,int b,int k,int l,int r)
{
eval(k);
if(r<=a||b<=l)return ex;
else if(a<=l&&r<=b)return d[k];
else
{
X vl=qsub(a,b,k*2+1,l,(l+r)/2);
X vr=qsub(a,b,k*2+2,(l+r)/2,r);
return fx(vl,vr);
}
}
X query(int a,int b){return qsub(a,b,0,0,n);}
};
//RMQ :
//int n=**size**
//auto fx=[](int a,int b)->int{return min(a,b);};
//auto fa=[](int x,int m)->int{return m;};
//auto fm=[](int m1,int m2)->int{return m2;};
//int ex=inf;
//int em=inf;
//lazyseg<int,int>rmq(n,fx,fa,fm,ex,em);
*/
#line 2 "cpplib/Structure/segtree.hpp"
// Segtree
template <class T>
struct segtree
{
using F = std::function<T(T, T)>;
int sz;
std::vector<T> seg;
const F f;
const T m1;
segtree(int n, const F f, const T& m1) : f(f), m1(m1)
{
for(sz = 1; sz < n; sz <<= 1)
;
seg.assign(2 * sz, m1);
}
void update(int k, const T& x)
{
k += sz;
seg[k] = x;
for(; k >>= 1;)
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
void set(int k, const T& x) { seg[k + sz] = x; }
void build()
{
for(int k = sz - 1; k > 0; k--)
seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
}
T query(int a, int b)
{
T L = m1, R = m1;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1)
{
if(a & 1)
L = f(L, seg[a++]);
if(b & 1)
R = f(seg[--b], R);
}
return f(L, R);
}
T operator[](const int& k) const { return seg[k + sz]; }
template <class C>
int find_subtree(int a, const C& check, T& M, bool type)
{
for(; a < sz;)
{
T nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]);
if(check(nxt))
a = 2 * a + type;
else
M = nxt, a = 2 * a + 1 - type;
}
return a - sz;
}
template <class C>
int find_first(int a, const C& check)
{
T L = m1;
if(a <= 0)
return check(f(L, seg[1])) ? find_subtree(1, check, L, false) : -1;
int b = sz;
for(a += sz, b += sz; a < b; a >>= 1, b >>= 1)
{
if(a & 1)
{
T nxt = f(L, seg[a]);
if(check(nxt))
return find_subtree(a, check, L, false);
L = nxt;
a++;
}
}
return -1;
}
template <class C>
int find_last(int b, const C& check)
{
T R = m1;
if(b >= sz)
return check(f(seg[1], R)) ? find_subtree(1, check, R, true) : -1;
int a = sz;
for(b += sz; a < b; a >>= 1, b >>= 1)
{
if(b & 1)
{
T nxt = f(seg[--b], R);
if(check(nxt))
return find_subtree(b, check, R, true);
R = nxt;
}
}
return -1;
}
};
// SegmentTree(n, f, M1):= サイズ n の初期化。
// f : 2つの区間の要素をマージする二項演算,
// M1 はモノイドの単位元である。
// set(k, x):= k 番目の要素に x を代入する。
// build():= セグメント木を構築する。
// query(a, b):= 区間 [a, b) に対して二項演算した結果を返す。
// update(k, x):= k 番目の要素を x に変更する。
// operator[k] := k 番目の要素を返す。
// find_first(a, check) := [a,x) が check を満たす最初の要素位置 x を返す。
// find_last(b, check) := [x,b) が check を満たす最後の要素位置 x を返す。
// for example : segtree<int>seg(n,[](int a,int b){return min(a,b);},INT32_MAX);
#line 2 "cpplib/Structure/union-find.hpp"
#include <vector>
#include <algorithm>
//union-find
struct uni
{
int n_;
std::vector<int> par, siz;
uni(int n) : n_(n), par(n), siz(n, 1LL)
{
for(int i = 0; i < n; i++)
par[i] = i;
}
void init(int n)
{
par.resize(n);
siz.assign(n, 1LL);
for(int i = 0; i < n; i++)
par[i] = i;
}
void merge(int x, int y)
{
int rx = root(x);
int ry = root(y);
if(rx == ry)
return;
if(siz[rx] < siz[ry])
std::swap(rx, ry);
siz[rx] += siz[ry];
par[ry] = rx;
return;
}
int root(int x) { return par[x] == x ? x : par[x] = root(par[x]); }
bool same(int x, int y) { return root(x) == root(y); }
int size(int x) { return siz[root(x)]; }
std::vector<std::vector<int>> groups()
{
std::vector<int> rbuf(n_), grsiz(n_);
for(int i = 0; i < n_; i++)
grsiz[(rbuf[i] = root(i))]++;
std::vector<std::vector<int>> res(n_);
for(int i = 0; i < n_; i++)
res[i].reserve(grsiz[i]);
for(int i = 0; i < n_; i++)
res[rbuf[i]].push_back(i);
res.erase(remove_if(res.begin(), res.end(), [&](const std::vector<int>& v)
{ return v.empty(); }),
res.end());
return res;
}
};
#line 2 "Main.cpp"
bool is_prime(LL n)
{
if(n<=1)return false;
if(n==2)return true;
if(n%2==0)return false;
for(LL i=3;i<=(LL)sqrt(n);i+=2)
{
if(n!=i&&n%i==0)return false;
}
return true;
}
void solve()
{
using namespace std;
STR(s);
int n=s.size();
LL ans=0;
bitfor(bit,n)
{
LL sm=0,cur=0;
rep(i,n)
{
cur=cur*10+s[i]-'0';
bitif(bit,i)
{
sm+=cur;
cur=0;
}
}
sm+=cur;
ans+=is_prime(sm);
}
println(ans/2);
}
std::int32_t main()
{
// std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(15);
solve();
}