Welcome to my fiendish little bomb.
You have 6 phases with which to blow yourself up. Have a nice day!

bomblab分6个phase，每个phase有一个函数，没有函数的源代码，只能通过阅读函数的汇编代码得出恰当的输入。一次错误的输入会引爆炸弹。不过只要在explode_bomb打一个断点就可以了。

gdb调试汇编命令：
- disassemble 反汇编函数func，输出函数汇编代码。简称disas
- b 在函数func处打断点
- b *+ 在函数func汇编代码中+num处打断点
- cl 清除函数func的所有断点
- ni/si 在汇编代码中逐步执行
- p $ 打印寄存器reg当前的值 e.g.:p $rax
- x/<n/f/u> 输出地址addr后的信息，
n：一个数字，表示输出数量
f：输出格式（s：字符串，x：十六进制，d：十进制...）
u：输出每个数所占位数（b：单字节，h：双字节，w：四字节，g：八字节），默认四字节
addr：一个内存地址
e.g. x/8xg $rsp+0x20

特殊寄存器:
rsp：stack ptr，指向系统栈中当前函数栈底位置
rax：函数返回值寄存器
rdi：传入第一个参数
rsi：传入第二个参数
rdx：传入第三个参数
rcx：传入第四个参数

phase_1

   0x0000000000400ee0 <+0>: sub    $0x8,%rsp
   0x0000000000400ee4 <+4>: mov    $0x402400,%esi
   0x0000000000400ee9 <+9>: callq  0x401338 <strings_not_equal>
   0x0000000000400eee <+14>:    test   %eax,%eax
   0x0000000000400ef0 <+16>:    je     0x400ef7 <phase_1+23>
   0x0000000000400ef2 <+18>:    callq  0x40143a <explode_bomb>
   0x0000000000400ef7 <+23>:    add    $0x8,%rsp
   0x0000000000400efb <+27>:    retq 

<+4>行给esi赋了一个蜜汁内存地址0x402400，然后调用string_not_equal
x/s $0x402400 得到"Border relations with Canada have never been better."
就是答案了。

phase_2

   0x0000000000400efc <+0>:   push   %rbp
   0x0000000000400efd <+1>:   push   %rbx
   0x0000000000400efe <+2>:   sub    $0x28,%rsp
   0x0000000000400f02 <+6>:   mov    %rsp,%rsi
   0x0000000000400f05 <+9>:   callq  0x40145c <read_six_numbers>
   0x0000000000400f0a <+14>:  cmpl   $0x1,(%rsp)
   0x0000000000400f0e <+18>:  je     0x400f30 <phase_2+52>
   0x0000000000400f10 <+20>:  callq  0x40143a <explode_bomb>
   0x0000000000400f15 <+25>:  jmp    0x400f30 <phase_2+52>
   0x0000000000400f17 <+27>:  mov    -0x4(%rbx),%eax
   0x0000000000400f1a <+30>:  add    %eax,%eax
   0x0000000000400f1c <+32>:  cmp    %eax,(%rbx)
   0x0000000000400f1e <+34>:  je     0x400f25 <phase_2+41>
   0x0000000000400f20 <+36>:  callq  0x40143a <explode_bomb>
   0x0000000000400f25 <+41>:  add    $0x4,%rbx
   0x0000000000400f29 <+45>:  cmp    %rbp,%rbx
   0x0000000000400f2c <+48>:  jne    0x400f17 <phase_2+27>
   0x0000000000400f2e <+50>:  jmp    0x400f3c <phase_2+64>
   0x0000000000400f30 <+52>:  lea    0x4(%rsp),%rbx
   0x0000000000400f35 <+57>:  lea    0x18(%rsp),%rbp
   0x0000000000400f3a <+62>:  jmp    0x400f17 <phase_2+27>
   0x0000000000400f3c <+64>:  add    $0x28,%rsp
   0x0000000000400f40 <+68>:  pop    %rbx
   0x0000000000400f41 <+69>:  pop    %rbp
   0x0000000000400f42 <+70>:  retq   

<+9>调用read_six_numbers
<+18>要求第一个数必须为1
然后是一个循环，要求后一个数是前一个数的二倍
因此答案为 1 2 4 8 16 32

phase_3

   0x0000000000400f43 <+0>:   sub    $0x18,%rsp
   0x0000000000400f47 <+4>:   lea    0xc(%rsp),%rcx
   0x0000000000400f4c <+9>:   lea    0x8(%rsp),%rdx
   0x0000000000400f51 <+14>:  mov    $0x4025cf,%esi
   0x0000000000400f56 <+19>:  mov    $0x0,%eax
   0x0000000000400f5b <+24>:  callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000400f60 <+29>:  cmp    $0x1,%eax
   0x0000000000400f63 <+32>:  jg     0x400f6a <phase_3+39>
   0x0000000000400f65 <+34>:  callq  0x40143a <explode_bomb>
   0x0000000000400f6a <+39>:  cmpl   $0x7,0x8(%rsp)
   0x0000000000400f6f <+44>:  ja     0x400fad <phase_3+106>
   0x0000000000400f71 <+46>:  mov    0x8(%rsp),%eax
   0x0000000000400f75 <+50>:  jmpq   *0x402470(,%rax,8)
   0x0000000000400f7c <+57>:  mov    $0xcf,%eax
   0x0000000000400f81 <+62>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f83 <+64>:  mov    $0x2c3,%eax
   0x0000000000400f88 <+69>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f8a <+71>:  mov    $0x100,%eax
   0x0000000000400f8f <+76>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f91 <+78>:  mov    $0x185,%eax
   0x0000000000400f96 <+83>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f98 <+85>:  mov    $0xce,%eax
   0x0000000000400f9d <+90>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400f9f <+92>:  mov    $0x2aa,%eax
   0x0000000000400fa4 <+97>:  jmp    0x400fbe <phase_3+123>
   0x0000000000400fa6 <+99>:  mov    $0x147,%eax
   0x0000000000400fab <+104>: jmp    0x400fbe <phase_3+123>
   0x0000000000400fad <+106>: callq  0x40143a <explode_bomb>
   0x0000000000400fb2 <+111>: mov    $0x0,%eax
   0x0000000000400fb7 <+116>: jmp    0x400fbe <phase_3+123>
   0x0000000000400fb9 <+118>: mov    $0x137,%eax
   0x0000000000400fbe <+123>: cmp    0xc(%rsp),%eax
   0x0000000000400fc2 <+127>: je     0x400fc9 <phase_3+134>
   0x0000000000400fc4 <+129>: callq  0x40143a <explode_bomb>
   0x0000000000400fc9 <+134>: add    $0x18,%rsp
   0x0000000000400fcd <+138>: retq  

<+14>蜜汁内存地址0x4025cf
x/s 0x4025cf得到 "%d %d"
sscanf第二个参数，即输入格式为2个整数
eax为成功赋值参数个数
<+32>强制eax>1，即传入两个参数
可以发现传入的第一个参数地址为$rsp+0x8，第二个参数地址为$rsp+0xc
<+44>要求第一个参数小于等于7
<+50>跳转*(0x402470+8rax)，此时rax为第一个参数的值
看一下内存0x402470后的值

(gdb) x/8xg 0x402470
0x402470:   0x0000000000400f7c  0x0000000000400fb9
0x402480:   0x0000000000400f83  0x0000000000400f8a
0x402490:   0x0000000000400f91  0x0000000000400f98
0x4024a0:   0x0000000000400f9f  0x0000000000400fa6

即对于每个rax，会跳转到一个位置，以第一个参数为7为例：
会跳转到0x400fa6，然后比较第二个参数与0x147是否相等
因此7 327 (0x147=327)为一组解，理论上应该有八组解

