ограничение по времени на тест 2 секунды ограничен...

Question

ограничение по времени на тест 2 секунды
ограничение по памяти на тест 256 мегабайт
Рассмотрим бинарные деревья, в которых у каждой вершины не более двух детей и каждая вершина помечена либо 0, либо 1.

За одну операцию можно инвертировать все метки на любом простом пути, проходящем через корень. Инвертировать метку означает заменить 0 на 1, а 1 на 0. Заметьте, что путь длины 1, содержащий только корень, тоже разрешён.

Стоимость такого бинарного дерева определяется как минимальное число операций, необходимое для того, чтобы сделать все метки в дереве равными 0.

Даны два целых числа 𝑛 и 𝑘. Посчитайте количество различных бинарных деревьев ровно с 𝑛 вершинами и стоимостью ровно 𝑘. Так как ответ может быть очень большим, выведите его по модулю 10^9+7.

Два бинарных дерева считаются различными, если у них различается структура, либо если структура одинакова, но хотя бы в одной вершине различаются метки.

Входные данные
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число 𝑡 (1≤𝑡≤10^4) — количество наборов входных данных. Далее следует описание наборов входных данных.

В единственной строке каждого набора входных данных содержатся два целых числа 𝑛 и 𝑘 (1≤𝑛≤10^6, 0≤𝑘≤𝑛).

Гарантируется, что сумма значений 𝑛 по всем наборам входных данных не превосходит 10^6.

Выходные данные
Для каждого набора входных данных выведите на отдельной строке одно целое число — количество помеченных бинарных деревьев с 𝑛 вершинами и стоимостью 𝑘 по модулю 10^9+7.

Пример
входные данныеСкопировать
6
2 0
2 1
1 1
7 6
69 67
314159 42
выходные данныеСкопировать
2
4
1
2016
382216284
559671824
Примечание
В первом наборе входных данных имеем 𝑛=2 и 𝑘=0. Существует два возможных дерева — корень с левым ребёнком и корень с правым ребёнком. Поскольку нужна стоимость 0, все вершины должны быть помечены 0. Следовательно, ответ равен 2.

Во втором наборе входных данных имеем 𝑛=2 и 𝑘=1. Таких деревьев 4. Допустимые помеченные деревья показаны на рисунке ниже:

В третьем наборе входных данных имеем 𝑛=1 и 𝑘=1. Существует только одно дерево — одна корневая вершина с меткой 1. Следовательно, ответ равен 1.

Реши на с++

I'm testing if A_nk follows a form involving Catalan numbers or powers of 2. I’ve noticed that for k=1, A_n1 seems to follow the pattern 4^(n-1). For k=2, the values grow rapidly, and I wonder if there's a binomial connection. Maybe I can derive a recurrence or check OEIS for hints.{0, 1}.

I’m trying to figure out if A[n,n] follows a pattern similar to Catalan numbers. The pattern I see seems to match twice the Catalan sequence for most values: 2 * Catalan_{n-1}. I’ll need to test this hypothesis more systematically and potentially derive it from generating functions and Lagrange’s formula.ves and binomial coefficients. I need to verify if this works for all k.bash -lc python3 - <<'PY' import sympy as s z=s.symbols('z') C=(1-s.sqrt(1-4z))/(2z) q=C-1 for k in [1,2,6]: S=lambda m: (1-q**(m+1))/s.sqrt(1-4z) if m>=0 else 0 T=s.expand(z(s.simplify(S(k)2 - S(k-2)2))) series=s.series(T,z,0,10) print('k',k,series) Tq=s.simplify((1+q)/(1-q)(2qk - q(2k-1)-q**(2k+1))) print('equal?', s.simplify(T-Tq)==0) PY

Revisiting recurrence formula and coefficients

Hmm, it seems like the series from T_k isn’t matching the data from brute force calculations. For k=1 and n=7, I got 2002 instead of 4096. When I check my T_k formula, it seems connected to a different sequence, maybe D(k) instead of A. I’ll revisit my recurrence, as my earlier formula seems off for A_nk. Let me recheck.

