2023河南萌新联赛第（五）场：郑州轻工业大学C-数位dp

链接：登录—专业IT笔试面试备考平台_牛客网

给定一个正整数 n，你可以对 n 进行任意次（包括零次）如下操作：

• 选择 n 上的某一数位，将其删去，剩下的左右部分合并。例如 123，你可以选择删去第二位 2，得到新数 13。

在对 nnn 进行操作后，请问有多少种不同的 n，使得n 不是 3 的倍数？
由于结果可能非常大，请输出对 1000000007 取模的结果。

思路：

线性dp去求解

从前往后去枚举看有多少个时符合条件的 

数组dp[i][j]记录当枚举刀第i个其中所以mod3结果是j的数j=0,1,2

然后去转移

比如1223

取123时 你的2可以从第三位和第二位的2继承过来的

dp的转移就是在前面已有的数字末尾加上一个数，如果这个数字是前面没有出过的话就在该位上加上1

第一位 1(0*2+1=1)

第二位 1,12,2(1*2+1=3)

第三位 1,12,2,12,122,22(3*2+0=6)

如果前面出现过的话你发现会和之前的产生重复就是第3位12出现了两次

我们发现第三位的12其实一次从第一位的1加上2继承下去，一次从第二位的1加上一个2继承下去

本质上就是从前一位多继承了一次，因此减去前一位的数就行了，也就是去重一下

第一位 1(0*2+1=1)

第二位 1,12,2(1*2+1=3)

第三位 1,12,2,122,22(3*2+0-1=5)

第四位1,12,2,122,22,13,123,23,1223,223,3(5*2+1=11)

最后在开3位记录是否被3整除是多少就行了

#include<iostream>
#include<algorithm>
#include<numeric>//accumulate(be,en,0)
#include<cstring>//rfind("string"),s.find(string,begin)!=s.npos,find_first _of(),find_last_of()
#include<string>//to_string(value),s.substr(int begin, int length);
#include<cstdio>
#include<cmath>
#include<vector>//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end());
#include<queue>//priority_queue(big)  /priority_queue<int, vector<int>, greater<int>> q(small)
#include<stack>
//#include<map>//unordered_map
#include<set>//iterator,insert(),erase(),lower(>=)/upper_bound(>)(value)/find()return end()
#include<unordered_map>
#include<unordered_set>
#include<bitset>//size,count(size of 1),reset(to 0),any(have 1?)
//#include<ext/pb_ds/assoc_container.hpp>//gp_hash_table
//#include<ext/pb_ds/hash_policy.hpp>
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pair<int,int>
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 1e9 + 7;
int dp[N][3];
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);string s;cin >> s;s = ' ' + s;int n = s.length();int pre[10] = { 1 };dp[0][0] = 1;for (int i = 1; i < n; i++) {int x = s[i] - '0';int m = pre[x];for (int j = 0; j < 3; j++)dp[i][(j + x) % 3] = (dp[i - 1][(j + x) % 3] + dp[i - 1][j]) % mod;if (m){for (int j = 0; j < 3; j++)dp[i][(j + x) % 3] = (dp[i][(j + x) % 3] + mod - dp[m - 1][j]) % mod;}pre[x] = i;}cout << (dp[n - 1][1] + dp[n - 1][2]) % mod << '\n';}