phase_4

   0x000000000040100c <+0>: sub    $0x18,%rsp
   0x0000000000401010 <+4>: lea    0xc(%rsp),%rcx
   0x0000000000401015 <+9>: lea    0x8(%rsp),%rdx
   0x000000000040101a <+14>:    mov    $0x4025cf,%esi
   0x000000000040101f <+19>:    mov    $0x0,%eax
   0x0000000000401024 <+24>:    callq  0x400bf0 <__isoc99_sscanf@plt>
   0x0000000000401029 <+29>:    cmp    $0x2,%eax
   0x000000000040102c <+32>:    jne    0x401035 <phase_4+41>
   0x000000000040102e <+34>:    cmpl   $0xe,0x8(%rsp)
   0x0000000000401033 <+39>:    jbe    0x40103a <phase_4+46>
   0x0000000000401035 <+41>:    callq  0x40143a <explode_bomb>
   0x000000000040103a <+46>:    mov    $0xe,%edx
   0x000000000040103f <+51>:    mov    $0x0,%esi
   0x0000000000401044 <+56>:    mov    0x8(%rsp),%edi
   0x0000000000401048 <+60>:    callq  0x400fce <func4>
   0x000000000040104d <+65>:    test   %eax,%eax
   0x000000000040104f <+67>:    jne    0x401058 <phase_4+76>
   0x0000000000401051 <+69>:    cmpl   $0x0,0xc(%rsp)
   0x0000000000401056 <+74>:    je     0x40105d <phase_4+81>
   0x0000000000401058 <+76>:    callq  0x40143a <explode_bomb>
   0x000000000040105d <+81>:    add    $0x18,%rsp
   0x0000000000401061 <+85>:    retq  

同理可以发现仍然需要两个输入数
<+34>说明第一个参数小于0xe
<+69>要求第二个参数为0（所以要他何用）
<+60>调用函数func4，传入三个参数，分别为0xe,0x0,phase_4的第一个参数
<+67>要求func4返回值为0
然后看一下func4长什么样：
其实把第一个参数从0试到0xe也行

   0x0000000000400fce <+0>: sub    $0x8,%rsp
   0x0000000000400fd2 <+4>: mov    %edx,%eax
   0x0000000000400fd4 <+6>: sub    %esi,%eax
   0x0000000000400fd6 <+8>: mov    %eax,%ecx
   0x0000000000400fd8 <+10>:    shr    $0x1f,%ecx
   0x0000000000400fdb <+13>:    add    %ecx,%eax
   0x0000000000400fdd <+15>:    sar    %eax
   0x0000000000400fdf <+17>:    lea    (%rax,%rsi,1),%ecx
   0x0000000000400fe2 <+20>:    cmp    %edi,%ecx
   0x0000000000400fe4 <+22>:    jle    0x400ff2 <func4+36>
   0x0000000000400fe6 <+24>:    lea    -0x1(%rcx),%edx
   0x0000000000400fe9 <+27>:    callq  0x400fce <func4>
   0x0000000000400fee <+32>:    add    %eax,%eax
   0x0000000000400ff0 <+34>:    jmp    0x401007 <func4+57>
   0x0000000000400ff2 <+36>:    mov    $0x0,%eax
   0x0000000000400ff7 <+41>:    cmp    %edi,%ecx
   0x0000000000400ff9 <+43>:    jge    0x401007 <func4+57>
   0x0000000000400ffb <+45>:    lea    0x1(%rcx),%esi
   0x0000000000400ffe <+48>:    callq  0x400fce <func4>
   0x0000000000401003 <+53>:    lea    0x1(%rax,%rax,1),%eax
   0x0000000000401007 <+57>:    add    $0x8,%rsp
   0x000000000040100b <+61>:    retq   

看起来是一个奇怪的递归函数，不过不要慌，我们只需要让这个函数返回0就行了
然后可以发现，只要rdi=7就可以跳过那坨递归直接返回一个0。。。
所以 7 0 就行了。
其实答案不止7一个

phase_5

=> 0x0000000000401062 <+0>:   push   %rbx
   0x0000000000401063 <+1>:   sub    $0x20,%rsp
   0x0000000000401067 <+5>:   mov    %rdi,%rbx
   0x000000000040106a <+8>:   mov    %fs:0x28,%rax
   0x0000000000401073 <+17>:  mov    %rax,0x18(%rsp)
   0x0000000000401078 <+22>:  xor    %eax,%eax
   0x000000000040107a <+24>:  callq  0x40131b <string_length>
   0x000000000040107f <+29>:  cmp    $0x6,%eax
   0x0000000000401082 <+32>:  je     0x4010d2 <phase_5+112>
   0x0000000000401084 <+34>:  callq  0x40143a <explode_bomb>
   0x0000000000401089 <+39>:  jmp    0x4010d2 <phase_5+112>
   0x000000000040108b <+41>:  movzbl (%rbx,%rax,1),%ecx
   0x000000000040108f <+45>:  mov    %cl,(%rsp)
   0x0000000000401092 <+48>:  mov    (%rsp),%rdx
   0x0000000000401096 <+52>:  and    $0xf,%edx
   0x0000000000401099 <+55>:  movzbl 0x4024b0(%rdx),%edx
   0x00000000004010a0 <+62>:  mov    %dl,0x10(%rsp,%rax,1)
   0x00000000004010a4 <+66>:  add    $0x1,%rax
   0x00000000004010a8 <+70>:  cmp    $0x6,%rax
   0x00000000004010ac <+74>:  jne    0x40108b <phase_5+41>
   0x00000000004010ae <+76>:  movb   $0x0,0x16(%rsp)
   0x00000000004010b3 <+81>:  mov    $0x40245e,%esi
   0x00000000004010b8 <+86>:  lea    0x10(%rsp),%rdi
   0x00000000004010bd <+91>:  callq  0x401338 <strings_not_equal>
   0x00000000004010c2 <+96>:  test   %eax,%eax
   0x00000000004010c4 <+98>:  je     0x4010d9 <phase_5+119>
   0x00000000004010c6 <+100>: callq  0x40143a <explode_bomb>
   0x00000000004010cb <+105>: nopl   0x0(%rax,%rax,1)
   0x00000000004010d0 <+110>: jmp    0x4010d9 <phase_5+119>
   0x00000000004010d2 <+112>: mov    $0x0,%eax
   0x00000000004010d7 <+117>: jmp    0x40108b <phase_5+41>
   0x00000000004010d9 <+119>: mov    0x18(%rsp),%rax
   0x00000000004010de <+124>: xor    %fs:0x28,%rax
   0x00000000004010e7 <+133>: je     0x4010ee <phase_5+140>
   0x00000000004010e9 <+135>: callq  0x400b30 <__stack_chk_fail@plt>
   0x00000000004010ee <+140>: add    $0x20,%rsp
   0x00000000004010f2 <+144>: pop    %rbx
   0x00000000004010f3 <+145>: retq  

<+32> 说明输入是一个长度为6的字符串。
然后进入一个循环<+41>~<+74>
枚举输入的字符，取其&$0xf后的数edx，然后把edx+0x4024b的值赋到$rsp+0x10+i（i为1到6的循环变量）
看一下0x4024b有啥

(gdb) x/s 0x4024b0
0x4024b0 <array.3449>:  "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"

其实只有前面一段"maduiersnfotvbyl"有用
然后<+76>~<+98>
比较字符串$rsp+0x10和0x40245e是否相等

(gdb) x/s 0x40245e
0x40245e:   "flyers"

也就是说我们需要通过凑出一个"flyers"
输入字符串每一个字符ascii的后四个bit对应"maduiersnfotvbyl"的下标，凑出一个"flyers"
一个可行解是"9?>567"

phase_6

