CF316A2 Special Task

特工 Smart Beaver 在 ABBYY 的一个秘密研究部门工作。他在那里工作了很久，对自己的工作非常满意，因为这份工作让他能在最好的餐厅用餐，并点最昂贵、最稀有的木材美食。 这位满足的特工接到了一个重要任务：获取英国科学家关于英语语言的最新研究成果。这些成果经过加密，被存放在一个大型保险箱中。海狸的牙齿非常坚固，所以上级保证他到达现场后，打开保险箱不会有任何问题。 他吃完了他的杨木枝条，便出发去执行这个重要任务。当然，海狸顺利到达了现场，但遗憾的是，他无法用自己强壮的大牙打开保险箱。就在这时，Smart Beaver 接到了总部的电话，得知其实并不需要用牙齿开箱，因为有可靠的消息来源发来了如下信息：保险箱的密码由数字组成，且没有前导零。同时，还给出了一个特殊的提示字符串 $s$，其结构如下： - 如果 $s_i$ 为 "?"，则密码的第 $i$ 位可以是任意数字（$0$ 到 $9$，包括 $0$ 和 $9$）； - 如果 $s_i$ 是一个数字（$0$ 到 $9$），则密码的第 $i$ 位必须是该数字； - 如果字符串中包含字母 "A" 到 "J"，则所有相同字母的位置必须填相同的数字，不同字母的位置必须填不同的数字。 - 密码的长度与提示字符串的长度相同。 例如，提示 "?JGJ9" 有如下合法的密码方案："51919"、"55959"、"12329"、"93539" 等，也有不合法的方案："56669"、"00111"、"03539"、"13666"。 收到这些信息后，上级改变了计划，要求特工们安静温和地工作，不要再尝试用机械手段打开保险箱，而是根据提示字符串找出密码。 在特工学校时，Smart Beaver 是全班最快找出这类保险箱密码的人，但现在他已经不如当年了……请你帮他计算，满足给定提示的密码有多少种可能。得到这个信息后，结合自己输入密码的速度，Smart Beaver 就能判断今晚能否赶上最喜欢的电视节目《海狸追踪》，还是要熬夜工作了。

第一行包含字符串 $s$，表示保险箱密码的提示。字符串 $s$ 由以下字符组成：?、0-9、A-J。保证字符串 $s$ 的第一个字符不是 $0$。 对于 30 分的子任务（子任务 A1）： - $1 \leq |s| \leq 5$。 对于 100 分的子任务（子任务 A1+A2）： - $1 \leq |s| \leq 10^5$。 其中 $|s|$ 表示字符串 $s$ 的长度。

输出满足提示的密码的种数。

由 ChatGPT 4.1 翻译