2020-09-22

AOJ 3190 Ribbons on A Perfect Binary Tree (AUPC 2020 day3-F)

AOJ ACPC 数え上げ問題木探索順序を工夫して解く二項係数累積和選択肢が広い方か狭い方から決めていく各地点について自由度を掛け算していく

こういうのは探索順序を適切に定めることがめっちゃ重要！

問題概要

高さ $N$ の完全二分木と、

長さが 2 のリボンが $a_{1}$ 本
長さが 4 のリボンが $a_{2}$ 本
...
長さが $2N$ のリボンが $a_{N}$ 本

が与えられる。各リボンは、完全二分木において「葉」と「葉」を始点と終点とするパスに飾り付けたい (下図のように)。ただし、どの 2 本のリボンも node-disjoint となるようにしたい。そのような方法が何通りあるか、998244353 で割ったあまりを求めよ。

f:id:drken1215:20200922125403p:plain

制約

$1 \le N \le 2000$
$0 \le a_{i} \le 2000$

考えたこと

とりあえずまずは長さが $2i$ のリボンを 1 本飾りつける方法の数を数え上げてみる。このとき、

リボンの折り返し地点となるノードは、 $2^{N - i}$ 通りありうる
そこから深さ 1 だけ潜るときには選択肢の自由度はない (1 通り)
そこから深さ 1 だけ潜るときには左右それぞれ 2 通りずつの選択肢がある
そこから深さ 1 だけ潜るときには左右それぞれ 2 通りずつの選択歳がある
...

というわけで、 $2^{N-i} \times 2^{2(i - 1)}$ 通りとなる。

リボンが長い方から決めていく

次に複数のリボンを飾り付けていく方法を考えていく。ここで、リボンが長い方から順に決めていくことがポイントになる。短い方からやると上手くいかなかった。

さて、まず長さ $2N$ のリボンが 2 本以上あったらダメで、1 本あったときにそれを飾り付けたとする。このとき

深さ 1 のノードで選べるやつは 2 減って、 $2^{1} -2 = 0$ 個になる
深さ 2 のノードで選べるやつは 2 減って、 $2^{2} - 2 = 2$ 個になる
深さ 3 のノードで選べるやつは 2 減って、 $2^{3} - 2 = 6$ 個になる
...

というふうになる。つまり、浅い方で飾り付けを行うと、それよりも深いところではノードが 2 個ずつ潰されていくイメージ！！よって、次のように考えることができる。よって、長いリボンから順に考えて行って、

長さが $2i$ のリボンについて考えているとき、すでにそれより長いリボンが $s$ 個飾られているとする
長さが $2i$ のリボンを折り返し地点として飾るのに残されているノードの個数は、 $2^{N-i} - s$ 個である
それらから $a_{i}$ 個選ぶ場合の数は $P(2^{N-i} - s, a_{i})$ 通り ( $P$ は順列)
それぞれ飾り付け方を考慮して $(2^{2(i - 1)})^{a_{i}}$ 通り

というふうに考えれば OK。以下の実装では $a$ を reverse して考えているので、添字の扱いが少し変わっている。

#include <bits/stdc++.h>
using namespace std;

// modint
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() const { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b, swap(a, b);
            u -= t * v, swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr istream& operator >> (istream &is, Fp<MOD>& x) noexcept {
        is >> x.val;
        x.val %= MOD;
        if (x.val < 0) x.val += MOD;
        return is;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

const int MOD = 998244353;
using mint = Fp<MOD>;

// Binomial coefficient
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

BiCoef<mint> bc;

int main() {
    int N;
    cin >> N;
    vector<int> a(N), s(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> a[N-i-1];
    for (int i = 0; i < N; ++i) s[i+1] = s[i] + a[i];

    mint res = 1;
    for (int i = 0; i < N; ++i) {
        mint two = modpow(mint(2), (N - i - 1) * 2);
        mint jiyudo = modpow(two, a[i]);
        mint choice = 1;
        mint cur = modpow(mint(2), i) - s[i] * 2;
        for (int j = 0; j < a[i]; ++j) {
            choice *= cur;
            cur -= 1;
        }
        res *= choice * jiyudo;
    }
    cout << res << endl;
}