2747 - 遗忘的密码

题目描述

故事发生在一个神秘的城市中,主人公小 G 忘记了他的个人识别码(PIN)。

这个 PIN 是一个仅由 0、1、…、9组成的四位数字字符串,可以以数字 0 开头。

对于每个数字 0 到 9,小 G 只模糊记得一些相关信息,信息用一个由 10 个字符组成的字符串 S_0, S_1, …, S_9 表示:

  1. 如果 S[i] 是 o:他确信 PIN 中包含数字 i;

  2. 如果 S[i] 是 x:他确信 PIN 不包含数字 i;

  3. 如果 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 码。

【样例 2 解释】

o?oo?oxoxo,确定包含 0、2、3、5、7、9,确定包含的数字有 6 位,但 PIN 码只有 4 位,所以可能性为 0。

【样例 3 解释】

xxxxx?xxxo , 数字 9 一定包含,数字 5 可能包含,一共 15 种可能性。

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 0 枚
难度 基础


上一题 下一题