結果
問題 | No.916 Encounter On A Tree |
ユーザー |
|
提出日時 | 2019-03-19 00:59:46 |
言語 | C++11 (gcc 13.3.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,606 bytes |
コンパイル時間 | 1,098 ms |
コンパイル使用メモリ | 98,056 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-09-19 00:44:44 |
合計ジャッジ時間 | 3,356 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 55 WA * 1 |
ソースコード
#include <iostream>#include <fstream>#include <cmath>#include <cstdlib>#include <ctime>#include <algorithm>#include <numeric>#include <functional>#include <string>#include <vector>#include <bitset>#include <map>#include <set>#include <stack>#include <queue>#include <deque>#include <random>#include <chrono>using namespace std;using ll = long long;using ull = unsigned long long;#define REP(i,n) for(long long i = 0; i < (n); i++)#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)#define ALL(obj) (obj).begin(),(obj).end()template<class T> using V = vector<T>;template<class T, class U> using P = pair<T, U>;const ll MOD = (ll)1e9 + 7;const ll MOD2 = 998244353;const ll LLINF = (ll)1e18;const ll INTINF = (ll)1e9;const long double PI = 3.1415926535897932384626433;template <class T> void corner(bool flg, T hoge) { if (flg) { cout << hoge << endl; exit(0); } }template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) { o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o; }template <class T>ostream &operator<<(ostream &o, const set<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) { o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "")<< obj[i]; o << "}"; return o; }template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) { o << "{" << obj.first << ", " << obj.second << "}"; return o; }template <template <class tmp> class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) { o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o; }void print(void) { cout << endl; }template <class Head> void print(Head&& head) { cout << head; print(); }template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) { cout << head << " "; print(forward<Tail>(tail)...); }template <class T> void chmax(T& a, const T b) { a = max<T>(a, b); }template <class T> void chmin(T& a, const T b) { a = min<T>(a, b); }void YN(bool flg) { cout << ((flg) ? "YES" : "NO") << endl; }void Yn(bool flg) { cout << ((flg) ? "Yes" : "No") << endl; }void yn(bool flg) { cout << ((flg) ? "yes" : "no") << endl; }//Factorial_Modvector<long long> Factorial_Mod(long long N, long long mod) {vector<long long> res(N + 1, 1);for (long long i = 1; i <= N; ++i) res[i] = (res[i - 1] * i) % mod;return res;}int main() {int d, l, r, k,MAXD = 20;cin >> d >> l >> r >> k;V<int> pow2(MAXD + 1, 1), sum2(MAXD + 1, 0);for (int i = 2; i < MAXD+1; ++i) pow2[i] = pow2[i - 1] * 2;for (int i = 1; i < MAXD+1; ++i) sum2[i] = sum2[i - 1] + pow2[i];auto fac = Factorial_Mod(pow2[MAXD], MOD);l = lower_bound(ALL(sum2), l) - sum2.begin();r = lower_bound(ALL(sum2), r) - sum2.begin();ll cnt = 1, ans = 2;int c = 0;if ((l + r - k) > 1 && (l + r - k) % 2 == 0) c = (l + r - k) / 2;if (c == 0) ans = 0;for (int i = 1; i <= d; ++i) {ll tmp = pow2[i];if (i == l) tmp--;if (i == r) tmp--;(cnt *= fac[tmp]) %= MOD;}(ans *= cnt) %= MOD;(ans *= pow2[l - c]) %= MOD;(ans *= pow2[r - c]) %= MOD;(ans *= pow2[c]) %= MOD;cout << ans << endl;return 0;}