Encounter On A Tree [yukicoder 916]

https://yukicoder.me/problems/no/916

解説

https://yukicoder.me/submissions/393553

dがとても小さいので、深さ起点で考えれば良さそうな感じがする。
lが書き込まれる頂点の深さ、rが書き込まれる頂点の深さ、その2つのlcaの深さを全探索して、組み合わせ計算？
行けそうですね。

それぞれの深さをdl, dr, dlcaとして、深さがわかれば距離がわかるので、その距離がKであるかをまず確かめる。
後は、根性で（場所の組み合わせ）×（数の組み合わせ）を答える。
ある深さでの上限lft, 下限rhtと数の個数cntを用意すると実装が少し楽。

int D, L, R, K;
Comb<mint, 2010101> com;
int lft[21], rht[21];
int cnt[21];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> D >> L >> R >> K;

    lft[1] = rht[1] = 1;
    rep(d, 1, D) {
        lft[d + 1] = lft[d] * 2;
        rht[d + 1] = lft[d + 1] * 2 - 1;
    }
    rep(d, 1, D + 1) cnt[d] = rht[d] - lft[d] + 1;

    mint ans = 0;
    rep(dl, 1, D + 1) rep(dr, 1, D + 1) rep(dlca, 1, D + 1) {
        if (dlca > dl) continue;
        if (dlca > dr) continue;
        if ((dl - dlca) + (dr - dlca) != K) continue;

        if (lft[dl] <= L and L <= rht[dl] and lft[dr] <= R and R <= rht[dr]) {
            mint delta = 1;

            if (dl == dr) {
                delta *= cnt[dlca];
                delta *= cnt[dl] / cnt[dlca];
                delta *= cnt[dl] / cnt[dlca];
                delta /= 2;
            }
            else if (dl == dlca) {
                delta *= cnt[dlca];
                delta *= cnt[dr] / cnt[dlca];
            }
            else if (dr == dlca) {
                delta *= cnt[dlca];
                delta *= cnt[dl] / cnt[dlca];
            }
            else {
                delta *= cnt[dlca];
                delta *= cnt[dl] / cnt[dlca];
                delta *= cnt[dr] / cnt[dlca];
                delta /= 2;
            }

            rep(d, 1, D + 1) {
                if (dl == d and dr == d) delta *= com.fac[cnt[d] - 2];
                else if (dl == d or dr == d) delta *= com.fac[cnt[d] - 1];
                else delta *= com.fac[cnt[d]];
            }

            ans += delta;
        }
    }
    cout << ans << endl;
}