这是一条一维探测带上的约束计数。每个非异常源格子上的数字,等于它左右邻居中异常源的个数。
从左到右扫描字符串,维护三个量(均对 109+7 取模):
一条长度为 n 的线性探测带上,每个格子的状态用一个字符表示:
* 表示该格已经确认存在异常源;0、1、2 表示该格没有异常源,且其左右相邻格子中异常源的个数恰好等于该数字;? 表示该格尚未判定,既可以是异常源,也可以不是。请统计有多少种把所有 ? 填成“有异常源 / 无异常源”的方案,使得整条探测带与已给出的数字约束完全一致。答案对 109+7 取模。
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.