鏈接：登錄—專業(yè)IT筆試面試備考平臺_?？途W

給定一個正整數 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)

如果前面出現過的話你發(fā)現會和之前的產生重復就是第3位12出現了兩次

我們發(fā)現第三位的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';}