题解 | #被3整除的子序列#

感谢 牛客387909056号的题解，我看其他人的题解感觉看不懂的样子，后来看了他的，发现其他人讲的不够准确，十分感谢他，让我做出来了这一题。 为了巩固加强思路，我也来发一个题解，记录我写题的过程。 开始，没有头绪，想着这个是怎么跟dp扯上关系的呢，开始看题解，发现哦哦，原来看余数就可以了。于是我去尝试写代码，到这个状态转移方程这又卡住了，百思不得其解，最后看题解好久才明白。

• dp五步：
  dp数组以及下标含义 dp[i][j] 表示到第i个数时，余数为j的序列个数。

  递推公式 dp[i][j] = dp[i-1][j] + dp[i-1][ (j + 3 - x) ] 含义：（x表示第i个数的余数）到第i个数时，余数为j的序列个数 为 第i-1个数时余数为j的个数 + 第i-1个数的余数加上第i个数的余数x等于余数j的个数。

  dp数组如何初始化
  遍历顺序
  打印dp数组 之后遍历后，打印dp[len][0]就行;

#include <vector>
#include <string>
#include <set>
#include <cstring>
#include <map>
#include <stdio.h>
#include <algorithm>
using namespace std;

#define rep(i,x,n) for(int i = x; i <= n; i++)

typedef long long LL;
typedef pair<int,int> PII;

const int N = 121;
const int Mod = 1e9+7;
int dp[N][3]; // 到第i个数时，余数为j的序列个数 为 
// 第i-1个数时余数为j的个数 + 第i-1个数的余数加上第i个数的余数x等于余数j的个数
char str[N];
void test();
int main()
{
    cin>>str;
    int x = str[0] - '0'; // 字符型转整型
    x %= 3; // 求余数
    dp[0][x] = 1;
    int len = strlen(str); // 字符串长度
    for(int i = 1; i < len; ++i) {
        x = str[i] - '0'; 
        x %= 3;
        dp[i][x] = 1;
        for(int j = 0; j < 3; ++j) { // 余数为j的个数
            dp[i][j] += (dp[i-1][j] + dp[i-1][(j + 3 - x)%3])%Mod;
        }
    } 
    cout<<dp[len-1][0];
    return 0;
}

void test() {
    #define mytest
    #ifdef mytest
    freopen("ANSWER.txt", "w",stdout);
    #endif
}