$n$ balls stand a row. You can select exactly $m$ groups of them, each consisting either a single ball or two neighbouring balls. Each ball can only be in one group.

for all $m$ in $[1,k]$ you need to output the number of such divisions.


let $f(n,m)$ to be the answer of selecting $m$ groups in $n$ balls.



We have

It can be proved that there exist a $Z$ that for all $n$

Then we have


As is obviously that

So we can solve $C_1, C_2$

Then $F_n$ shoud be


So there is no need to calculate $Z_2$

And this can be solved in $O(k \log k)$


include1 include2

int main() {
 using namespace Polys;
 int _n = sc.n();
 int _k = sc.n();
 int k = std::max(3, _k+1);
 Poly Delta(k);
 Delta[0] = 1;
 Delta[1] = 6;
 Delta[2] = 1;
 Delta = Delta.sqrt();
 Poly Z = Delta;
 Z[0] += Int(1);
 Z[1] += Int(1);
 Z *= Int(1) / Int(2);
 int n = (_n+1) % MOD;
 Z = Z.pow(n,n);
 Z *= Delta.inv();
 for (int i = 1; i <= _k; ++ i) {
   printf("%u ", i <= _n ? static_cast<unsigned>(Z[i]) : 0);
 return 0;

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.