题解

一个数是 \(9\) 的倍数的充要条件是各个数位上的数加起来和是 \(9\) 的倍数。

原问题可以转化成，有多少种取法使得选择该字符串中某些位置的数使得这些位置的数加起来为 \(9\) 的倍数（模 \(9\) 为 \(0\)）。可以发现，这个问题可以看成一个 \(0-1\) 背包问题。

用\(dp[i][j]\) 表示字符串前 \(i\) 位，选取的位数和模 \(9\) 结果为 \(j\) 的所有取法的集合，属性值为方案数。根据\(0-1\)背包的状态转移，可以类似得到：不选取当前的第 \(i\) 位，方案数为 \(f[i-1][j]\); 选取当前的第 \(i\) 位，方案数为 \(f[i-1][(j-s[i])\%9]\) ，其中\(s[i]\) 代表第 \(i\) 位的数字。状态转移即为
\[ f[i][j] = f[i-1][j] + f[i-1][(j-s[i]\%9)] \]

最后本题所需要的结果即为 \(f[n][0]-1\)，需要减一的原因是一个数不取也是满足模 \(9\) 为 \(0\) 的条件的，但是原问题中子序列不能为空。

示例代码

const int N = 2e5 + 10, MOD = 1e9 + 7;

int f[N][10];

int get_mod(int x, int n)
{
    return (x % n + n) % n;
}
void Solve()
{
    string str; cin >> str;
    
    int n = str.size();
    
    f[0][0] = 1;
    for(int i=1; i<=n; i++)
        for(int j=0; j<9; j++)
        {
            f[i][j] = f[i-1][j];
            
            int x = str[i-1] - '0';
            f[i][j] = (f[i-1][get_mod(j-x, 9)] + f[i][j]) % MOD;
        }
        
    cout << (f[n][0] - 1 + MOD) % MOD << endl;
}