这个phase跟前面画风不太一样啊。。。

   0x00000000004010f4 <+0>:   push   %r14
   0x00000000004010f6 <+2>:   push   %r13
   0x00000000004010f8 <+4>:   push   %r12
   0x00000000004010fa <+6>:   push   %rbp
   0x00000000004010fb <+7>:   push   %rbx
   0x00000000004010fc <+8>:   sub    $0x50,%rsp
   0x0000000000401100 <+12>:  mov    %rsp,%r13
   0x0000000000401103 <+15>:  mov    %rsp,%rsi
   0x0000000000401106 <+18>:  callq  0x40145c <read_six_numbers>
   0x000000000040110b <+23>:  mov    %rsp,%r14
   0x000000000040110e <+26>:  mov    $0x0,%r12d
   0x0000000000401114 <+32>:  mov    %r13,%rbp
   0x0000000000401117 <+35>:  mov    0x0(%r13),%eax
   0x000000000040111b <+39>:  sub    $0x1,%eax
   0x000000000040111e <+42>:  cmp    $0x5,%eax
   0x0000000000401121 <+45>:  jbe    0x401128 <phase_6+52>
   0x0000000000401123 <+47>:  callq  0x40143a <explode_bomb>
   0x0000000000401128 <+52>:  add    $0x1,%r12d
   0x000000000040112c <+56>:  cmp    $0x6,%r12d
   0x0000000000401130 <+60>:  je     0x401153 <phase_6+95>
   0x0000000000401132 <+62>:  mov    %r12d,%ebx
   0x0000000000401135 <+65>:  movslq %ebx,%rax
   0x0000000000401138 <+68>:  mov    (%rsp,%rax,4),%eax
   0x000000000040113b <+71>:  cmp    %eax,0x0(%rbp)
   0x000000000040113e <+74>:  jne    0x401145 <phase_6+81>
   0x0000000000401140 <+76>:  callq  0x40143a <explode_bomb>
   0x0000000000401145 <+81>:  add    $0x1,%ebx
   0x0000000000401148 <+84>:  cmp    $0x5,%ebx
   0x000000000040114b <+87>:  jle    0x401135 <phase_6+65>
   0x000000000040114d <+89>:  add    $0x4,%r13
   0x0000000000401151 <+93>:  jmp    0x401114 <phase_6+32>
   0x0000000000401153 <+95>:  lea    0x18(%rsp),%rsi
   0x0000000000401158 <+100>: mov    %r14,%rax
   0x000000000040115b <+103>: mov    $0x7,%ecx
   0x0000000000401160 <+108>: mov    %ecx,%edx
   0x0000000000401162 <+110>: sub    (%rax),%edx
   0x0000000000401164 <+112>: mov    %edx,(%rax)
   0x0000000000401166 <+114>: add    $0x4,%rax
   0x000000000040116a <+118>: cmp    %rsi,%rax
   0x000000000040116d <+121>: jne    0x401160 <phase_6+108>
   0x000000000040116f <+123>: mov    $0x0,%esi
   0x0000000000401174 <+128>: jmp    0x401197 <phase_6+163>
   0x0000000000401176 <+130>: mov    0x8(%rdx),%rdx
   0x000000000040117a <+134>: add    $0x1,%eax
   0x000000000040117d <+137>: cmp    %ecx,%eax
   0x000000000040117f <+139>: jne    0x401176 <phase_6+130>
   0x0000000000401181 <+141>: jmp    0x401188 <phase_6+148>
   0x0000000000401183 <+143>: mov    $0x6032d0,%edx
   0x0000000000401188 <+148>: mov    %rdx,0x20(%rsp,%rsi,2)
   0x000000000040118d <+153>: add    $0x4,%rsi
   0x0000000000401191 <+157>: cmp    $0x18,%rsi
   0x0000000000401195 <+161>: je     0x4011ab <phase_6+183>
   0x0000000000401197 <+163>: mov    (%rsp,%rsi,1),%ecx
   0x000000000040119a <+166>: cmp    $0x1,%ecx
   0x000000000040119d <+169>: jle    0x401183 <phase_6+143>
   0x000000000040119f <+171>: mov    $0x1,%eax
   0x00000000004011a4 <+176>: mov    $0x6032d0,%edx
   0x00000000004011a9 <+181>: jmp    0x401176 <phase_6+130>
   0x00000000004011ab <+183>: mov    0x20(%rsp),%rbx
   0x00000000004011b0 <+188>: lea    0x28(%rsp),%rax
   0x00000000004011b5 <+193>: lea    0x50(%rsp),%rsi
   0x00000000004011ba <+198>: mov    %rbx,%rcx
   0x00000000004011bd <+201>: mov    (%rax),%rdx
   0x00000000004011c0 <+204>: mov    %rdx,0x8(%rcx)
   0x00000000004011c4 <+208>: add    $0x8,%rax
   0x00000000004011c8 <+212>: cmp    %rsi,%rax
   0x00000000004011cb <+215>: je     0x4011d2 <phase_6+222>
   0x00000000004011cd <+217>: mov    %rdx,%rcx
   0x00000000004011d0 <+220>: jmp    0x4011bd <phase_6+201>
   0x00000000004011d2 <+222>: movq   $0x0,0x8(%rdx)
   0x00000000004011da <+230>: mov    $0x5,%ebp
   0x00000000004011df <+235>: mov    0x8(%rbx),%rax
   0x00000000004011e3 <+239>: mov    (%rax),%eax
   0x00000000004011e5 <+241>: cmp    %eax,(%rbx)
   0x00000000004011e7 <+243>: jge    0x4011ee <phase_6+250>
   0x00000000004011e9 <+245>: callq  0x40143a <explode_bomb>
   0x00000000004011ee <+250>: mov    0x8(%rbx),%rbx
   0x00000000004011f2 <+254>: sub    $0x1,%ebp
   0x00000000004011f5 <+257>: jne    0x4011df <phase_6+235>
   0x00000000004011f7 <+259>: add    $0x50,%rsp
   0x00000000004011fb <+263>: pop    %rbx
   0x00000000004011fc <+264>: pop    %rbp
   0x00000000004011fd <+265>: pop    %r12
   0x00000000004011ff <+267>: pop    %r13
   0x0000000000401201 <+269>: pop    %r14
   0x0000000000401203 <+271>: retq  

一个巨长的汇编代码，各种跳转。。。
不过努力分析一波可以发现这其实是一坨循环组成的
可以发现输入是6个数
<+32>~<+95>判断输入是不是一个1到6的排列

<+108>~<+121>把排列的所有数变成7-x（强行增加难度）

<+128>~<+183>这段比较蛋疼，用力看一下，里面有一个蜜汁内存地址0x6032d0
里面是长这样的：

(gdb) x/12xg 0x6032d0
0x6032d0 <node1>:   0x000000010000014c  0x00000000006032e0
0x6032e0 <node2>:   0x00000002000000a8  0x00000000006032f0
0x6032f0 <node3>:   0x000000030000039c  0x0000000000603300
0x603300 <node4>:   0x00000004000002b3  0x0000000000603310
0x603310 <node5>:   0x00000005000001dd  0x0000000000603320
0x603320 <node6>:   0x00000006000001bb  0x0000000000000000

然后这段代码相当于把排列做了一个映射

1->0x00000000006032e0
2->0x00000000006032f0
3->0x0000000000603300
4->0x0000000000603310
5->0x0000000000603320
6->0x0000000000000000

然后接到原排列后面

<+201>~<+222>
其实最后两段是最蛋疼的
这一段相当于搞了一个类似链表的东西
把内存0x6032d0到0x6032e0这段做了一个轮换
（这段可以分成6组，每组由两个8位的数构成，一组中的第一个存一个数值，第二个存一个地址，对其中第二个做一个轮换）

