题解 | 小红过61

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL; // 题目要求的模数，防止数值溢出

int main() {
    // 优化输入输出速度：关闭cin与stdio同步，解绑cin和cout
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    if (!(cin >> s)) return 0; // 处理输入失败的边界情况
    
    // 动态规划状态定义（核心思想：先包含空序列简化计算，最后再剔除）
    ll total = 1; // 初始为1，表示空序列（所有合法子序列总数，包含空序列）
    ll end6 = 0;  // 记录所有合法子序列中以'6'结尾的数量（初始无字符，故为0）
    
    // 遍历每个字符，逐字符更新状态（时间复杂度O(n)，n为字符串长度）
    for (char ch : s) {
        ll prev = total; // 保存当前total的原始值（后续total会更新，需用原始值计算end6）
        
        ll allowed; // 定义allowed：可以拼接当前字符ch的合法子序列数量
        if (ch == '1') {
            // 情况1：当前字符是'1'——不能接在以'6'结尾的子序列后（避免形成"61"）
            // allowed = 所有合法子序列 - 以'6'结尾的子序列（仅保留非6结尾的合法子序列）
            allowed = (total - end6) % MOD;
        } else {
            // 情况2：当前字符不是'1'（是6或其他数字）——所有合法子序列都可拼接
            allowed = total % MOD;
        }
        
        // 更新total：新的子序列总数 = 原有子序列（不选当前字符） + 拼接当前字符的新子序列（选当前字符）
        total = (total + allowed) % MOD;
        
        // 若当前字符是'6'，更新以'6'结尾的子序列数量
        if (ch == '6') {
            // end6 = 原有以6结尾的子序列（不选当前6） + 拼接当前6的新子序列（选当前6，数量为prev即原total）
            end6 = (end6 + prev) % MOD;
        }
        // 注：字符是1/其他非6字符时，end6无需更新（不会新增以6结尾的子序列）
    }
    
    // 最终结果：total包含空序列，需减1得到非空合法子序列数
    ll ans = (total - 1) % MOD;
    if (ans < 0) ans += MOD; // 处理total=0（空字符串）时的负数情况
    cout << ans << '\n';
    return 0;
}