首页 › 题库 › C/C++编程考级 › C/C++编程四级 › 简答题
简答题 偏难
#13212

多样解码 将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一…

多样解码

将一个由大写英文字母组成的字符串加密为一个数字串,可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是,反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`,也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的,不能被解码为 `H`。

本题就请你计算一下,给定的数字串有多少种不同的解码结果。

时间限制:1000

内存限制:65536

输入

输入在一行中给出一个不超过 104 位的数字串,串非空且不包含空格。

输出

输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大,你只需要输出其对 1000000007 取模后的结果。


样例输入

1213407

样例输出

5
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1000000007; int main() { string s; cin &gt;&gt; s; int n = s.size(); vector&lt;long long&gt; dp(n + 1, 0); dp[0] = 1; // 空字符串有一种解码方式 for (int i = 1; i &lt;= n; ++i) { // 单独处理当前字符,总是允许 dp[i] = dp[i-1]; // 处理两位的情况 if (i &gt;= 2) { // 提取前两位字符并转换为整数 int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0'); if (two_digit &gt;= 10 &amp;&amp; two_digit &lt;= 25) { dp[i] += dp[i-2]; } } dp[i] %= MOD; } cout &lt;&lt; dp[n] % MOD &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。