<+235>~<+257>
这段是按上面那个链表的顺序访问访问每组，要求每组的第一个元素后四位递减顺序出现

0x000000010000014c->14c 
0x00000002000000a8->0a8 
0x000000030000039c->39c 
0x00000004000002b3->2b3 
0x00000005000001dd->1dd 
0x00000006000001bb->1bb 

然后就可以确定这个初始的排列了。。。

好像还有个隐藏关卡？
以后再说吧
强行完结撒花

好像几百年没更博了。。。

最近在学cmu的csapp，没有学号不能在cmu上交
不过可以下官方的自学lab

datalab断断续续搞了两三天QAQ
就不贴官方要求了

1.bitAnd

用 ~,| 实现按位与

int bitAnd(int x, int y) {
    return ~((~x)|(~y));
}

2.getByte

获得第n个byte

int getByte(int x, int n) {
    return (x>>(n<<3))&0xff;
}

3.logicalShift

逻辑右移n位
把最高的n-1位置0

int logicalShift(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    return (x>>n)&v2;
}

4.bitCount

计算所有位中1的个数，限制40个ops
开始确实没想到可以用类似分治一次搞多位。
就是每次把连续$$2^k$$个bit的和计算出来放在原来的位置
这个东西可以所有位一起搞

int bitCount(int x) {

    int t0 = 0x55|(0x55<<8);
    int v0 = t0|(t0<<16);
    int x0 = (x&v0)+((x>>1)&v0);

    int t1 = 0x33|(0x33<<8);
    int v1 = t1|(t1<<16);
    int x1 = (x0&v1)+((x0>>2)&v1);

    int t2 = 0xf|(0xf<<8);
    int v2 = t2|(t2<<16);
    int x2 = (x1&v2)+((x1>>4)&v2);

    int v3 = 0xff|(0xff<<16);
    int x3 = (x2&v3)+((x2>>8)&v3);

    int v4 = 0xff|(0xff<<8);
    int x4 = (x3&v4)+((x3>>16)&v4);

    return x4;
}

5.bang

不用!实现！
把所有位或到第一位就好了，每次折半

int bang(int x) {
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return (~x)&1;
}

6.tmin

最小的two's complement number -2147483648

int tmin(void) {
    return 1 << 31;
}

7.fitsBits

数x是否可以被表示成n个bit的数
就是判断最高32-n+1位是否相同
因为要实现logicalshift写的极丑，还特判了n=32

int fitsBits(int x, int n) {
    int v1 = 1<<31;
    int v2 = ~((v1>>n)<<1);
    x ^= x >> 31;
    return (n>>5&1)|(!((x << 1 >> n)&v2));
}

8.divpwr2

$$x/2^k$$向0取整
负数的话判断一下前n位有没有东西，如果有就+1

int divpwr2(int x, int n) {
    int v1 = x>>31&1;
    int v2 = !!((x>>n<<n)^x);
    return (x>>n)+(v1&v2);
}

9.negate

返回-x

int negate(int x) {
    return ~x + 1;
}

10.isPositive

返回x是否大于0
判0或负数

int isPositive(int x) {
    return !((!(x&~(1<<31)))|(x>>31));
}

11.isLessOrEqual

比较x是否小于等于y
首先比较符号是否相同
符号不同返回x为负
符号相同返回y-x非负

int isLessOrEqual(int x, int y) {
    int v2 = (x>>31)&1;
    int v1 = v2^((y>>31)&1);
    int v3 = y+((~x)+1);
    int v4 = !((v3>>31)&1);
    return (v1&v2)|((!v1)&v4);
}

12.ilog2

返回最高位位置（log下取整）
优雅的二分

int ilog2(int x) {
    int ret = 0;
    int t1 = 0;

    t1 = !(x>>16);
    ret = (!t1)<<4;
    x = x>>(16^(t1<<4));

    t1 = !(x>>8);
    ret |= (!t1)<<3;
    x = x>>(8^(t1<<3));

    t1 = !(x>>4);
    ret |= (!t1)<<2;
    x = x>>(4^(t1<<2));

    t1 = !(x>>2);
    ret |= (!t1)<<1;
    x = x>>(2^(t1<<1));

    return ret|(x>>1);
}

13.float_neg

为啥到这函数名就变下划线了啊啊啊啊
传入一个unsigned表示一个float格式的数，返回-x
判一下nan，把符号位反过来

unsigned float_neg(unsigned uf) {
    unsigned v = uf;
    unsigned frac = 0;
    unsigned exp = 0;
    unsigned s = 0;
    unsigned nf = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;
    nf = uf^0x80000000;
    if(exp == 0xff && frac)
        return uf;
    return nf;
}

14.float_i2f

把int转成float
首先特判掉0和-2147483648（雾）
然后记一下符号位，转成正数
然后如果不到23位就补到23位，如果超了的话emmm，round to nearest even了解一下~~~

unsigned float_i2f(int x) {
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned tx = x;
    unsigned num = 0;
    unsigned pre = 0;
    if(!tx) return 0u;
    if(tx == 0x80000000) return 0xcf000000;
    if(tx&0x80000000)
        s = 0x80000000, tx = -tx;
    exp = 150;
    while(tx < 0x800000)
        tx <<= 1,exp--;
    while(tx >= 0x1000000)
    {
        pre = tx & 1;
        num += pre;
        tx >>= 1; exp++;
    }
    if( pre && (num + (tx&1) >= 2))
    {
        tx++;
        if(tx >= 0x1000000)
            tx >>= 1, exp++;
    } 
    frac = tx^0x800000;
    return frac | (exp<<23) | s;
}

15.float_twice

传入一个unsigned表示一个float格式的数，返回2x
判掉nan和inf
再判一下2x会不会到inf
再判一下是不是normalized的
再判一下会不会到normalized

unsigned float_twice(unsigned uf) {
    unsigned v = uf;
    unsigned exp = 0;
    unsigned frac = 0;
    unsigned s = 0;
    unsigned exp1 = 0;
    unsigned frac1 = 0;
    unsigned s1 = 0;

    frac = v&0x7fffff;
    v>>=23;
    exp = v&0xff;
    v>>=8;
    s = v;

    exp1 = exp;
    frac1 = frac;
    s1 = s;

    if(exp == 0xff)
        return uf;

    if(exp == 0xfe)
        exp1 = 0xff, frac1 = 0;
    else if(exp == 0)
    {
        if((frac >> 23) & 1)
        {
            frac1 ^= 1<<23;
            exp1 = 1;
        }
        frac1 <<= 1;
    }
    else exp1++;

    return frac1 | (exp1<<23) | (s1<<31);
}

MinGW使用-lxxx来链接库的时候，搜索库的顺序如下：
libxxx.dll.a
xxx.dll.a
libxxx.a
cygxxx.dll (*)
libxxx.dll
xxx.dll

好久以来一直想去填这个坑，苦于作文水平一直拖到现在。这大概是我写的第一篇回忆OI的文章吧。

或许我已经退役了吧，不然也谈不上回忆。这必定是一篇充斥着感情的文章。因为两年，哦不，到现在已经有三年了，其中所发生的事必定不能轻描淡写的一笔带过。这三年间发生了太多的事，使我无法用轻松的心情去写这篇文章。

从三年前的暑假开始，我和其他一些同学提前一年进入高中学习，分叉在各个班级中。

三年前的寒假，我在学了一个学期数学竞赛后最终决定选择OI。放弃的理由？对OI更感兴趣，仅此而已。

巨大的机房中在前几排坐着十几个人，显得有些空旷。漆黑的走廊，老旧的XP系统，踩上去会发出响声的防静电地板，小屋中嗡嗡作响的交换机。我的OI生涯这样开始了。

