软通动力-编程能力在线评测系统

Problem1022--#547. 「LibreOJ β Round #7」匹配字符串

Time Limit: 2 Sec Memory Limit: 512 MB
Submit: 3 Solved: 1
[Submit] [Status] [Web Board] [Creator:]

对于一个 01 串（即由字符 0 和 1 组成的字符串） $s$ ，我们称 $s$ 合法，当且仅当串 $s$ 的任意一个长度为 $m$ 的子串 $s ' $ ，不为全 1 串。

请求出所有长度为 $n$ 的 01 串中，有多少合法的串，答案对 $65537$ 取模。

输入共一行，包含两个正整数 $n, m$ 。

输出共一行，表示所求的和对 $65537$ 取模的结果。

5 2

以下是所有合法的串：

2018 7

对于所有的数据，满足 $1≤n,m≤687215739041\le n,m\le 68721573904$ 。

详细的数据限制及约定如下（留空表示和上述所有数据的约定相同）：

Subtask #	分值	$n$	$m$
1	$6$	$≤18\le 18$	$≤18\le 18$
2	$7$	$≤109\le 10^9$	$≤2\le 2$
3	$15$	$≤106\le 10^6$	$≤106\le 10^6$
4	$10$	$≤109\le 10^9$	$≤50\le 50$
5	$14$	$≤109\le 10^9$	$≤500\le 500$
6	$15$	$≤4295098369\le 4295098369$	-
7	$18$	$≤17180393476\le 17180393476$	-
8	$15$	-	-