A27936. 多样解码将一个由大写英文字母组成的字符串加密为一个数字串，可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是，反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`，也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的，不能被解码为 `H`。本题就请你计算一下，给定…
填空题
较难
知识点
题目描述
多样解码
将一个由大写英文字母组成的字符串加密为一个数字串，可以简单地将 A ~ Z 转换为 0 ~ 25。但是这种方法带来的问题是，反向解码的结果可能是不唯一的。例如 `1213407` 既可以解码为 `BCBDEAH`，也可以解码为 `MBDEAH`、 `BCNEAH`、`BVDEAH` 或 `MNEAH`。注意 `07` 和 `7` 是有区别的，不能被解码为 `H`。
本题就请你计算一下，给定的数字串有多少种不同的解码结果。
输入
输入在一行中给出一个不超过 104 位的数字串，串非空且不包含空格。
输出
输出该数字串对应的不同解码结果的数量。这个数量可能非常巨大，你只需要输出其对 1000000007 取模后的结果。
样例输入
1213407样例输出
5参考答案
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
string s;
cin >> s;
int n = s.size();
vector<long long> dp(n + 1, 0);
dp[0] = 1; // 空字符串有一种解码方式
for (int i = 1; i <= n; ++i) {
// 单独处理当前字符，总是允许
dp[i] = dp[i-1];
// 处理两位的情况
if (i >= 2) {
// 提取前两位字符并转换为整数
int two_digit = (s[i-2] - '0') * 10 + (s[i-1] - '0');
if (two_digit >= 10 && two_digit <= 25) {
dp[i] += dp[i-2];
}
}
dp[i] %= MOD;
}
cout << dp[n] % MOD << endl;
return 0;
}
上一题
下一题