正值寒假，白天时如果有时间，我便会到机房中去做语法基础题。有时会有些高一的同学在，应该叫学长吧。他们便会探讨一些我根本不懂的题目。刚开始接触新鲜事物时，一切都是那么令人着迷。我梦想着有一天能达到他们的水平。不过想来当时的我过于naive，急于求成，遇到问题时不想着自己解决而是去问别人。把同学包括老师都问得很烦（绝对是我自己的锅，换成现在的我也会很烦的）。OI教会了我发问之前要先试图去自己解决。

假期结束，高中的基础课开始了。我同时兼顾着OI和课内，稍感力不从心。令人感到安慰的是，我们的班主任很支持我们学习OI。中午和小科课时，我会和几个同学去机房做题，没有受到什么阻挠（虽然不午睡的代价是下午第一节课梦游）。此时我们已经转到了高二真 $\cdot$学长们正在使用的小机房。xjk当时是高一，但已经拿了数学联赛和NOIP的一等奖。当时和高二学长们一起脱产学习OI。也许他选择OI的理由和我类似吧。

有时会有一些考试，几乎每次我都被高一的同学碾压。我一直在努力地试图去缩小我和他们的差距。晚上当周老师讲课的时候，有三个人是没有在听的：wfy和wzq——他们在我刚来时已经在学最短路了，和我——进度落后了一个学期，同时在听课的还有crh——一个和我同届的妹子。

在四月，我经历了第一次大型OI考试：JLOI2015。试想一个刚接触OI 2个月的人省选时的心情吧。在那场考试中，wty学长在第一天现场切掉了两题，而我两天加起来只有30。

学期过半时，另一个问题出现了，其实问题一直都在，只是被忙于文化课和OI的我忽略了而已——中考。再次回到初中的枯燥乏味的东西，我不太甘心。因此一直没有放弃OI，中考也恰好可以作为文化课不写作业的理由。

想来我对应试教育的不满从初中时就已经开始了。所谓中考与高考不知扼杀了多少人的梦想，我想如果每个有梦想的人都有实现梦想的机会，或许此刻在写这篇文章的就是另一个人了吧。（如果对应试教育没有偏见请将以上以及以后出现的此类言论当成一个失败者的借口）

我想我一定是幸运的吧，可以不再拼死拼活的去争取高考的一点分数。如果有人问我没有完整的高中生活是否有遗憾，至少现在我的答案是没有。

中考结束，一切有惊无险。我终于成为了一名高中生。那个暑假，我每天都从早到晚在机房中做题。假期作业保持着刚发时的空白。感觉自己终于有了一点进步，考试时终于不再垫底了。这让我稍微有了一点信心。

这个假期我经历了第一次外出培训，培训时讲了一些我当时觉得很厉害的算法。培训恰逢国赛。我听说了wty学长和wyf学长进入集训队的消息，ygy获得了银牌，xjk拿了D类铜牌。他们是学校OI史上第一届集训队，这对我来说是很大的激励。

假期再次结束，wzq和wfy在学期开始时脱产了。我感到有些寂寞，从教室向机房的队伍中少了一个人（wfy当时和我不是同班）。而我也更加地感到力不从心。有一段时间我晚上从机房回家就会很困，然后第二天早晨3点起来写一些作业（这个三点的闹钟还在培训时把周老师吵醒过一次）。白天在学校有一半的课上会困。我觉得我无法再同时兼顾OI和文化课了。因此我决定脱产。由于老师们的支持，最终父母也同意了我的决定。

我曾经好多次幻想过脱产之后的时光，像梦一般的时光。每天可以没有文化课的苦恼，可以有充足的睡眠，可以全身心投入到OI之中。但这同样有着极大的风险：如果最终没有取得任何成果，那么等待着的将是文化课和高考，而长期停止文化课的学习，试图把落下的补回来付出的代价可想而知。

一边是梦想，一边是煎熬。我能做的只有尽我所能去靠近那个遥不可及的梦想。

脱产后的我接触到了省选级别的知识点，平衡树，树套树，一道稍有难度的题就可能耗费我一天的时间。调试的过程是艰难的。一处随手犯下的错误，找出却需要百倍的努力。思路上的一点错误，可能需要将整个代码写完后才能发现。

我脱产不久后，LLX也脱产了。和我一样从省选知识点学起。11月的深秋是NOIP的时间。NOIP一个月之前机房中迎来了新的一员，或许应该说是最老的一员回归了吧。dzn和我一样提前一年进入高中，是我的上一届。在15年的省选中没能进入省队，NOIP前重新回到机房准备新的一轮。

NOIP一周前其他高一的同学也脱产来准备NOIP。机房的白天也变得热闹起来。但我内心中知道这热闹无法延续。对很多人来说，NOIP的结束就是OI生涯的结束吧。

NOIP开始，我的第一场NOIP。day1前两个题做得比较容易，T3见过一道类似的搜索，如果出到模拟赛里就好了呢，我这样想。但代码能力有限，最终没有调出来。day2T1很容易，T2的dp没有想出来，写了一个70分的暴力（然而访问了负索引其实只有40），然后T3同样最终没有调出来。第一场NOIP，最终以435分这样的分数告终了。wzq在NOIP中发挥失常，我想是紧张导致的吧。

在决定命运的时刻，谁不会紧张呢？越告诉自己不要紧张，反而却越紧张，而OI考试又偏偏是一个需要静下心来的地方，思考题目需要静下心来，写题和调试时更需要静下心来。但这往往是不可能的。旁边人敲击键盘的声音，不停流逝的时间，没有通过的样例，对拍中的一组错误。时刻面临着选择，放弃当前正在调试的题相当于放弃之前一小时甚至几小时的成果，而其他题目又未必会有什么进展。但如果不放弃呢？在你调试的时候别人可能已经在其他题目上有了进展，继续调试不知会花费多长时间，甚至如果到考试结束还没有完成，结果可想而知。即使过了样例，一个隐藏的错误可能会使所有努力付之东流。正因如此，几乎所有考试中，或多或少都会有失误或后悔的地方。

wzq最终选择了退役，他一定是不甘和无奈的吧，毕竟一年半的努力，换来了这样的结果。这是我第一次经历OI中的告别。我也许在内心中知道以后还要经历很多这样的告别。

但这只是暂别呢，是吧？也许在大学，也许在更远的未来，我们还会相遇。

相逢是问候，分手是祝愿。

因为NOIP的成绩不错，而省队有一个女生的名额，因此QT加入了脱产的队伍。

接下来是WC。讲的东西根本没有听懂，更多的时候是看wfy打东方或和LLX玩一个解迷游戏。最终JDFZ所有人的成绩巧合般地组成了一个30到90公差为10的等差数列。没错，我就是那个30。90分的dzn拿到了Au。

接下来的时光在做题与考试中度过。每周六上午是考试，考完试后所有人会一起去桂林路吃饭。那是一段令人怀念的时光。汉堡王，生煎，米伴（这个只有我比较喜欢）。饭后大家一起聊天走回学校。

那段时间的考试，我偶尔可以靠一些奇怪的做法过掉一些题。到了互策的时候就完全变成了互相伤害。而在不知不觉中，省选临近了。

脱产的男生有五个人，而其中最多只有四个人能进入省队。而由于吉林省的强校只有两所，因此对于我们两所学校来说省选完全是校内的竞争。两所学校之间只有AB名额的竞争。我一直认为那个不能进入省队的人应该是我。因为按理来讲，我的水平在五人中最低，并且学籍是高一，还有一年的时间。大概所有人都是这样想的吧，因此学校并没有申请C类名额。

