#398457 (C++14) No.916 Encounter On A Tree

提出ソース

結果

問題	No.916 Encounter On A Tree
ユーザー	ningenMe
提出日時	2019-11-17 19:39:19
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	11 ms / 2,000 ms
コード長	4,353 bytes
コンパイル時間	1,600 ms
コンパイル使用メモリ	172,200 KB
実行使用メモリ	11,572 KB
最終ジャッジ日時	2024-09-25 06:03:47
合計ジャッジ時間	3,668 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	10 ms 11,352 KB
testcase_01	AC	10 ms 11,392 KB
testcase_02	AC	10 ms 11,348 KB
testcase_03	AC	10 ms 11,404 KB
testcase_04	AC	11 ms 11,372 KB
testcase_05	AC	10 ms 11,364 KB
testcase_06	AC	10 ms 11,444 KB
testcase_07	AC	11 ms 11,488 KB
testcase_08	AC	10 ms 11,508 KB
testcase_09	AC	10 ms 11,412 KB
testcase_10	AC	11 ms 11,376 KB
testcase_11	AC	10 ms 11,508 KB
testcase_12	AC	11 ms 11,372 KB
testcase_13	AC	11 ms 11,388 KB
testcase_14	AC	11 ms 11,376 KB
testcase_15	AC	10 ms 11,472 KB
testcase_16	AC	11 ms 11,388 KB
testcase_17	AC	10 ms 11,404 KB
testcase_18	AC	11 ms 11,452 KB
testcase_19	AC	10 ms 11,528 KB
testcase_20	AC	11 ms 11,528 KB
testcase_21	AC	10 ms 11,572 KB
testcase_22	AC	10 ms 11,388 KB
testcase_23	AC	10 ms 11,452 KB
testcase_24	AC	11 ms 11,348 KB
testcase_25	AC	10 ms 11,500 KB
testcase_26	AC	10 ms 11,456 KB
testcase_27	AC	10 ms 11,412 KB
testcase_28	AC	10 ms 11,352 KB
testcase_29	AC	11 ms 11,348 KB
testcase_30	AC	10 ms 11,456 KB
testcase_31	AC	10 ms 11,492 KB
testcase_32	AC	10 ms 11,412 KB
testcase_33	AC	10 ms 11,412 KB
testcase_34	AC	11 ms 11,412 KB
testcase_35	AC	10 ms 11,496 KB
testcase_36	AC	10 ms 11,388 KB
testcase_37	AC	10 ms 11,404 KB
testcase_38	AC	10 ms 11,456 KB
testcase_39	AC	10 ms 11,392 KB
testcase_40	AC	10 ms 11,512 KB
testcase_41	AC	10 ms 11,220 KB
testcase_42	AC	10 ms 11,484 KB
testcase_43	AC	10 ms 11,416 KB
testcase_44	AC	10 ms 11,528 KB
testcase_45	AC	10 ms 11,556 KB
testcase_46	AC	11 ms 11,412 KB
testcase_47	AC	11 ms 11,384 KB
testcase_48	AC	11 ms 11,488 KB
testcase_49	AC	10 ms 11,500 KB
testcase_50	AC	10 ms 11,512 KB
testcase_51	AC	11 ms 11,348 KB
testcase_52	AC	11 ms 11,392 KB
testcase_53	AC	10 ms 11,352 KB
testcase_54	AC	10 ms 11,416 KB
testcase_55	AC	10 ms 11,552 KB
testcase_56	AC	10 ms 11,516 KB
testcase_57	AC	10 ms 11,504 KB
testcase_58	AC	11 ms 11,412 KB
testcase_59	AC	11 ms 11,496 KB
testcase_60	AC	10 ms 11,492 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;


