2709 - 遗忘的密码

题目描述

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

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

对于每个数字 09,小 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 的模糊相关信息,一个只包含 ox? 的字符串。

输出

所有正确的 PIN 码个数。

样例

输入

ooo???xxxx

输出

108

输入

o?oo?oxoxo

输出

0

输入

xxxxx?xxxo

输出

15
说明

【数据说明】

所输入的字符串,只可能包含 xo?

【样例 1 解释】

ooo???xxxx,可以确定四位的 PIN 一定包含: 012,一定不包含:6789

? 表示可能包含。

一共有 108 种正确的 PIN 码。

比如:01230021 等等,都是正确的 PIN 码。

【样例 2 解释】

o?oo?oxoxo,确定包含 023579,确定包含的数字有 6 位,但 PIN 码只有 4 位,所以可能性为 0

【样例 3 解释】

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

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


上一题 下一题