結果
問題 | No.2442 線形写像 |
ユーザー |
|
提出日時 | 2024-07-22 06:06:40 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 56,138 bytes |
コンパイル時間 | 5,894 ms |
コンパイル使用メモリ | 255,700 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-22 06:06:51 |
合計ジャッジ時間 | 7,087 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 3 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 3 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 15 ms
5,376 KB |
testcase_16 | AC | 14 ms
5,376 KB |
testcase_17 | AC | 28 ms
5,376 KB |
testcase_18 | AC | 33 ms
5,376 KB |
testcase_19 | AC | 36 ms
5,376 KB |
testcase_20 | AC | 36 ms
5,376 KB |
testcase_21 | AC | 29 ms
5,376 KB |
ソースコード
#include <stdio.h> #include <sstream> #include <string.h> #include <vector> #include <map> #include <algorithm> #include <utility> #include <set> #include <cctype> #include <queue> #include <stack> #include <cstdio> #include <cstdlib> #include <cmath> #include <deque> #include <limits> #include <iomanip> #include <ctype.h> #include <unordered_map> #include <random> #include <numeric> #include <iostream> #include <array> #include <atcoder/all> #include <functional> #define _USE_MATH_DEFINES #include <iostream> #include <fstream> #include <math.h> #include <bitset> #pragma intrinsic(_umul128) using namespace std; using namespace atcoder; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<ll, double> pld; typedef pair<double, double> pdd; typedef pair<double, ll> pdl; typedef pair<int, char> pic; typedef vector<ll> vl; typedef vector<double> vd; typedef vector<ull> vul; typedef vector<pll> vpll; typedef vector<int> vi; typedef vector<string> table; typedef priority_queue<ll, vector<ll>, greater<ll>> llgreaterq; typedef priority_queue<pll, vector<pll>, greater<pll>> pllgreaterq; typedef priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> plpllgreaterq; typedef priority_queue<vi, vector<vi>, greater<vi>> vigreaterq; typedef priority_queue<vl, vector<vl>, greater<vl >> vlgreaterq; typedef vector<vl> mat; typedef vector<mat> thd; typedef modint1000000007 mint7; typedef modint998244353 mint9; typedef modint mint; template <class o, class p, class q> using tuple3q = priority_queue<tuple<o, p, q>, vector<tuple<o, p, q>>, greater<tuple<o, p, q>>>; template <class o, class p, class q, class r> using tuple4q = priority_queue<tuple<o, p, q, r>, vector<tuple<o, p, q, r>>, greater<tuple<o, p, q, r>>>; template <class o, class p, class q, class r, class s> using tuple5q = priority_queue<tuple<o, p, q, r, s>, vector<tuple<o, p, q, r, s>>, greater<tuple<o, p, q, r, s>>>; vl dx = { 1,0,-1,0 }; vl dy = { 0,1,0,-1 }; int dxe[] = { 1,1,0,-1,-1,-1,0,1 }; int dye[] = { 0,1,1,1,0,-1,-1,-1 }; #define bit(x,v) ((ll)x << v) #define rep(x,n) for(ll x = 0;x < n;x++) #define rep2(x,f,v) for(ll x=f;x<v;x++) #define repe(v,x) for(auto v : x) // 許容する誤差ε #define EPS (1e-10) // 2つのスカラーが等しいかどうか #define EQ(a,b) (std::abs(a-b) < EPS) // 2つのベクトルが等しいかどうか #define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) ) #define all(a) a.begin(),a.end() #define all0(a) memset(a,0,sizeof(a)) #define allm1(a) memset(a,-1,sizeof(a)) #define set_float() cout << fixed << setprecision(12); #define coutl(s) cout <<s <<endl #define pln(s) cout<<s<<"\n" #define ple pln(-1) #define plm(s) cout<<(s).val()<<"\n" #define plm17(s) cout<<modint1000000007(s).val()<<"\n" #define plm9(s) cout<<modint998244353(s).val()<<"\n" #define put_float(v) set_float() \ pln(v) #define vinsert(v,p,x) v.insert(v.begin() + p,x) #define vsort(v) sort(all(v)); #define vdesc(v) vsort(v); \ reverse(all(v)) #define gete(u,v) ll u,v; cin>>u>>v; u--;v--; #define getpair(a,b) ll a,b;cin>>a>>b; #define dup(v) v.erase(unique(all(v)),v.end()) #define cub(a) (a)*(a)*(a) #define ion(i,j) (i & (1LL << j)) #define Len size() #define psp(a,b) push_back(make_pair(a,b)) #define psp2(a,b) push(make_pair(a,b)) #define cini(a) a; cin >> a #define infa(a,b) (a + b) % INF #define infm(a,b) (a * b) % INF #define infd(a,b) (a * INFinv(b)) % INF #define infs(a,b) (a + INF - inff(b)) % INF #define inf(a) (a) %= INF #define inff(a) ((a + INF) % INF) #define No cout << "No" << endl #define Yes cout << "Yes" << endl #define NO cout << "NO" << endl #define YES cout << "YES" << endl #define errm1 pln(-1);return; #define smal -(ll)1000000009*1000000009 #define big (ll)1000000009*1000000009 #define frontpop(q) q.front();q.pop() #define toppop(q) q.top();q.pop() #define arr(a,s) a[s]; all0(a); #define nxt(cu) (cu+1) % 2 #define chkover(x,y,h,w) (x<0||y<0||x>=h||y>=w) #define psb(v) ll value;cin>>value;v.push_back(value); #define lower_b(v,p) lower_bound(all(v), p) #define upper_b(v,p) upper_bound(all(v), p) #define allpln(v) for(auto &e:v)pln(e) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define msize 216; #define revarr(p,l,r) reverse(p.begin()+l,p.begin()+r+1) #define reverse_all(p) reverse(all(p)) #define cill(x) ll x;cin>>x #define cilll(x,y) ll x,y;cin>>x>>y #define bitn(x,k)(((x)>>(k))&1) #define iotan(a,n) iota(all(a),n) #define cline(a,k) vl a(k); rep(i,k){cin>>a[i];} #define clineu(a,k) vul a(k); rep(i,k){cin>>a[i];} #define clines(a,k) vector <string> a(k); rep(i,k){cin>>a[i];} #define cindec(a) ll a; cin>> a; a--; template <typename T, typename U> T SUM(const vector<U>& A) { T sum = 0; for (auto&& a : A) sum += a; return sum; } ll ceil(ll a, ll b) { return a > 0 ? (a - 1) / b + 1 : a / b; } ll n, m; bool chmin(ll& a, ll b) { if (a > b) { a = b; return 1; } return 0; } bool chmind(double& a, double b) { if (a > b) { a = b; return 1; } return 0; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } ll INF = 1000000007; const int MAX = 3000010; void cout2(ll val) { if (val >= big) { pln(-1); } else { pln(val); } } void cout3(ll val) { if (val >= INF) { pln(-1); } else { pln(val); } } template <typename T> vector<T> merge_arr(vector<T>& a, vector<T>& b) { vector<T> c(a.size() + b.size()); std::merge(all(a), all(b), c.begin()); return c; } string padleft(string x, ll dig, char c) { ll si = x.size(); for (ll i = 0; i < dig - si; i++) { x = c + x; } return x; } long long fac[MAX], finv[MAX], inv[MAX], called; void COMinit() { fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i < MAX; i++) { fac[i] = fac[i - 1] * i % INF; inv[i] = INF - inv[INF % i] * (INF / i) % INF; finv[i] = finv[i - 1] * inv[i] % INF; } } void COMinit998244353() { INF = 998244353; COMinit(); called = 1; } void COMinit1000000007() { INF = 1000000007; COMinit(); called = 1; } ll gfac(ll x) { if (!called) { COMinit(); called = 1; } return fac[x]; } // 二項係数計算 long long COM(int n, int k) { if (!called) { COMinit(); called = 1; } if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % INF) % INF; } modint998244353 COM2(ll n, ll k) { modint998244353 res = 1; rep(i, k) { res *= (n - i); res /= (i + 1); } return res; } ll getpow(ll b, ll x, ll md) { ll t = b % md; ll res = 1; while (x > 0) { if (x & 1) { res *= t; res %= md; } x >>= 1; t *= t; t %= md; } return res % md; } ull getpowul(ull b, ull x, ull md) { ull t = b % md; ull res = 1; while (x > 0) { if (x & 1) { res *= t; res %= md; } x >>= 1; t *= t; t %= md; } return res % md; } ll getpow(ll b, ll x) { return getpow(b, x, INF); } /// 素数を法とする場合 ll modinv(ll x) { return getpow(x, INF - 2); } ll extgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } /// <summary> /// 素数を法としない場合 /// </summary> /// <param name="a"></param> /// <param name="m"></param> /// <returns></returns> ll modinv(ll a, ll m) { ll x, y; extgcd(a, m, x, y); return (m + x % m) % m; } ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } class m_random { std::mt19937 mt; std::uniform_int_distribution<> rand100; public: m_random(ll mi, ll ma) { init_random(mi, ma); } void init_random(ll mi, ll ma) { std::random_device rnd; // 非決定的な乱数生成器を生成 mt = std::mt19937(rnd()); // メルセンヌ・ツイスタの32ビット版、引数は初期シード値 rand100 = std::uniform_int_distribution<>(mi, ma); } ll get() { return rand100(mt); } }; class m_sampling { std::mt19937 mt; std::normal_distribution<double> rand; public: m_sampling(double sigma) { init_sampling(sigma); } void init_sampling(double sigma) { std::random_device rnd; mt = std::mt19937(rnd()); rand = std::normal_distribution<double>(0.0, sigma); } double get() { return rand(mt); } }; typedef vector<modint998244353> vml; typedef vector<vml> matm; typedef vector<modint1000000007> vml2; typedef vector<vml2> matm2; typedef vector<modint> vml3; typedef vector<vml3> matm3; #define cmat(n,s,ss) mat n(s,vl(ss)) #define cmatm(n,s,ss) matm n(s,vml(ss)) #define cmatm2(n,s,ss) matm2 n(s,vml2(ss)) #define cmatm3(n,s,ss) matm3 n(s,vml3(ss)) // Union find vl pr; vl lank; vl udpt; void uini(int _n) { _n++; // 一個拡張しておく pr = vl(_n + 1); lank = vl(_n + 1); udpt = vl(_n + 1, 0); for (ll i = 0; i <= _n; i++) { pr[i] = i; lank[i] = 1; } } int parent(int x) { if (x == pr[x]) return x; auto paren = parent(pr[x]); udpt[x] = udpt[paren] + 1; return pr[x] = paren; } int same(int x, int y) { return parent(x) == parent(y); } bool unit(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (lank[py] <= lank[px]) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } ll unisize(ll i) { return lank[parent(i)]; } bool unitm(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (lank[py] < lank[px]) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } /// <summary> /// 数字の小さい方を親にするように処理 /// </summary> /// <param name="x"></param> /// <param name="y"></param> /// <returns></returns> bool unitlow(int x, int y) { int px = parent(x); int py = parent(y); if (px == py) return false; if (py < px) { pr[py] = px; lank[px] += lank[py]; } else { pr[px] = py; lank[py] += lank[px]; } return true; } ll clamp(ll t, ll l, ll r) { return max(l, min(r, t)); } int H; int left(int i) { return i * 2 + 1; } int right(int i) { return i * 2 + 2; } class edge { public: int from, to, i; ll val; ll cap, rev, icap; edge() {} edge(ll to) : to(to) {} edge(ll to, ll i) : to(to), i(i) {} edge(ll from, ll to, ll val) : from(from), to(to), val(val) {} void flowEdge(ll _to, ll _cap, ll _rev) { to = _to; cap = _cap; icap = _cap; rev = _rev; } }; typedef vector<vector<edge>> vve; class LCA { private: vector<vector<edge>> v; vector<vector<int>> parent; vector<int> depth; ll root; void dfs(int n, int m, int d) { parent[0][n] = m; depth[n] = d; for (auto x : v[n]) { if (x.to != m) dfs(x.to, n, d + 1); } } public: LCA() {} LCA(ll N, ll root, vector<vector<edge>>& tree) { v = tree; this->root = root; parent = vector<vector<int>>(21, vector<int>(N + 1, 0)); depth = vector<int>(N + 1, 0); dfs(root, -1, 0); for (int j = 0; j + 1 < 20; j++) { for (int i = 1; i <= N; i++) { if (parent[j][i] < 0) parent[j + 1][i] = -1; else parent[j + 1][i] = parent[j][parent[j][i]]; } } } int lca(int n, int m) { if (depth[n] > depth[m]) swap(n, m); if (n == root) return root; for (int j = 0; j < 20; j++) { if ((depth[m] - depth[n]) >> j & 1) m = parent[j][m]; } if (n == m) return n; for (int j = 19; j >= 0; j--) { if (parent[j][n] != parent[j][m]) { n = parent[j][n]; m = parent[j][m]; } } return parent[0][n]; } int dep(int n) { return depth[n]; } }; ll k; int _rank[1010]; int temp[1010]; bool compare_sa(int i, int j) { if (_rank[i] != _rank[j]) return _rank[i] < _rank[j]; else { int ri = i + k <= n ? _rank[i + k] : -1; int rj = j + k <= n ? _rank[j + k] : -1; return ri < rj; } } void construct_sa(string S, int* sa) { n = S.length(); for (ll i = 0; i <= n; i++) { sa[i] = i; _rank[i] = i < n ? S[i] : -1; } for (k = 1; k <= n; k *= 2) { sort(sa, sa + n + 1, compare_sa); // saはソート後の接尾辞の並びになっている、rankは元の位置のindexを保持したまま、更新されている。 // ピンとこなかった部分 temp[sa[0]] = 0; for (ll i = 1; i <= n; i++) { temp[sa[i]] = temp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for (ll i = 0; i <= n; i++) { _rank[i] = temp[i]; } } } bool contain(string S, int* sa, string T) { int a = 0, b = S.length(); // sa は 接尾辞が辞書順に並んでいる、入っているのはその位置のインデックス while (b - a > 1) { int c = (a + b) / 2; if (S.compare(sa[c], T.length(), T) < 0) a = c; else b = c; } return S.compare(sa[b], T.length(), T) == 0; } #define bit(x,v) ((ll)x << v) class BIT { static const int MAX_N = 500010; public: vl bit; ll n; BIT() { bit = vl(MAX_N + 1, 0); } BIT(ll _n) { bit = vl(_n * 2 + 10, 0); n = _n; } ll sum(int i) { ll s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(int i, int x) { while (i <= n) { bit[i] += x; i += i & -i; } } }; struct UnionFind { vector<int> A; UnionFind(int n) : A(n, -1) {} int find(int x) { if (A[x] < 0) return x; return A[x] = find(A[x]); } void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (A[x] > A[y]) swap(x, y); A[x] += A[y]; A[y] = x; } int ngroups() { int ans = 0; for (auto a : A) if (a < 0) ans++; return ans; } }; vector<ll> getp(ll n) { vector<ll> res; if (n % 2 == 0) { res.push_back(2); while (n % 2 == 0)n /= 2; } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { res.push_back(i); while (n % i == 0)n /= i; } } if (n != 1) res.push_back(n); return res; } vector<ll> getpp(ll n) { vector<ll> res; if (n % 2 == 0) { res.push_back(2); while (n % 2 == 0)n /= 2; } for (ll i = 3; i * i * i <= n; i += 2) { if (n % i == 0) { res.push_back(i); while (n % i == 0)n /= i; } } if (n != 1) res.push_back(n); return res; } vector<ll> getp2(ll n) { vector<ll> res; if (n % 2 == 0) { while (n % 2 == 0) { n /= 2; res.push_back(2); } } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { while (n % i == 0) { n /= i; res.push_back(i); } } } if (n != 1) res.push_back(n); return res; } vector<pll> getp3(ll n) { vector<pll> res; int si = 0; if (n % 2 == 0) { res.push_back(make_pair(2, 0)); while (n % 2 == 0) { n /= 2; res[si].second++; } si++; } for (ll i = 3; i * i <= n; i += 2) { if (n % i == 0) { res.push_back(make_pair(i, 0)); while (n % i == 0) { n /= i; res[si].second++; } si++; } } if (n != 1) { res.push_back(make_pair(n, 1)); } return res; } vector<ll> getDivisors(ll n) { vector<ll> res; res.push_back(1); if (1 < n) res.push_back(n); for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { res.push_back(i); if (n / i != i) res.push_back(n / i); } } vsort(res); return res; } struct ve { public: vector<ve> child; int _t = INF; ve(int t) :_t(t) {} ve(ve _left, ve _right) { _t = _left._t + _right._t; child.push_back(_left); child.push_back(_right); } bool operator<(const ve& t) const { return _t > t._t; } }; vector<bool> elas(ll n) { n++; vector<bool> r(n, 1); r[0] = 0; r[1] = 0; ll tw = 4; while (tw < n) { r[tw] = false; tw += 2; } ll th = 6; while (th < n) { r[th] = false; th += 3; } ll fv = 10; while (fv < n) { r[fv] = false; fv += 5; } for (ll i = 6; i * i < n; i += 6) { ll bf = i - 1; if (r[bf]) { ll ti = bf * 2; while (ti < n) { r[ti] = false; ti += bf; } } ll nx = i + 1; if (r[nx]) { ll ti = nx * 2; while (ti < n) { r[ti] = false; ti += nx; } } } return r; } vl getprimes(ll x) { auto e = elas(x); vl r; rep2(i, 2, x + 1) { if (e[i])r.push_back(i); } return r; } bool isPrime(ll v) { if (v == 1 || v == 0) return false; for (ll i = 2; i * i <= v; i++) { if (v % i == 0) return false; } return true; } class SegTree { public: const static int MAX_N = 1000100; const static int DAT_SIZE = (1 << 20) - 1; int N, Q; int A[MAX_N]; ll MAX = big; ll data[DAT_SIZE], datb[DAT_SIZE]; void init(int _n) { N = 1; while (N < _n) N <<= 1; memset(data, 0, sizeof(data)); memset(datb, 0, sizeof(datb)); } void init(int _n, ll iv) { N = 1; while (N < _n) N <<= 1; rep(i, DAT_SIZE) { data[i] = iv; datb[i] = iv; } } void initRMQ(int _n) { N = 1; while (N < _n) N *= 2; // 全ての値をbigに rep(i, 2 * N - 1) data[i] = MAX; } void updateRMQ(int k, ll a) { k += N - 1; data[k] = a; while (k > 0) { k = (k - 1) / 2; data[k] = min(data[k * 2 + 1], data[k * 2 + 2]); } } ll RMQ(int a, int b) { return queryRMQ(a, b + 1, 0, 0, N); } ll queryRMQ(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return MAX; // [a,b)が[l,r)を完全に含んでいれば if (a <= l && r <= b) return data[k]; // そうでなければ2つの子の最小値 // n=16 // 0,16→0,8 8,16 // 0,4 4,8 8,12 12,16 ll vl = queryRMQ(a, b, k * 2 + 1, l, (l + r) / 2); ll vr = queryRMQ(a, b, k * 2 + 2, (l + r) / 2, r); return min(vl, vr); } void add(int a, int b, int x) { add(a, b + 1, x, 0, 0, N); } void add(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { data[k] += x; } else if (l < b && a < r) { datb[k] += (min(b, r) - max(a, l)) * x; add(a, b, x, k * 2 + 1, l, (l + r) / 2); add(a, b, x, k * 2 + 2, (l + r) / 2, r); } } void change(int a, int b, int x) { change(a, b + 1, x, 0, 0, N); } void change(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { data[k] = x; } else if (l < b && a < r) { datb[k] = x; change(a, b, x, k * 2 + 1, l, (l + r) / 2); change(a, b, x, k * 2 + 2, (l + r) / 2, r); } } ll sum(int a, int b) { return sum(a, b + 1, 0, 0, N); } ll sum(int a, int b, int k, int l, int r) { if (b <= l || r <= a) { return 0; } if (a <= l && r <= b) { return data[k] * (r - l) + datb[k]; } ll res = (min(b, r) - max(a, l)) * data[k]; res += sum(a, b, k * 2 + 1, l, (l + r) / 2); res += sum(a, b, k * 2 + 2, (l + r) / 2, r); return res; } }; class LazySegTree { private: int N; vl node, lazy; public: void init(int _n) { N = 1; while (N < _n) N <<= 1; node.resize(2 * N, 0); lazy.resize(2 * N, 0); } // k 番目のノードについて遅延評価を行う void eval(int k, int l, int r) { // 遅延配列が空でない場合、自ノード及び子ノードへの // 値の伝播が起こる if (lazy[k] != 0) { node[k] += lazy[k]; // 最下段かどうかのチェックをしよう // 子ノードは親ノードの 1/2 の範囲であるため、 // 伝播させるときは半分にする if (r - l > 1) { lazy[2 * k + 1] += lazy[k] / 2; lazy[2 * k + 2] += lazy[k] / 2; } // 伝播が終わったので、自ノードの遅延配列を空にする lazy[k] = 0; } } void add(int a, int b, ll x) { addbody(a, b + 1, x); } void addbody(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { lazy[k] += (r - l) * x; eval(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { addbody(a, b, x, 2 * k + 1, l, (l + r) / 2); addbody(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = node[2 * k + 1] + node[2 * k + 2]; } } ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return 0; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r); return vl + vr; } ll getMax(int a, int b) { // 半開区間に変換 return getMaxBdy(a, b + 1); } ll getMaxBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; class LazySegTreeRMQ { private: int N; vl node, lazy; public: void init(int _n) { N = 1; while (N < _n) N <<= 1; node.resize(2 * N, 0); lazy.resize(2 * N, 0); } // k 番目のノードについて遅延評価を行う void eval(int k, int l, int r) { if (lazy[k] != 0) { node[k] = lazy[k]; if (r - l > 1) { lazy[2 * k + 1] = lazy[k]; lazy[2 * k + 2] = lazy[k]; } lazy[k] = 0; } } void evalAdd(int k, int l, int r) { if (lazy[k] != 0) { node[k] += lazy[k]; if (r - l > 1) { lazy[2 * k + 1] += lazy[k]; lazy[2 * k + 2] += lazy[k]; } lazy[k] = 0; } } void add(int a, int b, ll x) { addbody(a, b + 1, x); } void addbody(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う evalAdd(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { lazy[k] += x; evalAdd(k, l, r); } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { addbody(a, b, x, 2 * k + 1, l, (l + r) / 2); addbody(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = max(node[2 * k + 1], node[2 * k + 2]); } } void update(int a, int b, ll v) { updateBdy(a, b + 1, v); } void updateBdy(int a, int b, ll x, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; // k 番目のノードに対して遅延評価を行う eval(k, l, r); // 範囲外なら何もしない if (b <= l || r <= a) return; // 完全に被覆しているならば、遅延配列に値を入れた後に評価 if (a <= l && r <= b) { if (x > node[k]) { lazy[k] = x; eval(k, l, r); } } // そうでないならば、子ノードの値を再帰的に計算して、 // 計算済みの値をもらってくる else { updateBdy(a, b, x, 2 * k + 1, l, (l + r) / 2); updateBdy(a, b, x, 2 * k + 2, (l + r) / 2, r); node[k] = max(node[2 * k + 1], node[2 * k + 2]); } } ll getMaxAdd(int a, int b) { // 半開区間に変換 return getMaxAddBdy(a, b + 1); } ll getMaxAddBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! evalAdd(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxAddBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxAddBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } ll getMax(int a, int b) { // 半開区間に変換 return getMaxBdy(a, b + 1); } ll getMaxBdy(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = N; if (b <= l || r <= a) return -big; // 関数が呼び出されたら評価! eval(k, l, r); if (a <= l && r <= b) return node[k]; ll vl = getMaxBdy(a, b, 2 * k + 1, l, (l + r) / 2); ll vr = getMaxBdy(a, b, 2 * k + 2, (l + r) / 2, r); return max(vl, vr); } }; class Segment; class Circle; class Point { public: double x, y; Point(double x = 0, double y = 0) :x(x), y(y) {} Point operator + (Point p) { return Point(x + p.x, y + p.y); } Point operator - (Point p) { return Point(x - p.x, y - p.y); } Point operator * (double a) { return Point(a * x, a * y); } Point operator / (double a) { return Point(x / a, y / a); } double abs() { return sqrt(norm()); } double norm() { return x * x + y * y; } bool operator < (const Point& p)const { return x != p.x ? x < p.x : y < p.y; } bool operator == (const Point& p) const { return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS; } // 内積 static double dot(Point a, Point b) { return a.x * b.x + a.y * b.y; } // 外積 static double cross(Point a, Point b) { return a.x * b.y - a.y * b.x; } static bool isOrthogonal(Point a, Point b) { return EQ(dot(a, b), 0.0); } static bool isOrthogonal(Point a1, Point a2, Point b1, Point b2) { return isOrthogonal(a1 - a2, b1 - b2); } static bool isOrthogonal(Segment s1, Segment s2); static bool isPalallel(Point a, Point b) { return EQ(cross(a, b), 0.0); } static bool isPalallel(Point a1, Point a2, Point b1, Point b2) { return isPalallel(a1 - a2, b1 - b2); } static bool isPalallel(Segment s1, Segment s2); static const int COUNTER_CLOCKWISE = 1; static const int CLOCKWISE = -1; static const int ONLINE_BACK = 2; static const int ONLINE_FRONT = -2; static const int ON_SEGMENT = 0; static int bbw(Point p0, Point p1, Point p2) { // 線分はp0とp1でp2がどこにあるかを探る Point a = p1 - p0; Point b = p2 - p0; if (cross(a, b) > EPS) return COUNTER_CLOCKWISE; if (cross(a, b) < -EPS) return CLOCKWISE; if (dot(a, b) < -EPS) return ONLINE_BACK; if (a.norm() < b.norm()) return ONLINE_FRONT; return ON_SEGMENT; } // 交差しているか static bool intersect(Point p1, Point p2, Point p3, Point p4) { return (bbw(p1, p2, p3) * bbw(p1, p2, p4) <= 0 && bbw(p3, p4, p1) * bbw(p3, p4, p2) <= 0); } static bool intersect(Segment s1, Segment s2); static Point project(Segment s, Point p); static Point reflect(Segment s, Point p); static Point getDistance(Point a, Point b) { return (a - b).abs(); } static double getDistanceLP(Segment s, Point p); static double getDistanceSP(Segment s, Point p); static double getDistance(Segment s1, Segment s2); static Point getIntersection(Segment s1, Segment s2); static pair<Point, Point> crossPoints(Circle c, Segment s); static int contains(vector<Point> g, Point p) { int n = g.size(); bool x = false; rep(i, n) { Point a = g[i] - p, b = g[(i + 1) % n] - p; // 線の上に載っているか if (std::abs(cross(a, b)) < EPS && dot(a, b) < EPS) return 1; // pを基準として上下にあるか // または外積が正か?(→にあるか) if (a.y > b.y) swap(a, b); if (a.y < EPS && EPS < b.y && cross(a, b) > EPS) x = !x; } return x ? 2 : 0; } static vector<Point> andrewScan(vector<Point> s) { vector<Point> u, l; ll si = s.size(); if (si < 3) return s; sort(all(s)); u.push_back(s[0]); u.push_back(s[1]); l.push_back(s[si - 1]); l.push_back(s[si - 2]); for (int i = 2; i < si; i++) { for (int _n = u.size(); _n >= 2 && bbw(u[_n - 2], u[_n - 1], s[i]) > CLOCKWISE; _n--) { u.pop_back(); } u.push_back(s[i]); } for (int i = s.size() - 3; i >= 0; i--) { for (int _n = l.size(); _n >= 2 && bbw(l[_n - 2], l[_n - 1], s[i]) > CLOCKWISE; _n--) { l.pop_back(); } l.push_back(s[i]); } reverse(all(l)); for (int i = u.size() - 2; i >= 1; i--) { l.push_back(u[i]); } return l; } void get_cin() { cin >> x >> y; } static Point rotate(double r, Point p) { Point ret; ret.x = cos(r) * p.x - sin(r) * p.y; ret.y = sin(r) * p.x + cos(r) * p.y; return ret; } }; class Segment { public: Point p1, p2; Segment() {} Segment(Point p1, Point p2) :p1(p1), p2(p2) {} void get_cin() { cin >> p1.x >> p1.y >> p2.x >> p2.y; } Point p1tp2() { return p2 - p1; } Point p2tp1() { return p1 - p2; } double abs() { return (p2 - p1).abs(); } double norm() { return (p2 - p1).norm(); } }; // 直行 bool Point::isOrthogonal(Segment s1, Segment s2) { return EQ(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0); } // 平行 bool Point::isPalallel(Segment s1, Segment s2) { return EQ(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0); } // 交差しているか bool Point::intersect(Segment s1, Segment s2) { return intersect(s1.p1, s1.p2, s2.p1, s2.p2); } Point Point::project(Segment s, Point p) { Point base = s.p2 - s.p1; double r = Point::dot(p - s.p1, base) / base.norm(); return s.p1 + base * r; } Point Point::reflect(Segment s, Point p) { return (project(s, p) * 2) - p; } double Point::getDistanceLP(Segment s, Point p) { return std::abs(cross(s.p2 - s.p1, p - s.p1) / (s.p2 - s.p1).abs()); } double Point::getDistanceSP(Segment s, Point p) { if (dot(s.p2 - s.p1, p - s.p1) < 0.0) return (p - s.p1).abs(); if (dot(s.p1 - s.p2, p - s.p2) < 0.0) return (p - s.p2).abs(); return getDistanceLP(s, p); } double Point::getDistance(Segment s1, Segment s2) { if (intersect(s1, s2)) return 0.0; return min({ getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2) ,getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2) }); } Point Point::getIntersection(Segment s1, Segment s2) { // (s1.p1 - s2.p1).norm() auto bs = s1.p2 - s1.p1; auto n1 = s2.p1 - s1.p1; auto n2 = s2.p2 - s1.p1; auto c1 = std::abs(cross(n1, bs)) / bs.norm(); auto c2 = std::abs(cross(n2, bs)) / bs.norm(); return s2.p1 + (s2.p2 - s2.p1) * (c1 / (c1 + c2)); // c1:c2=t:1-t // c2t=(1-t)c1 // t/(1-t)=c1/(c1+c2) // } double arg(Point p) { return atan2(p.y, p.x); } Point polar(double a, double r) { return Point(cos(r) * a, sin(r) * a); } class Circle { public: Point c; double r; Circle(Point c = Point(), double r = 0.0) : c(c), r(r) {} void get_cin() { cin >> c.x >> c.y >> r; } static pair<Point, Point> getCrossPoints(Circle c1, Circle c2) { double d = (c1.c - c2.c).abs(); // 中心点どうしの距離 double a = acos((c1.r * c1.r + d * d - c2.r * c2.r) / (2 * c1.r * d)); double t = arg(c2.c - c1.c); return make_pair(c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)); } }; pair<Point, Point> Point::crossPoints(Circle c, Segment s) { auto pp = project(s, c.c); auto f = (pp - c.c).norm(); auto mu = sqrt(c.r * c.r - f); // 単位ベクトル auto e = s.p1tp2() / s.p1tp2().abs(); return make_pair(pp + e * mu, pp - e * mu); } ll divRm(string s, ll x) { ll r = 0; for (ll i = 0; i < s.size(); i++) { r *= 10; r += s[i] - '0'; r %= x; } return r; } ll cmbi(ll x, ll b) { ll res = 1; for (size_t i = 0; i < b; i++) { res *= x - i; res %= INF; res *= inv[b - i]; res %= INF; } return res; } map<ll, ll> dgmemo; ll digsum(ll x) { if (dgmemo.count(x))return dgmemo[x]; ll res = 0; while (x > 0) { res += x % 10; x /= 10; } return res; } bool check_parindrome(string s) { int n = s.size(); rep(i, n / 2) { if (s[i] != s[n - i - 1]) { return false; } } return true; } ll npr(ll n, ll r) { if (r == 0) return 1; return inff(fac[n] * modinv(fac[n - r])); } vl zalgo(string s) { ll c = 0; vl a(s.size()); ll si = s.size(); rep2(i, 1, s.size()) { if (i + a[i - c] < c + a[c]) { a[i] = a[i - c]; } else { ll j = max(0LL, a[c] - (i - c)); while (i + j < si && s[j] == s[i + j]) { j++; } a[i] = j; c = i; } } a[0] = s.size(); return a; } // 数値文字列の除算 string divStrNum(string s, ll v) { ll si = s.size(); ll val = 0; string res = ""; for (ll i = 0; i < si; i++) { val *= 10; val += s[i] - '0'; ll add = val / v; val %= v; if (add == 0 && res == "") continue; res += add + '0'; } if (res == "") return "0"; return res; } // 数値文字列の減算 string difStrNum(string s, ll v) { ll si = s.size(); bool dec = false; for (ll i = si - 1; i >= 0; i--) { if (v == 0) break; ll t = v % 10; v /= 10; ll u = (s[i] - '0'); if (dec) { if (u == 0) { s[i] = 9 - t; dec = true; continue; } u--; } if (u < t) { s[i] = 10 - (t - u); dec = true; } else { s[i] -= t; dec = false; } } return s; } // 数値文字列を1減らした数 string decStrNum(string s) { ll si = s.size(); for (int i = si - 1; i >= 0; i--) { if (s[i] == '0') { s[i] = '9'; continue; } s[i] = s[i] - 1; break; } return s; } void dateCal(int x) { int lp = x / 7; string date[] = { "月曜日","火曜日","水曜日","木曜日","金曜日","土曜日","日曜日" }; rep(i, 7) { int st = i; rep(j, lp) { cout << "\t" << date[i] << x << "-" << st << "\t" << "NULL" << "\t" << x << "\t" << st << "\t" << 0 << endl; st += 7; } } } // 行列べき乗計算 mat mul(mat& A, mat& B) { ll as = A.size(); ll bs = B.size(); mat C(A.size(), vl(B[0].size())); rep(i, as) { rep(t, bs) { ll bz = B[0].size(); rep(j, bz) { C[i][j] = inff(C[i][j] + A[i][t] * B[t][j]); } } } return C; } mat pow(mat A, ll x) { if (A.size() == 0)return A; mat B(A.size(), vl(A.size())); rep(i, A.size()) { B[i][i] = 1; } while (x > 0) { if (x & 1) B = mul(B, A); A = mul(A, A); x >>= 1; } return B; } class dinic { public: vve G; vl level; vl iter; dinic(int _n) : dinic(vve(_n + 1)) { } dinic(vve g) { G = g; level = vl(g.size()); iter = vl(g.size()); } void add_edge(ll from, ll to, ll cap) { auto e1 = edge(); auto e2 = edge(); e1.flowEdge(to, cap, G[to].size()); G[from].push_back(e1); e2.flowEdge(from, 0, G[from].size() - 1); G[to].push_back(e2); } void bfs(ll s) { fill(all(level), -1); queue<ll> q; level[s] = 0; q.push(s); while (!q.empty()) { ll v = frontpop(q); for (auto e : G[v]) { if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; q.push(e.to); } } } } ll dfs(ll v, ll t, ll f) { if (v == t) return f; for (ll& i = iter[v]; i < G[v].size(); i++) { edge& e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { ll d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } ll max_flow(ll s, ll t) { ll flow = 0; for (;;) { bfs(s); if (level[t] < 0) return flow; fill(all(iter), 0); ll f; while ((f = dfs(s, t, big)) > 0) { flow += f; } } } }; const ull BS = 1000000007; // aはbに含まれているか? bool rolling_hash(string a, string b) { int al = a.size(), bl = b.size(); if (al > bl) return false; // BSのal乗を計算 ull t = 1; rep(i, al)t *= BS; // aとbの最初のal文字に関するハッシュ値を計算 ull ah = 0, bh = 0; rep(i, al) ah = ah * BS + a[i]; rep(i, al) bh = bh * BS + b[i]; // bの場所を一つずつ進めながらハッシュ値をチェック for (ll i = 0; i + al <= bl; i++) { if (ah == bh) return true; if (i + al < bl)bh = bh * BS + b[i + al] - b[i] * t; } return false; } mat sans(9, vl(9, -1)); bool srec(ll x, ll y) { if (x == 9) return true; vl use(10, 0); rep(i, 9) { if (sans[i][y] == -1) continue; use[sans[i][y]] = 1; } rep(j, 9) { if (sans[x][j] == -1) continue; use[sans[x][j]] = 1; } ll px = x % 3; ll py = y % 3; ll tx = x - px + 3; ll ty = y - py + 3; rep2(i, x - px, tx) { rep2(j, y - py, ty) { if (sans[i][j] == -1) continue; use[sans[i][j]] = 1; } } ll nx, ny; if (y == 8) { nx = x + 1; ny = 0; } else { nx = x; ny = y + 1; } if (sans[x][y] != -1) { if (srec(nx, ny)) { return true; } return false; } rep2(i, 1, 10) { if (use[i]) continue; sans[x][y] = i; if (srec(nx, ny)) { return true; } sans[x][y] = -1; } return false; } void sudoku() { vector<string> tb; rep(i, 9) { string s; cin >> s; tb.push_back(s); rep(j, 9) { if (tb[i][j] != '.') { sans[i][j] = tb[i][j] - '0'; } } } srec(0, 0); rep(i, 9) { rep(j, 9) { cout << sans[i][j]; } cout << endl; } } mint ncr(ll n, ll r) { mint v = 1; rep(i, r) { v *= (n - i); v *= inv[i + 1]; } return v; } modint1000000007 ncr2(ll n, ll r) { modint1000000007 v = 1; rep(i, r) { v *= (n - i); v /= i + 1; } return v; } ll sq(ll x) { return x * x; } ll phi(ll x) { auto p = getp(x); ll res = x; for (auto v : p) { res /= v; res *= v - 1; } return res; } const ull MASK30 = (1ULL << 30) - 1; const ull MASK31 = (1ULL << 31) - 1; const ull MOD = (1ULL << 61UL) - 1UL; const ull MASK61 = MOD; //mod 2^61-1を計算する関数 ull calc_mod_61(ull x) { ull xu = x >> 61; ull xd = x & MASK61; ull res = xu + xd; if (res >= MOD) res -= MOD; return res; } ull mul_61(ull a, ull b) { ull au = a >> 31; ull ad = a & MASK31; ull bu = b >> 31; ull bd = b & MASK31; ull mid = ad * bu + au * bd; ull midu = mid >> 30; ull midd = mid & MASK30; return calc_mod_61(au * bu * 2 + midu + (midd << 31) + ad * bd); } vl mulMatVec(mat a, vl b) { int n = b.size(); vl ret(n, 0); rep(i, n) rep(j, n) ret[j] = inff(ret[j] + inff(a[i][j] * b[i])); return ret; } ll isqrt(ll N) { ll sqrtN = sqrt(N) - 1; while (sqrtN + 1 <= N / (sqrtN + 1))sqrtN++; return sqrtN; } ll cross(pll l, pll r) { return l.first * r.second - l.second * r.first; } void rotate(vl& v) { v.push_back(v.front()); v.erase(v.begin()); } class ConvexHullDynamic { typedef long long coef_t; typedef long long coord_t; typedef long long val_t; /* * Line 'y=a*x+b' represented by 2 coefficients 'a' and 'b' * and 'xLeft' which is intersection with previous line in hull(first line has -INF) */ private: struct Line { coef_t a, b; double xLeft; enum Type { line, maxQuery, minQuery } type; coord_t val; explicit Line(coef_t aa = 0, coef_t bb = 0) : a(aa), b(bb), xLeft(-INFINITY), type(Type::line), val(0) {} val_t valueAt(coord_t x) const { return a * x + b; } friend bool areParallel(const Line& l1, const Line& l2) { return l1.a == l2.a; } friend double intersectX(const Line& l1, const Line& l2) { return areParallel(l1, l2) ? INFINITY : 1.0 * (l2.b - l1.b) / (l1.a - l2.a); } bool operator<(const Line& l2) const { if (this->type == maxQuery) return this->val < l2.xLeft; if (this->type == minQuery) return this->val > l2.xLeft; if (l2.type == line) return this->a < l2.a; if (l2.type == maxQuery) return this->xLeft < l2.val; if (l2.type == minQuery) return this->xLeft > l2.val; } }; bool isMax; //whether or not saved envelope is top(search of max value) public: std::set< Line > hull; //envelope itself private: /* * INFO: Check position in hull by iterator * COMPLEXITY: O(1) */ bool hasPrev(std::set< Line >::iterator it) { return it != hull.begin(); } bool hasNext(std::set< Line >::iterator it) { return it != hull.end() && std::next(it) != hull.end(); } /* * INFO: Check whether line l2 is irrelevant * NOTE: Following positioning in hull must be true * l1 is next left to l2 * l2 is right between l1 and l3 * l3 is next right to l2 * COMPLEXITY: O(1) */ bool irrelevant(const Line& l1, const Line& l2, const Line& l3) { return intersectX(l1, l3) <= intersectX(l1, l2); } bool irrelevant(std::set< Line >::iterator it) { return hasPrev(it) && hasNext(it) && (isMax && irrelevant(*std::prev(it), *it, *std::next(it)) || !isMax && irrelevant(*std::next(it), *it, *std::prev(it))); } /* * INFO: Updates 'xValue' of line pointed by iterator 'it' * COMPLEXITY: O(1) */ std::set< Line >::iterator updateLeftBorder(std::set< Line >::iterator it) { if (isMax && !hasPrev(it) || !isMax && !hasNext(it)) return it; double val = intersectX(*it, isMax ? *std::prev(it) : *std::next(it)); Line buf(*it); it = hull.erase(it); buf.xLeft = val; it = hull.insert(it, buf); return it; } public: explicit ConvexHullDynamic(bool isMax = false) : isMax(isMax) {} /* * INFO: Adding line to the envelope * Line is of type 'y=a*x+b' represented by 2 coefficients 'a' and 'b' * COMPLEXITY: Adding N lines(N calls of function) takes O(N*log N) time */ void addLine(coef_t a, coef_t b) { //find the place where line will be inserted in set Line l3 = Line(a, b); auto it = hull.lower_bound(l3); //if parallel line is already in set, one of them becomes irrelevant if (it != hull.end() && areParallel(*it, l3)) { if (isMax && it->b < b || !isMax && it->b > b) it = hull.erase(it); else return; } //try to insert it = hull.insert(it, l3); if (irrelevant(it)) { hull.erase(it); return; } //remove lines which became irrelevant after inserting line while (hasPrev(it) && irrelevant(std::prev(it))) hull.erase(std::prev(it)); while (hasNext(it) && irrelevant(std::next(it))) hull.erase(std::next(it)); //refresh 'xLine' it = updateLeftBorder(it); if (hasPrev(it)) updateLeftBorder(std::prev(it)); if (hasNext(it)) updateLeftBorder(std::next(it)); } val_t getBest(coord_t x) const { Line q; q.val = x; q.type = isMax ? Line::Type::maxQuery : Line::Type::minQuery; auto bestLine = hull.lower_bound(q); if (isMax) --bestLine; return bestLine->valueAt(x); } }; class treelib { public: mat es; vl stop; vl d; treelib(mat _es) : es(_es) { stop.resize(_es.size() + 1, 0); d.resize(_es.size() + 1); } /* * first: depth.second : leaf; */ pll deepest(ll x, ll f) { ll a = 0, b = -1; for (auto v : es[x]) { if (stop[v])continue; if (v == f)continue; d[v] = d[x] + 1; auto p = deepest(v, x); if (p.first > a) { a = p.first; b = p.second; } } if (b == -1) { return { 1,x }; } else { return { a + 1,b }; } } }; class treelib2 { public: vector<vpll> es; vl stop; vl d; treelib2(vector<vpll> _es) : es(_es) { stop.resize(_es.size() + 1, 0); d.resize(_es.size() + 1); } /* * first: depth.second : leaf; */ pll deepest(ll x, ll f) { ll a = 0, b = -1; for (auto v : es[x]) { ll t = v.first; if (stop[t])continue; if (t == f)continue; d[t] = d[x] + v.second; auto p = deepest(t, x); if (p.first > a) { a = p.first; b = p.second; } } if (b == -1) { return { 1,x }; } else { return { a + 1,b }; } } }; struct scompress { vl mapped, dup; map<ll, ll> mp; }; scompress compress(vl& v) { ll n = v.size(); vl b(n); rep(i, n) { b[i] = v[i]; } vsort(b); dup(b); map<ll, ll> mp; rep(i, b.size()) { mp[b[i]] = i; } vl res(n); rep(i, n) { res[i] = mp[v[i]]; } vl bb(b.size()); rep(i, b.size()) { bb[i] = mp[b[i]]; } return { res,bb,mp }; } using ld = double; using P = Point; template <class iter> Circle min_ball(iter left, iter right, int seed = 1333) { const int n = right - left; assert(n >= 1); if (n == 1) { return { *left, ld(0) }; } std::mt19937 mt(seed); std::shuffle(left, right, mt); // std::random_shuffle(left, right); // simple but deprecated iter ps = left; using circle = Circle; auto make_circle_3 = [](P& a, P& b, P& c) -> circle { ld A = (b - c).norm(), B = (c - a).norm(), C = (a - b).norm(), S = Point::cross(b - a, c - a); P p = (a * (A * (B + C - A)) + (b * B * (C + A - B)) + c * C * (A + B - C)) / (4 * S * S); ld r2 = (p - a).norm(); return { p, r2 }; }; auto make_circle_2 = [](P& a, P& b) -> circle { P c = (a + b) / (ld)2; ld r2 = (a - c).norm(); return { c, r2 }; }; auto in_circle = [](P& a, circle& c) -> bool { return (a - c.c).norm() <= c.r + EPS; }; circle c = make_circle_2(ps[0], ps[1]); // MiniDisc for (int i = 2; i < n; ++i) { if (!in_circle(ps[i], c)) { // MiniDiscWithPoint c = make_circle_2(ps[0], ps[i]); for (int j = 1; j < i; ++j) { if (!in_circle(ps[j], c)) { // MiniDiscWith2Points c = make_circle_2(ps[i], ps[j]); for (int k = 0; k < j; ++k) { if (!in_circle(ps[k], c)) { c = make_circle_3(ps[i], ps[j], ps[k]); } } } } } } return c; } vml2 kitamasadfs(vml2 a, vml2 d, ll n) { if (d.size() == n) return d; vml2 res(d.size()); if (n < d.size() * 2 || (n & 1)) { auto f = kitamasadfs(a, d, n - 1); res[0] = f[k - 1] * d[0]; rep2(i, 1, d.size()) { res[i] = f[i - 1] + f[k - 1] * d[i]; } } else { auto v = kitamasadfs(a, d, n / 2); matm2 f(d.size(), vml2(d.size())); f[0] = v; rep2(i, 1, d.size()) { f[i][0] = f[i - 1][k - 1] * d[0]; rep2(j, 1, d.size()) { f[i][j] = f[i - 1][j - 1] + f[i - 1][k - 1] * d[j]; } } rep(i, d.size()) { rep(j, d.size()) { res[j] += f[i][j] * v[i]; } } } return res; } modint1000000007 kitamasa(vml2 a, vml2 d, ll n) { auto v = kitamasadfs(a, d, n); modint1000000007 res = 0; rep(i, d.size()) { res += v[i] * a[i]; } return res; } void belman_temp(vector<vpll>& es, vl& d, ll s) { d[s] = 0; rep(i, n + 1) { queue<ll> q; rep2(j, 1, n + 1) { if (d[j] == big)continue; for (auto& v : es[j]) { if (chmin(d[v.first], d[j] + v.second)) { q.push(v.first); } } } if (i < n)continue; while (!q.empty()) { auto p = frontpop(q); for (auto& v : es[p]) { if (chmin(d[v.first], -big)) { q.push(v.first); } } } } } vl getpath(mat& es, vl& d, ll s, ll g) { vl res; ll x = s; while (x != g) { res.push_back(x); for (auto v : es[x]) { if (d[v] == d[x] - 1) { x = v; break; } } } res.push_back(x); reverse(all(res)); return res; } /// <summary> /// ベルマンフォード /// </summary> /// <param name="es"></param> /// <param name="d"></param> /// <param name="s"></param> bool belman(vector<vpll>& es, ll n, vl& d, ll s) { d.resize(n, big); d[s] = 0; rep(i, n) { bool e = false; rep(f, n) { if (d[f] == big)continue; for (auto& v : es[f]) { if (chmin(d[v.first], d[f] + v.second)) { e = true; } } } if (!e) break; } queue<ll> q; rep(f, n) { if (d[f] == big)continue; for (auto& v : es[f]) { if (chmin(d[v.first], d[f] + v.second)) { q.push(v.first); } } } bool e = false; while (!q.empty()) { auto p = frontpop(q); for (auto& v : es[p]) { if (d[v.first] > -big) { e = true; d[v.first] = -big; q.push(v.first); } } } return e; } template<class t> void put_line(vector<t>& p) { rep(i, p.size()) { cout << p[i] << " "; } cout << endl; } mat tablecut(ll h, ll w, vector<string> t) { ll top = 0; rep(i, h) { bool ok = true; rep(j, w) { if (t[i][j] == '#') { ok = false; break; } } if (!ok)break; top++; } ll bot = h; for (int i = h - 1; i >= 0; i--) { bool ok = true; rep(j, w) { if (t[i][j] == '#') { ok = false; break; } } if (!ok)break; bot--; } ll lf = 0; rep(i, w) { bool ok = true; rep(j, h) { if (t[j][i] == '#') { ok = false; break; } } if (!ok)break; lf++;; } ll ri = w; for (int i = w - 1; i >= 0; i--) { bool ok = true; rep(j, h) { if (t[j][i] == '#') { ok = false; break; } } if (!ok)break; ri--; } mat tb(bot - top, vl(ri - lf)); rep2(i, top, bot) { rep2(j, lf, ri) { if (t[i][j] == '#') { tb[i - top][j - lf] = 1; } } } return tb; } mat tablerotate(ll h, ll w, mat& a) { mat b(w, vl(h)); rep(i, h) { rep(j, w) { b[w - j - 1][i] = a[i][j]; } } return b; } ll rangeadd_op(ll l, ll r) { return max(l, r); } ll rangeadd_e() { return -big; } ll range_add_map(ll l, ll r) { if (l == -big)return r; if (r == -big)return l; return l + r; } ll range_add_comp(ll l, ll r) { return l + r; } ll rangeadd_id() { return 0; } ll rangesum_op(ll l, ll r) { return max(0LL, l) + max(0LL, r); } ll rsum_op(ll l, ll r) { return l + r; } ll rangesum_e() { return -big; } lazy_segtree<ll, rangeadd_op, rangeadd_e, ll, range_add_map, range_add_comp, rangeadd_id> create_range_add_st(ll n) { return lazy_segtree<ll, rangeadd_op, rangeadd_e, ll, range_add_map, range_add_comp, rangeadd_id>(n + 1); } lazy_segtree<ll, rangesum_op, rangesum_e, ll, range_add_map, range_add_comp, rangeadd_id> create_range_add_stv2(vl a) { return lazy_segtree<ll, rangesum_op, rangesum_e, ll, range_add_map, range_add_comp, rangeadd_id>(a); } class rolhash_lib { string s; vl v, p; ll n; public: rolhash_lib() { } rolhash_lib(string _s) : s(_s) { n = s.size(); v.resize(n + 1); p.resize(n + 1); p[0] = 1; rep(i, n) { v[i + 1] = calc_mod_61(mul_61(v[i], INF) + s[i]); p[i + 1] = mul_61(p[i], INF); } } ll get_hash(ll l, ll r) { l--; return calc_mod_61(v[r] + MOD * 4 - mul_61(v[l], p[r - l])); } }; long long llceil(long long a, long long b) { if (a % b == 0) { return a / b; } if (a >= 0) { return (a / b) + 1; } else { return -((-a) / b); } } long long llfloor(long long a, long long b) { if (a % b == 0) { return a / b; } if (a >= 0) { return (a / b); } else { return -((-a) / b) - 1; } } using pl = pair<long long, long long>; pl findseg(pl seg, long long ini, long long step) { if (step > 0) { return { llceil(seg.first - ini,step), llfloor(seg.second - ini,step) }; } else { step *= -1; return { llceil(ini - seg.second,step), llfloor(ini - seg.first,step) }; } } ll matsum(mat& a, ll i, ll j, ll x, ll y) { return a[i][j] - a[i - x][j] - a[i][j - y] + a[i - x][j - y]; } ll __parity(ll t) { ll c = 0; while (t > 0) { c += t & 1; t >>= 1; } return c % 2; } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } ll popcount(ll x) { ll c = 0; while (x > 0) { c += x & 1; x >>= 1; } return c; } struct centroid_decomposition { int n; int centor; mat G; vector<int>size; vector<vector<array<ll, 3>>>child; //child[i]=iが重心の木の、iを根としたときの子の(index,size,centoroid index) vector<bool>removed; //作業用 centroid_decomposition(mat& g) { G = g; n = G.size(); size.resize(n); child.resize(n); removed.resize(n); decompose(); }; int find_centroid(int v, int pre, int cnt) { // 残っている頂点でなす、vを含む連結成分における重心のindexを返す // early returnはせず、sizeの再計算を全部やる size[v] = 1; bool ok = true; int centor = -1; for (auto vv : G[v]) { if (vv == pre)continue; if (removed[vv])continue; centor = max(centor, find_centroid(vv, v, cnt)); size[v] += size[vv]; ok &= size[vv] <= cnt / 2; } ok &= cnt - size[v] <= cnt / 2; return ok ? v : centor; } int decompose_recursive(int v, int cnt) { int vv = find_centroid(v, -1, cnt); removed[vv] = true; for (auto vvv : G[vv])if (!removed[vvv]) { int bbc = size[vvv] < size[vv] ? size[vvv] : cnt - size[vv]; child[vv].push_back({ vvv,bbc,-1 }); } for (auto& item : child[vv])item[2] = decompose_recursive(item[0], item[1]); return vv; } void decompose() { centor = decompose_recursive(0, n); } }; template <typename T> vl argsort(const vector<T>& A) { // stable vl ids(A.size()); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); }); return ids; } // A[I[0]], A[I[1]], ... template <typename T> vector<T> rearrange(const vector<T>& A, const vl& I) { int n = A.size(); vector<T> B(n); rep(i, n) B[i] = A[I[i]]; return B; } bool intersection(ll f, ll t, ll ff, ll tt) { return !(tt <= f || t <= ff); } // ここまでライブラリ // ここからコード struct C { ll a, mi; }; struct O { ll l, r, q; }; struct S { ll sz, val; }; S op(S l, S r) { return { l.sz + r.sz,l.val + r.val }; } S e() { return { 0,0 }; } ll ore() { return 0; } S mapping(ll f, S s) { if (f == -1)return s; return { s.sz,f * s.sz }; } ll composition(ll ne, ll ol) { if (ne < 0)return ol; if (ol < 0)return ne; return ne; } ll id() { return -1; } ll opmin(ll l, ll r) { return min(l, r); } ll emin() { return big; } ll opma(ll l, ll r) { return max(l, r); } ll ema() { return -big; } ll mamapping(ll ne, ll o) { if (ne < 0)return o; return ne; } ll oppp(ll l, ll r) { return max(l, r); } ll ee() { return -big; } modint998244353 o1(modint998244353 l, modint998244353 r) { return l + r; } modint998244353 e1() { return 0; } struct F { ll lz = 0, lo = 0, rz = 0, ro = 0, mz = 0, mo = 0, len = 0; }; F ost(F l, F r) { if (l.len == -1)return r; if (r.len == -1)return l; ll lz = l.lz; ll lo = l.lo; ll rz = r.rz; ll ro = r.ro; if (rz == r.len) { rz += l.rz; } if (ro == r.len) { ro += l.ro; } if (lz == l.len) { lz += r.lz; } if (lo == l.len) { lo += r.lo; } ll sm = l.len + r.len; ll mo = max({ l.mo ,r.mo,l.ro + r.lo }); ll mz = max({ l.mz,r.mz, l.rz + r.lz }); return { lz,lo,rz,ro,mz,mo,sm }; } F est() { return { -1,-1,-1,-1,-1,-1,-1 }; } F maest(ll v, F s) { if (v % 2 == 0)return s; return { s.lo,s.lz,s.ro,s.rz,s.mo,s.mz,s.len }; } vl o157(vl l, vl r) { if (l.empty())return r; if (r.empty())return l; rep(i, 26) { r[i] += l[i]; } return r; } vl e157() { return {}; } double ops(double l, double r) { return l + r; } double ope() { return 0; } pair<vl, vl> opx(pair<vl, vl> l, pair<vl, vl> r) { if (l.first.empty())return r; if (r.first.empty())return l; vl cn(26), tn(26); for (int i = 25; i >= 0; i--) { cn[i] = l.first[i]; if (i < 25) { cn[i] += cn[i + 1]; if (r.first[i] > 0) r.second[i] += cn[i + 1]; } r.second[i] += l.second[i]; r.first[i] += l.first[i]; } return r; } pair<vl, vl> epx() { return { {},{} }; } char cnt[162000001]; pll op299(pll l, pll r) { if (l.first == -1)return r; if (r.first == -1)return l; if (l.first < r.first)return l; if (l.first > r.first)return r; if (l.second < r.second)return l; return r; } pll e299() { return { -1,-1 }; } pair<ull, ull> oprol(pair<ull, ull> l, pair<ull, ull> r) { pair<ull, ull> nx; nx.first = calc_mod_61(l.first + mul_61(r.first, l.second)); nx.second = mul_61(l.second, r.second); return nx; } pair<ull, ull> erol() { return { 0,1 }; } class rolhash_lib_2 { string s; vl v, p; ll n; public: //pair<ull, ull> op(pair<ull,ull> l, pair<ull, ull> r) { // if (l.first == 0)return r; // if (r.first == 0)return l; // pair<ull,ull> nx; // nx.first = calc_mod_61(mul_61(l.first, INF) + r.first); // nx.second = mul_61(mul_61(l.second, r.second), INF); // return nx; //} //pair<ull, ull> e() { // return { 0,0 }; //} segtree<pair<ull, ull>, oprol, erol> st; rolhash_lib_2(string _s) : s(_s) { n = s.size(); //v.resize(n + 1); //p.resize(n + 1); //p[0] = 1; vector<pair<ull, ull>> v(n); rep(i, n) { v[i].first = s[i]; v[i].second = INF; //v[i + 1] = calc_mod_61(mul_61(v[i], INF) + s[i]); //p[i + 1] = mul_61(p[i], INF); } st = segtree<pair<ull, ull>, oprol, erol>(v); } void set(ll x, char c) { st.set(x, { c,INF }); } ull get_hash(ll l, ll r) { l--; return st.prod(l, r).first; //return calc_mod_61(v[r] + MOD * 4 - mul_61(v[l], p[r - l])); } }; struct Fu { mint9 a = 1, b = 0; }; ll mapf(Fu f, ll v) { return (v*f.a+f.b).val(); } Fu comf(Fu ne, Fu ol) { return { ol.a*ne.a, ol.b*ne.a+ne.b }; } Fu idf() { Fu f; return f; } void solv() { /* 私は素因数分解を使うべきところで、エラトステネスを使ってハマりました。 私は「lからrまでを数としてみた時、7で割り切れるか?」を「lからrまでを数としてみた時、『各桁の和を』7で割り切れるか?」と誤解しました。 私は累積和を使うべきところで、遅延セグ木を使ってTLEを食らいました。 tをn進法にする時は素直にwhile(t>0)の条件で処理しよう 問題を誤読すると痛いよ! 愚直解テストはレンジの小さい範囲も入念に試しておきたい(https://atcoder.jp/contests/abc309/tasks/abc309_f) next_permutation使う時は基本的にはソートするんや m回接続(ループ)してその中を計算するタイプの問題、確定している分はしっかりmから引く事 ARCでは特に、愚直解との比較で間違っている箇所は出来る限り出す 中央値を使う総和の計算の左側は、カッコを忘れない事→x*lf-(s[i]-s[i-lf]) lazy_segtreeは分解した式で考える */ cin >> n; ll nn = 1LL << n; clineu(a, nn); vul b(n); rep(i, n) { b[i] = a[1LL << i]; } rep(i, nn) { ull g = 0; rep(j, n) { if (ion(i, j)) { g ^= b[j]; } } if (g != a[i]) { No; return; } } Yes; } int main() { cin.tie(0); ios::sync_with_stdio(false); INF = 998244353; solv(); return 0; }