省选day1，我全程在写T2，在考试快要结束的时候调了出来，但最终因为没开long long只有40分。wfy是全场rank1，而dzn却由于失误只有30分。day2我决定不去刚一道题，因此每道题写了一些暴力。最后加起来有一百多分。wfy又是rank1，获得称号万队长。而dzn再次失误还是只有30分。我竟然进了省队。但我很清楚这不是因为我有进入省队的实力，而只是因为实力在我之上的dzn的失误。我所能做的只有继续努力。

接下来是APIO和CTSC。这几场考试对我来说就是暴力大赛而已。晚上我们在五星级宾馆里玩三国杀，很开心。我在APIO卡线拿了银牌，CTSC铜牌。

省选之后的时间过得飞快，紧接着就是清北夏令营。我，xjk，wfy，LLX去了清华，而QT和dzn去了北大。我当时是抱着今年先感受一下的想法参加的夏令营。但题格外顺手。考试时先看了一下T1，感觉不太会，于是去看T2，发现T2很简单，这给了我一些信心，T3是提答。写完T2后回头看T1，想了一个dp，虽然复杂度比较高但常数挺小的。写完之后去做了一下提答。想来这可能是我OI生涯省选级别考试中做得最顺的一次。最后我，xjk，wfy拿到了一本线，而LLX因为没有做上T1只拿到了国赛前一百名降60。

dzn在北大夏令营拿到了rank1，但最终由于是D类，只有降60分和国赛前一百名降一本。QT拿到了前150降20。

想来这次的确算是JDFZOI的辉煌了吧。在一个一本率92%的学校，考上一本线不是一件难事。当时的确感觉一年多的努力没有白费。

但我的目标仅仅是上一所大学吗？我深知自己现在并没有一本线的实力，拿到一本线可以说是因为努力但更多的应该是运气的因素。我需要证明自己，证明自己的确有这样的实力。不然到了大学以后仍然别无所长。我这样告诉自己，但仍然比以前松懈了不少。

接下来到国赛前的一个月中，我们一起到安徽培训。培训基本就是每天考一场试。可能是由于夏令营的成绩比较好吧，培训的时候我们比较松懈，并没有国赛前的紧张气氛。晚上和xjk一起看GOT，LLX一个人玩游戏。隔壁wfy打dota，dzn看番。半夜声音太大时还会吵到周老师。

最后到了16年国赛，省选时的一切再次重演，D1T1所有人都拿了95分然后跑路，T2当场想了一个做法，很迷，也不太好写，但还是勇敢地硬着头皮去写，最后没调过大样例。T3根本没碰。最后发现T2，T3暴力写全每道是70+。D2没管太多写了两题暴力去搞提答。最后193分跑路。

我一直以为在国赛中必须切题才能拿到一个比较好的名次，其实在所有比赛中，如果能做到没有遗憾，那么最终一定可以得到一个理想的结果。

xjk进了集训队，dzn进了前一百，QT拿到了武大一本，wfy差一点没有拿到金牌，LLX没有进到前一百名，而我只拿到了铜牌。

一切尘埃落定，大概每个人都有或多或少的遗憾吧。这就是考试的常态吧。我面对学文化课或是继续脱产的选择没有犹豫。今年我只是没有足够的实力，但我相信再经过一年的努力，我可以证明自己。并且，我还是不想学文化课的。只是觉得太忙，也有些枯燥。

和大家在长江坐船玩了几天。回到学校后，新的一轮OI年开始了。

每天的脱产生活还算愉快，白天在学校做一些题，晚上回家之后就干些别的事情。但是总觉得水平没有太大的提升。

渐渐的，脱产的人多了起来。crh，wyx，lhy，mrc。我还在我的老位置上，而机房渐渐重新热闹起来。而这又能持续多久呢？每天在学校做一些题，用来给自己的空虚一点安慰。我或许有些厌倦了呢。功利地去做一件事情，不免会心生厌倦。而如果没有了功利，又如何坚持呢？当当初的热情消失的时候，对坚持的事物，又剩下些什么呢？

我给自己的理由是，我不想回到教室，回到繁多的课业。我想有属于自己的时间，我想证明自己的能力。于是我坚持着，没有了那份热情，也缺了几分斗志。

又是一年的NOIP。没有顾虑，也没什么压力，两天考完之后感觉没什么问题。出成绩时一点小担心吧。D2T3没清数组挂了90。算是个遗憾吧，但又哪有没有遗憾的考试呢？我更庆幸的是没有更大的遗憾。

今年学校的成绩有些惨淡。lhy第二天文件名写错爆零了。其他人还在继续脱产。一天好像是前一天的重复，一周好像是前一周的重复。在做题，考试，讲课间重复。中间考了一场WC，还是老样子吧。讲课时开始尝试听一听，听不下去也就弃疗了。看xjk推steins gate。WC的考试，没什么参考价值吧，拿一块银牌也就笑笑走人了。

时间过得飞快，又到了4月的省选。其实也没有那么在意吧。

血崩

————简单题不会，暴力打不对

最后靠NOIP的分强行进了A队，垫底。我思考，最后得出结论——我还太菜了。这种水平根本没有自满的资本。删了所有手机电脑游戏。还有不到三个月，我不能让自己为虚度这三个月而后悔。

学校成绩惨淡。mrc，czy都退役了。crh B队，wyx准备买D。机房又一下子冷清下来。在OI中告别已是常态了吧。生活不会事事如愿，我们在世界面前是弱小的，无法改变什么。只能做出自己微薄的努力，去祈求一点未必会有的回报。这世界既不温柔，也不正确。

接着便是APIO和CTSC。可能有些紧张了吧，又是两块银牌。也算在北京玩了几天。

国赛前的一个月在湖南度过，发现自己水平果然还是很低。在这一个月里认识了大佬们，学了很多东西。

最后的国赛。

这可能是我最后的OI比赛了吧。day1写了三个暴力，拿了206分。可能是暴力不太好写吧，发现进了前50。挺开心的，打了一天红警。day2先写了T1的2SAT，然后用力写了一下T2，过了大样例，然后写了T3的暴力。感觉自己很稳。然后决定拍一下T1，GG ，我发现我似乎把2SAT记错了。用力的改，直到考试结束。。。应该能骗到一些分吧，我这样安慰自己。

下午看成绩，

5+100+20=125

T1完美爆炸

一道暴力50+的题我拿了5分，还是无解的5分

OI再见

很不甘心，但已经结束了。一路走来没有什么后悔的地方。

上一年无聊的课内课，然后考一个一本。已经没有什么好害怕的了。

去听讲题，说是去听讲题，其实坐在座位上根本听不进去，T1 A了70多人，呵呵。

然后发成绩单，集训队线431，我TM，我TM，我TM竟然踩了集训队的线！

然后看名单，上面和我同分，我rank51？

隐约记得有一条规定是国赛同分按NOIP成绩计算，然后我成了这个规定适用的第一人？

感觉自己带着莫名喜感，NOI搞笑选手，呵呵。

假期玩了半个多月，开始上学。上课听听课，偶尔犯困，偶尔写写作业。

上了一个月的课，接到通知说我进集训队了？gzz因为学籍的问题集训队资格被取消了？

虽然感觉不太公平，实力在我之上的人因为学籍的问题失去了资格。但更多的是庆幸吧。庆幸自己终于可以不再学基础课，庆幸自己有时间做自己的事情。

不知道坑了多长时间，一直想去写，又迟迟没有动笔，又写了一半弃坑。今天终于补完了，匆忙收笔，有些遗憾，但凡事多少会有遗憾吧。

最后，感谢家长，老师，同学们长期的支持和帮助。感谢你能看完这篇流水账。

以上。

一.题目大意

一行有$$n$$个球，现在将这些球分成$$K$$组，每组可以有一个球或相邻两个球。一个球只能在至多一个组中。求对于$$1\le K\le m$$的所有$$K$$分别有多少种分组方法。答案对$$998244353$$取模。
$$1\le n \le 10^9$$
$$1\le K \le 2^{15}$$