template<long long mod> class ModInt {
public:
	long long x;
	ModInt():x(0) {
		// do nothing
	}
	ModInt(long long y) : x(y>=0?(y%mod): (mod - (-y)%mod)%mod) {
		// do nothing
	}
	ModInt &operator+=(const ModInt &p) {
		if((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator+=(const long long y) {
        ModInt p(y);
		if((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator+=(const int y) {
        ModInt p(y);
		if((x += p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator-=(const ModInt &p) {
		if((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator-=(const long long y) {
        ModInt p(y);
		if((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator-=(const int y) {
        ModInt p(y);
		if((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	ModInt &operator*=(const ModInt &p) {
		x = (x * p.x % mod);
		return *this;
	}
	ModInt &operator*=(const long long y) {
        ModInt p(y);
		x = (x * p.x % mod);
		return *this;
	}
	ModInt &operator*=(const int y) {
        ModInt p(y);
		x = (x * p.x % mod);
		return *this;
	}
	ModInt &operator/=(const ModInt &p) {
		*this *= p.inv();
		return *this;
	}
	ModInt &operator/=(const long long y) {
        ModInt p(y);
		*this *= p.inv();
		return *this;
	}
	ModInt &operator/=(const int y) {
        ModInt p(y);
		*this *= p.inv();
		return *this;
	}
	ModInt operator=(const int y) const {
        ModInt p(y);
        *this = p;
        return *this;
    }
    ModInt operator=(const long long y) const {
        ModInt p(y);
        *this = p;
        return *this;
    }
	ModInt operator-() const { return ModInt(-x); }
	ModInt operator++() { 
        x++;
        if(x>=mod) x-=mod;
        return *this; 
    }
	ModInt operator--() { 
        x--;
        if(x<0) x+=mod;
        return *this; 
    }
	ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
	ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
	ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
	ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
	bool operator==(const ModInt &p) const { return x == p.x; }
	bool operator!=(const ModInt &p) const { return x != p.x; }
	ModInt inv() const {
		int a = x, b = mod, u = 1, v = 0, t;
		while(b > 0) {
			t = a / b;
			swap(a -= t * b, b);
			swap(u -= t * v, v);
		}
		return ModInt(u);
	}
	ModInt pow(long long n) const {
		ModInt ret(1), mul(x);
		while(n > 0) {
			if(n & 1) ret *= mul;
			mul *= mul;
			n >>= 1;
		}
		return ret;
	}
	friend ostream &operator<<(ostream &os, const ModInt &p) {
		return os << p.x;
	}
	friend istream &operator>>(istream &is, ModInt &a) {
		long long t;
		is >> t;
		a = ModInt<mod>(t);
		return (is);
	}
};
using modint = ModInt<MOD>;

int main() {
	int d, l, r, k;
    int MAX_d = 20;
	cin >> d >> l >> r >> k;
	vector<modint> fac((1<<MAX_d) + 1,1);
    vector<int> pow2(MAX_d + 1, 1),sum(MAX_d + 1, 0);
	//2冪を前計算
	for (int i = 2; i < MAX_d + 1; ++i) pow2[i] = pow2[i - 1] * 2;
	//2冪の和を前計算
	for (int i = 1; i < MAX_d + 1; ++i) sum[i] = sum[i - 1] + pow2[i];
	//階乗を前計算
	for (long long i = 1; i < (1 << MAX_d) + 1; ++i) fac[i] = fac[i-1] * modint(i);
	//l,rを深さに変換
	l = lower_bound(sum.begin(), sum.end(), l) - sum.begin();
	r = lower_bound(sum.begin(), sum.end(), r) - sum.begin();

	int lca = -1;

	//lcaが存在するならそのlcaの深さを計算
	if ((l + r - k) > 1 && (l + r - k) % 2 == 0) lca = (l + r - k) / 2;

	//lcaが条件を満たしていない場合コーナー
	if(lca == -1 || lca > l || lca > r){
		cout << 0 << endl;
		return 0;
	}

	modint ans = 1;
	//上の段からl,r以外の頂点の順列の数え上げ
	for (int i = 1; i <= d; ++i) {
		int cnt = pow2[i];
		if (i == l) cnt--;
		if (i == r) cnt--;
		ans *= fac[cnt];
	}
	
	//lcaとなるような頂点の位置についての数え上げ
	ans *= pow2[lca];
	//lcaを決め打ちした時のlの位置についての数え上げ
	ans *= pow2[l - lca];
	//lcaを決め打ちした時のrの位置についての数え上げ
	ans *= pow2[r - lca];
	//lcaについて、子は左右について2通りのパターンがあるため
	ans *= 2;

	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード