280 人解决,348 人已尝试。
342 份提交通过,共有 1895 份提交。
2.8 EMB 奖励。
单点时限: 2.0 sec
内存限制: 512 MB
有一个电视直播节目,其中有一个神秘单词 $W$,猜中单词的人可以获得大奖,但是要完全猜中一个单词太难了,所以节目组决定放宽一下条件。
如果你猜的单词中每个字母,都至少和神秘单词中相同位置相差不超过一个位置的字母相同,就可以获得一份小奖。
形式化的说,对于一个猜的单词 $G$,获奖的条件为 $(|G|=|W|)\land \forall~i~((1 \leq i \leq |G|) \rightarrow \exists~j~((\max(1, i-1) \leq j \leq \min(i+1, |G|))\land(G_i=W_j)))$,其中 $G_i$ 表示字符串 $G$ 中的第 $i$ 个字母(字符串$G$中的第1个字母下标为1),$|G|$表示字符串$G$的长度。
节目组想知道对于一个指定的神秘单词 $W$ 有多少种可能获奖的猜测单词(包括大奖和小奖),因为可能的单词数量太多了,他们想知道答案对 $1~000~000~007$ 取模的结果。
神秘单词 $W$($1 \leq |W| \leq 1~000$),保证单词全部由小写英文字母构成。
其中 10% 的数据保证 $|W| \leq 10$。
输出可能中奖的单词数量对 $1~000~000~007$ 取模后的结果。
yes
12
y
1
yy
1
对于神秘单词 yes
,所有可以获奖的单词包括:
yes
, yys
, yss
, yee
, yye
, yse
, ees
, eys
, ess
, eee
, eye
, ese
。
280 人解决,348 人已尝试。
342 份提交通过,共有 1895 份提交。
2.8 EMB 奖励。
创建: 6 年,4 月前.
修改: 4 年,10 月前.
最后提交: 2 月,4 周前.
来源: N/A