Aha, it seems the S1 formula is giving Catalans, not cumulative. The formula might be correct for the ratio, but I think I misspoke regarding the relationship between q and z C^2. The sum I used still needs some adjustments since the resulting series is off by one. Let's refine the derivation, especially for different values of m and n, to make sure we're counting correctly.

MOD=10**9+7
from functools import lru_cache
def cat(n):
import math
from math import comb
return comb(2n,n)//(n+1)
def A(n,k):
B=[[0](n+1) for _ in range(n+1)]
C=[[0]*(n+1) for _ in range(n+1)]
# B one-arm
B[0][0]=1
for m in range(1,n+1):
for i in range(m):
j=m-1-i
for a in range(i+1):
if B[i][a]==0: continue
for b in range(j+1):
if B[j][b]==0: continue
s=a+b
B[m][s]+=B[i][a]*B[j][b]
B[m][s+1]+=B[i][a]*B[j][b]
C[0][0]=1
for m in range(1,n+1):
for i in range(m):
j=m-1-i
for a in range(i+1):
if B[i][a]==0: continue
for b in range(j+1):
if B[j][b]==0: continue
t=max(a,b)
C[m][t]+=B[i][a]*B[j][b]
C[m][t+1]+=B[i][a]*B[j][b]
return C[n][k],B[n]
for n in range(1,8):
vals=[]
for k in range(n+1):
vals.append(A(n,k)[0])
print(n, vals, 'cat',cat(n), 'B?',A(n,min(n,0))[1][:n+1])

Нашёл удобную промежуточную модель.

Есть две похожие “стоимости”:

если можно инвертировать только путь от корня к одной вершине, это даёт очень простую биномиальную формулу;
исходная задача получается из неё через свёртку по левому и правому поддереву.
Сейчас дожимаю эту свёртку до закрытой формулы/быстрого DP.bash -lc python3 - <<'PY' from math import comb

def compute(nmax): B=[0 for _ in range(nmax+1)] A=[0 for _ in range(nmax+1)] B[0][0]=1 A[0][0]=1 for n in range(1,nmax+1): for i in range(n): j=n-1-i for a,v1 in enumerate(B[i]): if not v1: continue for b,v2 in enumerate(B[j]): if not v2: continue s=a+b B[n][s]+=v1v2 B[n][s+1]+=v1v2 t=max(a,b) A[n][t]+=v1v2 A[n][t+1]+=v1v2 return A,B A,B=compute(8) for n in range(1,8): print('n',n,'A',A[n][:n+1]) print('n',n,'B',B[n][:n+1]) PY

Simplifying generating function expression

I'm realizing the expression is a bit messy, but simplifying the square root gives a clearer form:
1
−
q
1
+
q
1+q
1−q

. Now, I'll substitute this back into the equation. For
a
≥
1
a≥1, the formula might involve a Catalan polynomial, so I'll simplify it manually to see if I can spot any patterns.bash -lc python3 - <<'PY' import sympy as s q,u=s.symbols('q u') z=q/(1+q)*2 srt=(1-q)/(1+q) H=(1-srts.sqrt(1-4qu/(1-q)**2))/(2q(1+u)/(1+q)**2) # maybe not exact

let's just substitute sqrt simplification in previous H

H=(1-((1-q)/(1+q))s.sqrt(1-4qu/(1-q)*2))/(2q(1+u)/(1+q)**2) H=s.simplify(H) print('H=',H) for a in range(5): Ea=s.simplify(s.series(H,u,0,a+1).removeO().coeff(u,a)) print('a',a, s.factor(Ea)) PY

Working on generating function and pattern recognition

So, I have this formula for
E
a
(
q
)
E
a

(q), with some expressions for small values of
a
a, but the polynomials might relate to Narayana/Catalan numbers — not sure if it's needed though. Let's focus on simplifying the inner sum and computing pair counts. I’ll look at generating functions
J
a
,
b
(
z
)
J
a,b

(z) and explore how to connect them to simpler forms with polynomials and powers of
(
1
+
q
)
(1+q) and
(
1
−
q
)
(1−q). Let me test a few small
k
k values for clues.bash -lc python3 - <<'PY' import sympy as s q,u=s.symbols('q u') z=q/(1+q)**2 H=(1-s.sqrt(1-4z(1+u)))/(2z(1+u)) for k in range(5): G=s.simplify(sum(s.series(H,u,0,k+1).removeO().coeff(u,a) for a in range(k+1))) print('k',k, s.factor(G)) PY

