故事发生在一个神秘的城市中,主人公小 G 忘记了他的个人识别码(PIN)。
这个 PIN 是一个仅由 0、1、…、9组成的四位数字字符串,可以以数字 0 开头。
对于每个数字 0 到 9,小 G 只模糊记得一些相关信息,信息用一个由 10 个字符组成的字符串 S_0, S_1, …, S_9 表示:
如果 S[i] 是 o:他确信 PIN 中包含数字 i;
如果 S[i] 是 x:他确信 PIN 不包含数字 i;
如果 S[i] 是 ?:他不确定 PIN 中是否包含数字 i。
现在的问题是:有多少个字符串可能是小 G 的 PIN ?
PIN 的模糊相关信息,一个只包含 o、x、? 的字符串。
所有正确的 PIN 码个数。
ooo???xxxx
108
o?oo?oxoxo
0
xxxxx?xxxo
15
所输入的字符串,只可能包含 x、o、?。
【样例 1 解释】
ooo???xxxx,可以确定四位的 PIN 一定包含: 0、1、2,一定不包含:6、7、8、9。
? 表示可能包含。
一共有 108 种正确的 PIN 码。
比如:0123 、 0021 等等,都是正确的 PIN 码。
o?oo?oxoxo,确定包含 0、2、3、5、7、9,确定包含的数字有 6 位,但 PIN 码只有 4 位,所以可能性为 0。
xxxxx?xxxo , 数字 9 一定包含,数字 5 可能包含,一共 15 种可能性。