QOJ.ac

QOJ

Time Limit: 0.25 s Memory Limit: 256 MB Total points: 100
[0]

# 10141. AA Tree

Statistics

An AA tree is a binary search tree with a special structure. Every node has a value and a level. Values obey the usual binary search tree properties:

  1. The value of every left child (and every node in the subtree of the left child) is less than or equal to the value of its parent.
  2. The value of every right child (and every node in the subtree of the right child) is greater than or equal to the value of its parent.

Levels obey the following rules:

  1. The level of every leaf node is 1.
  2. The level of every left child is exactly one less than that of its parent.
  3. The level of every right child is equal to or one less than that of its parent.
  4. The level of every right grandchild is strictly less than that of its grandparent.
  5. Every node of level greater than one has two children.

Below are five examples of AA trees, having 3, 5, 5, 11 and 11 nodes respectively. For clarity, right children on an equal level with their parent are shown in red.

problem_10141_1.png

Task

Given two numbers N and L, how many ways are there of arranging the values 1, 2, ..., N in an AA tree such that it has exactly L levels?

Input data

The only line of input will contain the integers N and L separated by a space.

Output data

Output the number of arrangements modulo 109+7.

Constraints and clarifications

  • The problem statement is slightly modified due to an error in the definition of what a binary search tree is in the original statement.
  • 1≤L≤9
  • 1≤N≤10 000
# Points Constraints
0 0 Examples
1 19 L≤4
2 34 5≤L≤7
3 47 No additional constraints

Example 1

stdin

5 2

stdout

2

Explanation

The two possible arrangements are shown in images 2 and 3 above.

Example 2

stdin

442 6

stdout

896944318

Example 3

stdin

7133 9

stdout

980381648

Un arbore AA este un arbore binar de căutare cu o structură specială. Fiecărui nod îi sunt atribuite o valoare și un nivel. Valorile îndeplinesc proprietățile obișnuite ale arborilor binari de căutare:

  1. Valoarea fiecărui fiu stâng (și a nodurilor din subarborele fiului stâng) este mai mică sau egală ca cea a tatălui său.
  2. Valoarea fiecărui fiu drept (și a nodurilor din subarborele fiului drept) este mai mare sau egală cu valoarea tatălui său.

Nivelele respectă următoarele reguli:

  1. Nivelul fiecărui nod frunză este 1.
  2. Nivelul fiecărui fiu stâng este exact cu unu mai mic decât cel al tatălui său.
  3. Nivelul fiecărui fiu drept este egal sau cu unu mai mic decât cel al tatălui său.
  4. Nivelul fiecărui nepot drept este strict mai mic decât cel al bunicului său.
  5. Fiecare nod de nivel mai mare strict ca unu are exact doi fii.

Mai jos găsiți cinci exemple de arbori AA, având 3, 5, 5, 11 și 11 noduri. Pentru claritate, fiii drepți pe același nivel cu tații lor sunt colorați cu roșu.

problem_10141_1.png

Cerință

Date fiind două numere N și L, câte moduri sunt de a aranja valorile 1, 2, ..., N într-un arbore AA astfel încât acesta are fix L nivele?

Date de intrare

Singura linie a datelor de intrare va conține numerele întregi N și L separate printr-un spațiu.

Date de ieșire

Afișați numărul de aranjări modulo 109+7.

Restricții și precizări

  • Enunțul problemei este puțin modificat din cauza unei erori în definiția arborilor binari de căutare în enunțul original al problemei.
  • 1≤L≤9
  • 1≤N≤10 000
# Punctaj Restricții
0 0 Exemplele
1 19 L≤4
2 34 5≤L≤7
3 47 Fără restricții suplimentare

Exemplul 1

stdin

5 2

stdout

2

Explicație

Cele două posibile aranjări sunt arătate în imaginile 2 și 3 de mai sus.

Exemplul 2

stdin

442 6

stdout

896944318

Exemplul 3

stdin

7133 9

stdout

980381648
English 繁體中文 简体中文

Server Time: 2025-03-26 22:48:17 | OpenSource Project