derive Gk by solving from known z-series maybe? Use H expansion but substitute sqrt=(1-q)/(1+q)

let's directly use formulas from E_a simplified and sum.

E=[1+q, q*(1+q)/(1-q), q2*(2-q)(1+q)/(1-q)3, q3(q2-4q+5)(1+q)/(1-q)**5] for k in range(4): G=sum(E[:k+1]) print('G',k,s.factor(s.together(G))) A2=s.simplify(q/(1+q)**2 * (G.subs(k,2) if False else 0)) PY

I’m considering deriving the generating function for
A
k
A
k

directly through Lagrange’s method or by interpreting labeled tree counts via Schröder/ballot numbers. I’ll try using recurrence on tree counts and an exact bivariate generating function to avoid needing a closed form for
G
k
G
k

. Let’s investigate further.

Answer 1

Ниже — решение на C++ с выводом формулы за O(1) предусчёт + O(min(k, n-k+1)) на запрос.
Так как k <= n, а сумма всех n не больше 10^6, суммарная сложность O(10^6).

Идея

Для вершины v введём новую метку

b_v = a_v \oplus a_{left(v)} \oplus a_{right(v)},

где у отсутствующего ребёнка метка считается 0.

Это преобразование биективно: по всем b_v исходные a_v восстанавливаются снизу вверх.

Теперь важно следующее:

если разрешены только пути вида root -> x, то операция меняет ровно один b_x;
значит, для фиксированной формы дерева число разметок с ровно t единицами среди b равно просто $\binom{n}{t}$ .

Обозначим

B_{n,t} = Cat_n \binom{n}{t},

где Cat_n — число форм бинарных деревьев из n вершин.

Как выглядит исходная операция в новых метках

Если выбрать путь через корень:

только в левое поддерево — меняется один b слева;
только в правое — один b справа;
корень-корень — только b_root;
левый конец + правый конец — меняются:
- один b слева,
- один b справа,
- b_root.

Пусть в левом поддереве среди b ровно x единиц, в правом — y, а в корне b_root = c.

Тогда оптимально:

спарить min(x,y) единиц слева и справа,
остаток убрать одиночными путями,
в конце, возможно, убрать корень.

Стоимость равна

\max(x,y) + (c \oplus ( \min(x,y)\bmod 2)).

Значит, для фиксированных x,y два возможных значения c дают стоимости:

max(x,y)
max(x,y)+1

ровно по одному разу.

Генерирующие функции

Пусть

C(z)=\sum_{n\ge 0} Cat_n z^n = \frac{1-\sqrt{1-4z}}{2z},

H(z,u)=\sum_{n,t\ge 0} B_{n,t} z^n u^t = C(z(1+u)).

После подстановки

q = C(z)-1,\qquad x=\frac{q}{(1-q)^2}=\frac{z}{1-4z},

получается удобная формула, из которой после суммирования префиксов выводится

F_k(z)=\sum_{n\ge 1} A_{n,k} z^n = 2[k\text{ чётно}]\,Cat_{k-1}\,x^k(1-q) + 2Cat_{k-1}\!\!\sum_{\substack{1\le j\le k\\ j\equiv k\pmod 2}}\!\!Cat_{j-1}x^{k+j-1} - Cat_{k-1}^2x^{2k-1}.

Остаётся взять коэффициенты.

Нужные коэффициенты

Для $m\ge 1$ :

[z^n]\,x^m = [z^n]\left(\frac{z}{1-4z}\right)^m = 4^{\,n-m}\binom{n-1}{m-1}.

Для чётного k:

[z^n]\,x^k(1-q) = \frac12\Big( [z^{n-k+1}](1-4z)^{-(k-\frac12)} - [z^{n-k+1}](1-4z)^{-(k-1)} \Big),

то есть

[z^n]\,x^k(1-q) = \frac12\left( \frac{(2n)!(k-1)!}{n!(2k-2)!(n-k+1)!} - 4^{\,n-k+1}\binom{n-1}{k-2} \right).

Отсюда уже получается формула, которую можно считать за O(min(k,n-k+1)).

