有一个 行 列的棋盘，每个棋子可以攻击到本行、上一行、下一行的一些棋子，求有多少种放棋子的方案使得任意两个棋子都不会互相攻击。

已知

给定 ，求 。

给一个图，求从 点到 点恰好经过 步的最短路。

给一个图，有一些鳄鱼在两个、三个或四个点之间周期性移动，求从 点到 点，恰好走 步，任意时刻都不与鳄鱼同时到达同一个点的方案数。

给一个长度为 的字符串 ，求长度为 且不包含 的字符串的数量。

对于一个给定的字符串 ，有多少连续子串是 prefix-suffix-square free 的。

一个字符串被称为 square 当且仅当它可以由两个相同的串连接而成。例如，abab，aa 是 square，而 aaa，abba 不是。一个字符串是 prefix-suffix-square free 的当且仅当他的任何前缀或者后缀都不是 square。

给三个字符串 ，求一个长度最大的 ，满足：

1. 是 的子串；
2. 是 的子串；
3. 不是 的子串；

给 个字符串，询问每个字符串有多少子串（不要求本质不同，不包括空串）是所有 个字符串中至少 个字符串的子串。

对于一个长度为 的字符串 ，将其本质不同的所有子串按照字典序排序。我们定义两个子串的相似程度为 的最大值，其中 、 满足：，，，。

每次询问排序后的第 个和第 个子串的相似程度。

对于一个字符串 ，每次从它的首部或尾部弹出一个字符，加入到 的尾部，求可以构造出的字典序最小的 。