結果
問題 | No.916 Encounter On A Tree |
ユーザー |
![]() |
提出日時 | 2019-10-25 22:42:01 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 8 ms / 2,000 ms |
コード長 | 1,912 bytes |
コンパイル時間 | 1,235 ms |
コンパイル使用メモリ | 148,656 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-30 15:31:03 |
合計ジャッジ時間 | 3,143 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 56 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>#include <algorithm>#include <utility>#include <functional>#include <cstring>#include <queue>#include <stack>#include <math.h>#include <iterator>#include <vector>#include <string>#include <set>#include <math.h>#include <iostream>#include <random>#include<map>#include <iomanip>#include <time.h>#include <stdlib.h>#include <list>#include <typeinfo>#include <list>#include <set>#include <cassert>#include<fstream>#include <unordered_map>#include <cstdlib>#include <complex>#include <cctype>#include <bitset>using namespace std;typedef string::const_iterator State;#define Ma_PI 3.141592653589793#define eps 1e-5#define LONG_INF 2000000000000000000LL#define GOLD 1.61803398874989484820458#define MAX_MOD 1000000007LL#define GYAKU 500000004LL#define MOD 998244353LL#define seg_size 262144*2#define REP(a,b) for(long long a = 0;a < b;++a)long long depth(long long now) {long long ans = 0;while (now != 0) {now /= 2;ans++;}return ans;}long long inv(long long now) {long long b = MAX_MOD - 2;long long ans = 1;while (b != 0) {if (b % 2) {ans *= now;ans %= MAX_MOD;}now *= now;now %= MAX_MOD;b /= 2;}return ans;}int main() {long long d, l, r, k;cin >> d >> l >> r >> k;k -= depth(r) - depth(l);int target = k / 2;if (k % 2 == 1 || depth(l) - target < 1||k < 0||(depth(l) == depth(r)&&k == 0)) {cout << 0 << endl;return 0;}long long ans = 1;for (long long i = 2; i <= d; ++i) {for (long long q = 1; q <= (1LL << (i - 1)); ++q) {ans *= q;ans %= MAX_MOD;}}if (depth(l) != depth(r)) {long long hoge = depth(l) - max(target - 1, 0) - 1;ans *= inv((1LL << hoge) % MAX_MOD);}else {long long hoge = (1LL << (depth(l) - 1)) - 1;ans *= inv(hoge);ans %= MAX_MOD;ans *= (1LL << (target - 1));}cout << ans%MAX_MOD << endl;}