Код C++

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

static const int MOD = 1000000007;

long long mod_pow(long long a, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    vector<pair<int,int>> qs(T);
    int maxN = 0;
    for (int i = 0; i < T; ++i) {
        int n, k;
        cin >> n >> k;
        qs[i] = {n, k};
        maxN = max(maxN, n);
    }

    // factorials up to 2*maxN
    vector<long long> fact(2 * maxN + 1), invfact(2 * maxN + 1);
    fact[0] = 1;
    for (int i = 1; i <= 2 * maxN; ++i) fact[i] = fact[i - 1] * i % MOD;

    invfact[2 * maxN] = mod_pow(fact[2 * maxN], MOD - 2);
    for (int i = 2 * maxN; i >= 1; --i) invfact[i - 1] = invfact[i] * i % MOD;

    auto C = [&](int n, int r) -> long long {
        if (r < 0 || r > n) return 0;
        return fact[n] * invfact[r] % MOD * invfact[n - r] % MOD;
    };

    // Catalan: Cat[n] = (2n)! / (n! (n+1)!)
    vector<long long> cat(maxN + 1);
    for (int n = 0; n <= maxN; ++n) {
        cat[n] = fact[2 * n] * invfact[n] % MOD * invfact[n + 1] % MOD;
    }

    vector<long long> pow4(maxN + 1, 1);
    for (int i = 1; i <= maxN; ++i) pow4[i] = pow4[i - 1] * 4 % MOD;

    const long long INV2 = (MOD + 1) / 2;

    auto coeff_x = [&](int n, int m) -> long long {
        // [z^n] (z/(1-4z))^m = 4^(n-m) * C(n-1, m-1)
        if (m < 1 || m > n) return 0;
        return pow4[n - m] * C(n - 1, m - 1) % MOD;
    };

    auto coeff_special = [&](int n, int k) -> long long {
        // [z^n] x^k (1-q), only used for even k
        // = 1/2 * ( (2n)! (k-1)! / (n! (2k-2)! (n-k+1)!)
        //         - 4^(n-k+1) * C(n-1, k-2) )
        long long first = fact[2 * n];
        first = first * fact[k - 1] % MOD;
        first = first * invfact[n] % MOD;
        first = first * invfact[2 * k - 2] % MOD;
        first = first * invfact[n - k + 1] % MOD;

        long long second = pow4[n - k + 1] * C(n - 1, k - 2) % MOD;

        long long res = (first - second) % MOD;
        if (res < 0) res += MOD;
        res = res * INV2 % MOD;
        return res;
    };

    for (auto [n, k] : qs) {
        if (k == 0) {
            cout << cat[n] << '\n';
            continue;
        }

        long long ck = cat[k - 1];
        long long sum = 0;

        int start = (k & 1) ? 1 : 2;
        int lim = min(k, n - k + 1);

        for (int j = start; j <= lim; j += 2) {
            int m = k + j - 1;
            long long add = cat[j - 1] * coeff_x(n, m) % MOD;
            sum += add;
            if (sum >= MOD) sum -= MOD;
        }

        long long ans = 2LL * ck % MOD * sum % MOD;

        // j = k was counted with coefficient 2, but must be 1
        if (2 * k - 1 <= n) {
            long long sq = ck * ck % MOD * coeff_x(n, 2 * k - 1) % MOD;
            ans -= sq;
            if (ans < 0) ans += MOD;
        }

        if ((k & 1) == 0) {
            long long sp = coeff_special(n, k);
            ans += 2LL * ck % MOD * sp % MOD;
            if (ans >= MOD) ans -= MOD;
        }

        cout << ans % MOD << '\n';
    }

    return 0;
}

Сложность

Предобработка: O(maxN)
Один запрос: O(min(k, n-k+1))
Суммарно по всем тестам: O(sum n) ≤ O(10^6)

Если хочешь, я могу ещё отдельно расписать короткое “редакционное” доказательство формулы для F_k(z) без пропусков.

ограничение по времени на тест 2 секунды ограничен...

Question

Thought

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Python

Thought

Answer

Идея

Как выглядит исходная операция в новых метках

Генерирующие функции

Нужные коэффициенты

Код C++

Сложность

Share this Q&A