1253: LOJ547 -「LibreOJ β Round #7」匹配字符串
[Creator : ]
Description
对于一个 01 串（即由字符 0 和 1 组成的字符串）s，我们称 s 合法，当且仅当串 s 的任意一个长度为 m 的子串 s'，不为全 1 串。
请求出所有长度为 n 的 01 串中，有多少合法的串，答案对 65537 取模。
请求出所有长度为 n 的 01 串中，有多少合法的串，答案对 65537 取模。
Input
输入共一行，包含两个正整数 n,m。
Output
输出共一行，表示所求的和对 65537 取模的结果。
Constraints
对于所有的数据，满足 1≤n,m≤68,721,573,904。
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：
| Subtask # | 分值 | n | m |
|---|---|---|---|
| 1 | 6 | ≤18 | ≤18 |
| 2 | 7 | $\le 10^9$ | ≤2 |
| 3 | 15 | $\le 10^6$ | $\le 10^6$ |
| 4 | 10 | $\le 10^9$ | ≤50 |
| 5 | 14 | $\le 10^9$ | ≤500 |
| 6 | 15 | ≤4295098369 | - |
| 7 | 18 | ≤17180393476 | - |
| 8 | 15 | - | - |
Sample 1 Input
5 2
Sample 1 Output
13
以下是所有合法的串：
00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
Sample 2 Input
2018 7
Sample 2 Output
27940