結果
問題 | No.916 Encounter On A Tree |
ユーザー |
![]() |
提出日時 | 2019-10-25 23:17:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 9,721 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 129,248 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-13 08:42:16 |
合計ジャッジ時間 | 2,973 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 56 |
ソースコード
#include <algorithm>#include <bitset>#include <cassert>#include <chrono>#include <cmath>#include <complex>#include <cstdint>#include <fstream>#include <functional>#include <iomanip>#include <iostream>#include <limits>#include <list>#include <map>#include <queue>#include <random>#include <regex>#include <set>#include <sstream>#include <stack>#include <string>#include <sys/timeb.h>#include <vector>using namespace std;#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)#define rep(i, n) repr(i, 0, n)#define reprrev(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)#define reprev(i, n) reprrev(i, 0, n)#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)#define chmin(mi, value) mi = min(mi, value)#define chmax(ma, value) ma = max(ma, value)#define all(a) (a).begin(), (a).end()#define rall(a) (a).rbegin(), (a).rend()#define mp make_pair#define mt make_tuple#define INF 1050000000#define INFR INT_MAX#define INFL (long long)(4e18)#define INFLR LLONG_MAX#define EPS (1e-10)#define MOD 1000000007//#define MOD 998244353#define PI 3.141592653589793238#define RMAX 4294967295using vi = vector<int>;using vvi = vector<vector<int>>;using vvvi = vector<vector<vector<int>>>;using vvvvi = vector<vector<vector<vector<int>>>>;using ll = long long;using vll = vector<ll>;using vvll = vector<vector<ll>>;using vvvll = vector<vector<vector<ll>>>;using vd = vector<double>;using vvd = vector<vector<double>>;using vb = vector<bool>;using vvb = vector<vector<bool>>;using vc = vector<char>;using vvc = vector<vector<char>>;using vs = vector<string>;using vvs = vector<vector<string>>;using Pi = pair<int, int>;using vPi = vector<Pi>;using vvPi = vector<vector<Pi>>;using vvvPi = vector<vector<vector<Pi>>>;using vvvvPi = vector<vector<vector<vector<Pi>>>>;using Pll = pair<ll, ll>;using vPll = vector<Pll>;using Pd = pair<double, double>;using vPd = vector<Pd>;template <class T>using vec = vector<T>;template <class T>using pql = priority_queue<T, vector<T>, greater<T>>;using Comp = complex<double>;// vvvvvvvvvvvvvvvvvvvvvvv debug output vvvvvvvvvvvvvvvvvvvvvvv// vector inputtemplate <typename T>istream &operator>>(istream &is, vector<T> &vec) {for (T &x : vec) is >> x;return is;}// pairtemplate <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &pair_var) {os << "(" << pair_var.first << ", " << pair_var.second << ")";return os;}// vectortemplate <typename T>ostream &operator<<(ostream &os, const vector<T> &vec) {os << "{";for (int i = 0; i < vec.size(); i++) {os << vec[i] << (i + 1 == vec.size() ? "" : ", ");}os << "}";return os;}// dequetemplate <typename T>ostream &operator<<(ostream &os, const deque<T> &vec) {os << "{";for (int i = 0; i < vec.size(); i++) {os << vec[i] << (i + 1 == vec.size() ? "" : ", ");}os << "}";return os;}// maptemplate <typename T, typename U>ostream &operator<<(ostream &os, const map<T, U> &map_var) {os << "{";repi(itr, map_var) {os << *itr;itr++;if (itr != map_var.end()) os << ", ";itr--;}os << "}";return os;}// settemplate <typename T>ostream &operator<<(ostream &os, const set<T> &set_var) {os << "{";repi(itr, set_var) {os << *itr;itr++;if (itr != set_var.end()) os << ", ";itr--;}os << "}";return os;}// multisettemplate <typename T>ostream &operator<<(ostream &os, const multiset<T> &set_var) {os << "{";repi(itr, set_var) {os << *itr;itr++;if (itr != set_var.end()) os << ", ";itr--;}os << "}";return os;}#define DUMPOUT cerrvoid dump_func() {DUMPOUT << endl;}template <class Head, class... Tail>void dump_func(Head &&head, Tail &&... tail) {DUMPOUT << head;if (sizeof...(Tail) > 0) {DUMPOUT << ", ";}dump_func(std::move(tail)...);}#ifdef DEBUG_#define DEB#define dump(...) \DUMPOUT << " " << string(#__VA_ARGS__) << ": " \<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \<< endl \<< " ", \dump_func(__VA_ARGS__)#else#define DEB if (false)#define dump(...)#endif// ^^^^^^^^^^^^^^^^^^^^^^^ debug output ^^^^^^^^^^^^^^^^^^^^^^^string YN(bool y, int id = 0) {if (id) cout << id;return (y ? "YES" : "NO");}string yn(bool y, int id = 0) {if (id) cout << id;return (y ? "Yes" : "No");}string ON(bool y, int id = 0) {if (id) cout << id;return (y ? "OK" : "NG");}int dir4[4][2] = {{0, -1}, {-1, 0}, {1, 0}, {0, 1}};int dir8[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {-1, 0},{1, 0}, {-1, 1}, {0, 1}, {1, 1}};char dirchar[4] = {'<', '^', '>', 'v'};// [a,b)int irand(int a, int b) {static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));uniform_int_distribution<int> dist(a, b - 1);return dist(Rand);}// [a,b)double drand(int a, int b) {static mt19937 Rand(static_cast<unsigned int>(time(nullptr)));uniform_real_distribution<double> dist(a, b);return dist(Rand);}// https://qiita.com/IgnorantCoder/items/3101d6276e9bdddf872ctemplate <typename A, typename F>inline auto transform(const A &v, F &&f) {using result_type =decltype(std::declval<F>()(std::declval<typename A::value_type>()));vector<result_type> y(v.size());std::transform(std::cbegin(v), std::cend(v), std::begin(y), f);return y;}// generate vector which has multiple dimensiontemplate <class T>vector<T> make_v(size_t size, const T &init) {return vector<T>(size, init);}template <class... Ts>auto make_v(size_t size, Ts... rest) {return vector<decltype(make_v(rest...))>(size, make_v(rest...));}template <typename T>T Max(vector<T> a) {return *max_element(all(a));}template <typename T>T Min(vector<T> a) {return *min_element(all(a));}template <typename T>T Sum(vector<T> a) {return accumulate(all(a), (T)0);}// for counting using maptemplate <typename T>void Add(map<T, int> &m, T item) {if (m.find(item) == m.end()) {m[item] = 1;} else {m[item]++;}}// for counting using maptemplate <typename T>void Erase(map<T, int> &m, T item) {if (m.find(item) == m.end()) {} else {if (m[item] == 1) {m.erase(item);} else {m[item]--;}}}// get method for map with default valuetemplate <typename T, typename U>U Get(map<T, U> m, T key, U def) {if (m.find(key) == m.end()) {return def;} else {return m[key];}}template <typename T>inline bool Contains(const set<T> &t, const T &key) {return t.find(key) != t.end();}template <typename T, typename U>inline bool Contains(const map<T, U> &t, const T &key) {return t.find(key) != t.end();}template <class T>struct Edge {int from, to;T cost;Edge(int f, int t, T c) : from(f), to(t), cost(c) {}};template <class T>bool operator<(const Edge<T> e1, const Edge<T> e2) {return e1.cost < e2.cost || (e1.cost == e2.cost && e1.from < e2.from) ||(e1.cost == e2.cost && e1.from == e2.from && e1.to < e2.to);}template <class T>ostream &operator<<(ostream &os, const Edge<T> &edge) {os << "(" << edge.from << "->" << edge.to << ":" << edge.cost << ")";return os;}template <class T = int>class Graph {int n;bool directed;vector<vector<Edge<T>>> edges;public:Graph(int n, bool directed): n(n), directed(directed), edges(vector<vector<Edge<T>>>(n)) {}void add_edge(int s, int t, T cost) {edges[s].emplace_back(s, t, cost);if (!directed) {edges[t].emplace_back(t, s, cost);}}Graph() {}vector<Edge<T>> &operator[](size_t i) {return edges[i];}int size() const {return n;}};//======================================================long long powMod(long long x, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;}int depth(int n) {int ans = 0;while (n > 0) {ans++;n >>= 1;}return ans;}int main() {int d, l, r, k;cin >> d >> l >> r >> k;int dl = depth(l);int dr = depth(r);if (k - (dr - dl) < 0 || (k - (dr - dl)) % 2 != 0) {cout << 0 << endl;return 0;}int dlca = dl - (k - (dr - dl)) / 2;if (dlca < 1) {cout << 0 << endl;return 0;}dump(dl, dr, dlca);ll ans = 1;(ans *= powMod(2, dlca - 1, MOD)) %= MOD; // lcadump(ans);if (dlca == dl) {if (dl == dr) {cout << 0 << endl;return 0;}(ans *= powMod(2, dr - dlca, MOD)) %= MOD; // rdump(ans);} else {(ans *= powMod(2, dl - dlca, MOD)) %= MOD; // ldump(ans);(ans *= powMod(2, dr - dlca - 1, MOD)) %= MOD; // rdump(ans);}repr(e, 1, d + 1) {int n = 1 << (e - 1);if (dl == e) n--;if (dr == e) n--;dump(n);repr(f, 1, n + 1) {(ans *= f) %= MOD;}dump(ans);}cout << ans << endl;return 0;}