Даалуу

Бодолт

Эхлээд хамгийн эхний нөхцөлийг хасаад бодож үзье. Өөрөөр хэлбэл хөлөг дээр ганц ч даалуу байхгүй байх үеийг хариу мөн гэж тооцоод хөлөг $1\times i$ хэмжээтэй байх үеийн хариуг $a[i]$ хувьсагчид хадгалъя.

Тэгвэл $a[0],a[1],...,a[i]$-уудыг олсон гэж үзээд $1\times (i+1)$ үеийн хариуг ольё. Энэ нь $i+1$ нүдэн дээр даалуу тавьсан болон тавиагүй гэж $2$ нөхцөл сална. $i+1$ нүдэн дээр даалуу тавиагүй үед $1\times i$ үетэй адилхан тул $a[i]$ янзын боломжтой.$i+1$ нүдэн дээр даалуу тавьсан үед $3$ дахь дүрмийн дагуу $i$ дахь нүдэнд даалуу тавьж болохгүй тул эхний $1\times (i - 1)$ нүдэн дээр даалуу тавих боломж болон $i + 1$ дэх нүдэнд даалуу тавих боломжийн тоонуудын үржвэр буюу $a[i - 1] * (i + 1)$ болно. Эндээс $a[i + 1] = a[i] + (i + 1) * a[i - 1]$ гэсэн томъё гарна. Энэ хариу нь үндсэн бодлого дээр хөлөг хоосон байх гэсэн нэг тохиолдлыг нэмсэн гэдгийг санавал үндсэн бодлогын хариу $a[N] - 1$ болно.

Дээр гаргасан томьёог харвал бид дурын $2\le N$-ийн хувьд өмнөх 2 үеийг нь мэдэж байвал бодлогын хариуг олж болох тул $a[0]$ болон $a[1]$ гэсэн бага утгуудыг бодож олоод үлдсэн утгуудыг давталт ашиглан хялбархан олж болно. Гэвч $N=31$ үед $a[31]$ нь хэт том тоо болох тул C болон C++ хэлний ямар ч төрлийн хувьсагчид(1-р олимпиадын бага ангийн илэрхийлэл бодлогын анализыг харна уу) утгыг хадгалах боломжгүй тул тоог цифр цифрээр салган хүснэгтэд хадгалан тэдгээр дээрээ үржих болон нэмэх үйлдлийг гүйцэтгэх шаардлагатай үүнийг өөрөө хийж сураасай гэж хүсэж байгаа учраас бичилгүй орхиё.

Код