loj3291

题意

loj

做法

(F_{n+m}=F_{n}*F_{m}+F_{n-1}*F_{m-1})
(F_{n}*F_{m}=F_{n+m}-(F_{n-1}*F_{m-1}))
(F_n*_m=F_{n+m}-F_{n+m-2}+F_{n+m-4}…+(-1)^{min(n,m)}*F_{|n-m|})

分别算出(F_{n+m})与((-1)^{min(n,m)-2}*F_{|n-m|-2})，可以差分算出中间的
(A,B)分别用多项式(A(x),B(x))表示，通过多项式加速整体求和的过程

最后得到的多项式有正有负，负数取绝对值，分别做表示成最简表示，然后做减法

现在问题转化成，若得到(sum a_i*F_{i})，如何转化到最简的表示
分治一下：(sum a_i*F_{i}=sum (a_i\%2)F_i+2(sum (leftlfloorfrac{a_i}{2} ight floor) F_i))
相加就暴力做好了