[nk] 被3整除的数 线性DP

前言

线性DP 也太难了吧 哈哈哈哈 传送门 : https://ac.nowcoder.com/acm/problem/21302

思路

一开始 以为是 一层状态 f [ i ] f[i] f[i] 表示 以当前数结尾的 总方案数 但是推方程的时候 简直无从下手

因此我们再引入一个状态 f [ i ] [ j ] f[i][j] f[i][j]表示 以 S [ i ] S[i] S[i]结尾的,取%后为 J J J的集合

这样子才可以用 J J J开始推嘛

因此不难想出

对于当前这个数

• 选 f [ i ] [ j ] = f [ i − 1 ] [ ( 3 + ( j − x ) ) % 3 ] f[i][j] =f[i-1][(3+(j-x))\%3] f[i][j]=f[i−1][(3+(j−x))%3] 前面的数相加 可以被3整除 例如:12 f [ i ] [ j ] = f [ i ] [ j ] + 1 f[i][j] = f[i][j]+1 f[i][j]=f[i][j]+1 单独加上自己

• 不选 f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] =f[i-1][j] f[i][j]=f[i−1][j] 直接从 i − 1 i-1 i−1 推过来

简单吧？ 哈哈哈哈哈

CODE

/**
f[i][j] 表示 以s[i]结尾对 3 取余后为j的集合
**/

#include 
using namespace std;
using ll = long long;

const int N = 1e5+10;
const ll mod = 1e9+7;
ll dp[N][3];

void solve()
{
    string s ;
    cin>>s;
    s=" "+s;
    int n  = s.size();

    dp[1][(s[1]-'0')%3] = 1;

    for(int i=2;i