Եթե վերաձևակերպեմ լուծումը, F(i)-ով կարելի ա նշանակել ծնվածների թիվը i-րդ տարում: Վերջնական պատասխանը կլինի 1-ից 35 տարի առաջ ծնվածների գումարը: Իսկ i-րդ տարում ծնվածների գումարը կլինի 15-34 տարի առաջ ծնվածների գումարը` մոտավորապես.
F(i) = F(i - 34) + F(i - 33) + ... + F(i - 15)
Հիմա եթե ունենք առաջին 35 տարիների հաշվարկը (F(1)-ից F(35)), դրանից կարող ենք F(2)-ից F(36)-ը ստանալ {F(1);F(2);...;F(35)} վեկտորը մատրիցով բազմապատկելով.
կամ ինչ-որ սենց բանԿոդ:0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 . . . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
Դե էս մատրիցն էլ O(logN)-ում կարանք N աստիճան բարձրացնենք:





Մեջբերել
Էջանիշներ