被3整除的子序列

[小菜鸡第一次写题解，请多多指教]

3的倍数特点：所有数位数字之和是3的倍数。

算法思路：二维dp

  1. 集合表示：f[i][j]表示长度为i的字符串中除以3后余数为j
  2. 集合含义：f[i][j]表示子串的个数
  3. 状态转换：将集合划分为两部分，第一部分为a[i]（第i个元素）除以3余数等于j，第二部分为a[i]除以3余数不等j。

现在我们来考虑状态转移方程：f[i][j]可以先考虑为两部分转移过来的：

  1. 第一部分）为长度是i-1的字串除以3余数是j的个数;
  2. 第二部分）为长度是i-1的字串除以3余数是k的个数，这一部分的子串和新加入的a[i]可以组合成新的除以3后余数为j，所以k满足(a[i] % 3 + k) % 3 == j

用代码表示为：

            //对于每一个f[i][j]
            //先求一下k的值
            int k;
            for(k = 0; k < 3; k++)
            {
                if((k + a[i] % 3) % 3 == j)
                    break;
            }
            //状态转移方程为：f[i][j] = f[i - 1][j] + f[i - 1][k]
            //需要注意的是：a[i]模3的余数可能是j，若为j的话，f[i][j]相对于（f[i - 1][j] + f[i - 1][k]）要新加如一个a[i],所以要加1
            if(a[i] % 3 == j) f[i][j] =  (f[i - 1][j] + f[i - 1][k] + 1) % mod;
            else  f[i][j] = (f[i - 1][j] + f[i - 1][k]) % mod;

所以将以上整合，代码为：

#include<iostream>
#include<cstring>
using namespace std;

const int N = 55, mod = 1e9 + 7;
char s[N];
int a[N];
int f[N][N];//长度为i的模3余数是j的字串个数

int main()
{
    scanf("%s", s);
    int n = strlen(s);
    for(int i  = 0; i < n; i++) a[i + 1] = s[i] - '0';

    
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < 3; j++)
        {
            //对于每一个f[i][j]
            //先求一下k的值
            int k;
            for(k = 0; k < 3; k++)
            {
                if((k + a[i] % 3) % 3 == j)
                    break;
            }
            //状态转移方程为：f[i][j] = f[i - 1][j] + f[i - 1][k]
            //需要注意的是：a[i]模3的余数可能是j，若为j的话，f[i][j]相对于（f[i - 1][j] + f[i - 1][k]）要新加如一个a[i],所以要加1
            if(a[i] % 3 == j) f[i][j] =  (f[i - 1][j] + f[i - 1][k] + 1) % mod;
            else  f[i][j] = (f[i - 1][j] + f[i - 1][k]) % mod;
        }
    
    printf("%d", f[n][0]);
    return 0;
}

补充知识点：1. C++中字符数组的输入输出 2. C++中如何表示字符数组的字符长度（strlen()）