二.解题报告

算法1

设$$f[i][j]$$表示把$$i$$个球分成$$j$$组的方案数。
则$$f[i][j]=f[i-1][j-1]+f[i-2][j-1]+f[i-1][j]$$
最终答案为$$f[n][1...m]$$
时间复杂度$$O(nm)$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5100,mod=998244353;
int n,m;
int f[N][N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    f[1][1]=f[1][0]=f[0][0]=1;
    for(int i=2;i<=n;i++)
    {
        f[i][0]=1;
        for(int j=1;j<=i&&j<=m;j++)
            f[i][j]=((f[i-1][j-1]+f[i-2][j-1])%mod+f[i-1][j])%mod;
    }
    for(int i=1;i<=m;i++)
        printf("%d ",f[n][i]);
    return 0;
}

算法2

设$$a(K)$$表示分为$$K$$组的答案。枚举相邻两个一组的个数$$i$$
$$a(K)=\sum\limits_{i=0}^{min(K,n-K)}C_{n-i}^K C_K^i$$

$$=\sum\limits_{i=0}^{min(K,n-K)} \frac{(n-i)!}{(n-i-K)!i!(K-i)!}$$

其中$$\frac{1}{i!}$$和$$\frac{1}{(K-i)!}$$可以通过$$O(m)$$预处理每次$$O(1)$$计算。
设$$g(i,K) = \frac{(n-i)!}{(n-i-K)!}$$
则$$g(i,K) = g(i,K-1)*(n-i-K+1)$$
对于每个$$K$$可以$$O(m)$$处理。
时间复杂度 $$O(m^2)$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=21000,mod=998244353;
int n,m,ans;
int jc[N],njc[N],g[N];
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void init()
{
    jc[0]=njc[0]=1;
    for(int i=1;i<=m;i++)jc[i]=(ll)jc[i-1]*i%mod;
    njc[m]=qpow(jc[m],mod-2);
    for(int i=m-1;i>=1;i--)
        njc[i]=(ll)njc[i+1]*(i+1)%mod;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<=m;i++)g[i]=1;
    for(int K=1;K<=m;K++)
    {
        ans=0;
        for(int i=0;i<=m;i++)
            g[i]=(ll)g[i]*(n-i-K+1)%mod;
        for(int i=0;i<=K&&i<=n-K;i++)
            ans=(ans+(ll)g[i]*njc[i]%mod*njc[K-i]%mod)%mod;
        printf("%d ",ans);
    }
    return 0;
}

算法3

在算法1基础上将$$f[i][0...m]$$看成一个关于x的多项式，称为$$f[i]$$
通过算法1可知如果已知$$f[n],f[n+1]$$可以$$O(m)$$求出$$f[n+2]$$
考虑在已知$$f[a],f[b],f[a-1],f[b-1]$$时计算$$f[a+b]$$
$$f[a+b]$$即为将长度为$$a$$和长度为$$b$$的两段连接起来得到的。
在连接处有两种情况，如果有一个两个球的组跨过连接处那么为$$f[a-1] * [b-1]$$（乘号为多项式卷积）
否则为$$f[a] * f[b]$$
因此$$f[a+b]=f[a-1] * f[b-1]+f[a] * f[b]$$
卷积可以通过NTT在$$O(m \log m)$$计算
因此可以在$$O(m\log m)$$通过$$f[a],f[b],f[a-1],f[b-1]$$计算$$f[a+b]$$
因此如果已知$$f[a-2],f[a-1],f[a]$$以及$$f[b-2],f[b-1],f[b]$$
可以通过$$f[a-2],f[a-1]$$，$$f[b-2],f[b-1]$$计算$$f[a+b-2]$$
通过$$f[a-1],f[a]$$，$$f[b-2],f[b-1]$$计算$$f[a+b-1]$$
通过$$f[a+b-2],f[a+b-1]$$计算$$f[a+b]$$
因此可以用倍增来计算$$f[n]$$
时间复杂度$$O(m\log n\log m)$$

#include <bits/stdc++.h>
using namespace std;
#define N (1<<16)+10
#define mod 998244353
#define ll long long
int len,n,m,flag;
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void NTT(int *a,int len,int type)
{
    for(int i=0,t=0;i<len;i++)
    {
        if(i>t)swap(a[i],a[t]);
        for(int j=len>>1;(t^=j)<j;j>>=1);
    }
    for(int i=2;i<=len;i<<=1)
    {
        int wn=qpow(3,(mod-1)/i);
        for(int j=0;j<len;j+=i)
        {
            int w=1,t;
            for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
            {
                t=(ll)a[j+k+(i>>1)]*w%mod;
                a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
            }
        }
    }
    if(type==-1)
    {
        for(int i=1;i<=len>>1;i++)swap(a[i],a[len-i]);
        int t=qpow(len,mod-2);
        for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
    }
}
struct node
{
    int a[N],b[N];
    void dft()
    {
        memset(b,0,sizeof(b));
        for(int i=0;i<len>>1;i++)b[i]=a[i];
        NTT(b,len,1);
    }
}a1,a2,a3,b1,b2,b3,ans,ans1,ans2,c1,c2;
void mul(node &r1,const node &r2,const node &r3)
{
    for(int i=0;i<len;i++)
        r1.b[i]=r1.a[i]=(ll)r2.b[i]*r3.b[i]%mod;
    NTT(r1.a,len,-1);
    for(int i=len>>1;i<len;i++)r1.a[i]=0;
}
void inv(node &r1,const node &r2,const node &r3)
{
    r1.a[0]=1;
    for(int i=1;i<len>>1;i++)
        r1.a[i]=(r2.a[i]+r3.a[i-1])%mod;
    r1.dft();
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(len=1;len<(m+1)<<1;len<<=1);
    a2.a[0]=1;a3.a[0]=1;a3.a[1]=1;
    a1.dft();a2.dft();a3.dft();
    for(;n;n>>=1)
    {
        if(n&1)
        {
            if(!flag)
            {
                ans=a3;ans1=a2;ans2=a1;
                flag=1;
            }
            else
            {
                mul(c1,ans,a3);mul(c2,ans1,a2);
                inv(ans,c1,c2);
                mul(c1,ans1,a3);mul(c2,ans2,a2);
                inv(ans1,c1,c2);
                for(int i=0;i<len>>1;i++)
                    ans2.a[i]=((ans.a[i+1]-ans1.a[i+1]+mod)%mod-ans1.a[i]+mod)%mod;
                ans2.dft();
            }
        }
        mul(c1,a2,a2);mul(c2,a1,a1);
        inv(b1,c1,c2);
        mul(c1,a3,a3);mul(c2,a2,a2);
        inv(b3,c1,c2);
        b2.a[0]=1;
        for(int i=1;i<len>>1;i++)
            b2.a[i]=((b3.a[i]-b2.a[i-1]+mod)%mod-b1.a[i-1]+mod)%mod;
        b2.dft();
        a1=b1;a2=b2;a3=b3;
    }
    for(int i=1;i<=m;i++)
        printf("%d ",ans.a[i]);
    return 0;
}

算法4

由算法3知$$f[i]=(x+1)f[i-1]+x f[i-2]$$
求$$f[i]$$的通项公式：
设$$f[i]=C_1 T_1(x)^i+C_2 T_2(x)^i$$
其中$$T_1(x),T_2(x)$$为关于$$T(x)$$的方程$$T(x)^2=(x+1)T(x)+x$$的两根。

解得$$
\left\{
\begin{aligned}
T_1(x)=\frac{x+1+\sqrt{x^2+6x+1}}{2}\\
T_2(x)=\frac{x+1-\sqrt{x^2+6x+1}}{2}
\end{aligned}
\right.
$$

将$$f[0]=1,f[1]=1+x$$带入

解得$$
\left\{
\begin{aligned}
C_1=\frac{T_1(x)}{T_1(x)-T_2(x)}\\
C_2=\frac{T_2(x)}{T_2(x)-T_1(x)}
\end{aligned}
\right.
$$

因此$$f[i]=\frac{T_1(x)^{i+1}-T_2(x)^{i+1}}{T_1(x)-T_2(x)}$$

$$ = \frac{(\frac{x+1+\sqrt{x^2+6x+1}}{2})^{n+1}-(\frac{x+1-\sqrt{x^2+6x+1}}{2})^{n+1}}{\sqrt{x^2+6x+1}}$$

其中$$(\frac{x+1-\sqrt{x^2+6x+1}}{2})^{n+1}$$最低次项大于$$n$$，因此可以舍掉

通过多项式开根，多项式求逆可以$$O(m\log m)$$计算$$\frac{x+1+\sqrt{x^2+6x+1}}{2}$$以及$$\frac{1}{\sqrt{x^2+6x+1}}$$
通过多项式exp以及多项式取ln可以$$O(m\log m)$$计算一个多项式的$$n+1$$次幂
时间复杂度$$O(m\log m)$$

#include <bits/stdc++.h>
using namespace std;
#define N (1<<16)+10
#define ll long long
#define mod 998244353
const int inv2=499122177;
int n,m,len;
int tmp[N],sq[N],inv_sq[N],rt1[N],ln1[N],a[N],ans[N],inv[N];
int test1[N],test2[N],test3[N];
int qpow(int x,int y)
{
    int ret=1;
    while(y)
    {
        if(y&1)ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;y>>=1;
    }
    return ret;
}
void NTT(int *a,int len,int type)
{
    for(int i=0,t=0;i<len;i++)
    {
        if(i<t)swap(a[i],a[t]);
        for(int j=len>>1;(t^=j)<j;j>>=1);
    }
    for(int i=2;i<=len;i<<=1)
    {
        int wn=qpow(3,(mod-1)/i);
        for(int j=0;j<len;j+=i)
        {
            int w=1,t;
            for(int k=0;k<i>>1;k++,w=(ll)w*wn%mod)
            {
                t=(ll)a[j+k+(i>>1)]*w%mod;
                a[j+k+(i>>1)]=(a[j+k]-t+mod)%mod;
                a[j+k]=(a[j+k]+t)%mod;
            }
        }
    }
    if(type==-1)
    {
        for(int i=1;i<len>>1;i++)swap(a[i],a[len-i]);
        int t=qpow(len,mod-2);
        for(int i=0;i<len;i++)a[i]=(ll)a[i]*t%mod;
    }
}
////////////////
void test_root(int *a,int len)
{
    memset(test1,0,sizeof(test1));
    for(int i=0;i<len;i++)
        test1[i]=a[i];
    NTT(test1,len<<1,1);
    for(int i=0;i<len<<1;i++)
        test1[i]=(ll)test1[i]*test1[i]%mod;
    NTT(test1,len<<1,-1);
    for(int i=0;i<len;i++)
        printf("#%d ",test1[i]);
    puts("");
}
void test_inv(int *a,int *b,int len)
{
    memset(test1,0,sizeof(test1));
    memset(test2,0,sizeof(test2));
    for(int i=0;i<len;i++)
        test1[i]=a[i],test2[i]=b[i];
    NTT(test1,len<<1,1);
    NTT(test2,len<<1,1);
    for(int i=0;i<len<<1;i++)
        test3[i]=(ll)test1[i]*test2[i]%mod;
    NTT(test3,len<<1,-1);
    for(int i=0;i<len;i++)
        printf("#%d ",test3[i]);
    puts("");
}
////////////////
void get_inv(int *a,int *b,int len)
{
    static int tmp[N];
    if(len==1)
    {
        b[0]=qpow(a[0],mod-2);
        return;
    }
    get_inv(a,b,len>>1);
    for(int i=0;i<len;i++)tmp[i]=a[i];
    for(int i=len;i<len<<1;i++)tmp[i]=0;
    NTT(tmp,len<<1,1);
    NTT(b,len<<1,1);
    for(int i=0;i<len<<1;i++)
        b[i]=(ll)b[i]*(2-(ll)b[i]*tmp[i]%mod+mod)%mod;
    NTT(b,len<<1,-1);
    for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_root(int *a,int *b,int len)
{
    static int invb[N],tmp[N];
    if(len==1){b[0]=1;return;}
    get_root(a,b,len>>1);
    for(int i=0;i<len<<1;i++)invb[i]=0;
    get_inv(b,invb,len);
    for(int i=0;i<len;i++)tmp[i]=a[i];
    for(int i=len;i<len<<1;i++)tmp[i]=0;
    NTT(tmp,len<<1,1);
    NTT(b,len<<1,1);
    NTT(invb,len<<1,1);
    for(int i=0;i<len<<1;i++)
        b[i]=(ll)inv2*(b[i]+(ll)tmp[i]*invb[i]%mod)%mod;
    NTT(b,len<<1,-1);
    for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_ln(int *a,int *b,int len)
{
    static int inva[N],a1[N];
    for(int i=0;i<len<<1;i++)inva[i]=0;
    get_inv(a,inva,len);
    for(int i=0;i<len;i++)a1[i]=(ll)(i+1)*a[i+1]%mod;
    for(int i=len;i<len<<1;i++)a1[i]=0;
    NTT(a1,len<<1,1);
    NTT(inva,len<<1,1);
    for(int i=0;i<len<<1;i++)a1[i]=(ll)a1[i]*inva[i]%mod;
    NTT(a1,len<<1,-1);
    b[0]=0;
    for(int i=1;i<len;i++)
        b[i]=(ll)a1[i-1]*inv[i]%mod;
    for(int i=len;i<len<<1;i++)b[i]=0;
}
void get_exp(int *a,int *b,int len)
{
    static int lnb[N],tmp[N];
    if(len==1){b[0]=1;return;}
    get_exp(a,b,len>>1);
    for(int i=0;i<len<<1;i++)lnb[i]=0;
    get_ln(b,lnb,len);
    for(int i=0;i<len;i++)tmp[i]=(a[i]-lnb[i]+mod)%mod;
    tmp[0]++;
    for(int i=len;i<len<<1;i++)tmp[i]=0;
    NTT(b,len<<1,1);
    NTT(tmp,len<<1,1);
    for(int i=0;i<len<<1;i++)
        b[i]=(ll)b[i]*tmp[i]%mod;
    NTT(b,len<<1,-1);
    for(int i=len;i<len<<1;i++)b[i]=0;
}
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(len=1;len<=m;len<<=1);
    for(int i=1;i<len;i++)inv[i]=qpow(i,mod-2);
    tmp[0]=1;tmp[1]=6;tmp[2]=1;
    get_root(tmp,sq,len);
    get_inv(sq,inv_sq,len);
    rt1[0]=rt1[1]=1;
    for(int i=0;i<len;i++)
        rt1[i]=(ll)(rt1[i]+sq[i])%mod*inv2%mod;
    get_ln(rt1,ln1,len);
    for(int i=0;i<len;i++)
        ln1[i]=(ll)ln1[i]*(n+1)%mod;
    get_exp(ln1,a,len);
    NTT(inv_sq,len<<1,1);
    NTT(a,len<<1,1);
    for(int i=0;i<len<<1;i++)
        ans[i]=(ll)a[i]*inv_sq[i]%mod;
    NTT(ans,len<<1,-1);
    for(int i=1;i<=m;i++)
        printf("%d ",i>n ? 0:ans[i]);
    return 0;
}