昆山高端网站设计建设,网站建设预招标,如何用手机制作游戏,企业网站建设熊掌号链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 给定一个正整数 n#xff0c;你可以对 n 进行任意次#xff08;包括零次#xff09;如下操作#xff1a;
选择 n 上的某一数位#xff0c;将其删去#xff0c;剩下的左右部分合并。例如 123#xff0c;你可以选择…链接登录—专业IT笔试面试备考平台_牛客网 给定一个正整数 n你可以对 n 进行任意次包括零次如下操作
选择 n 上的某一数位将其删去剩下的左右部分合并。例如 123你可以选择删去第二位 2得到新数 13。
在对 nnn 进行操作后请问有多少种不同的 n使得n 不是 3 的倍数 由于结果可能非常大请输出对 1000000007 取模的结果。
思路
线性dp去求解
从前往后去枚举看有多少个时符合条件的
数组dp[i][j]记录当枚举刀第i个其中所以mod3结果是j的数j0,1,2
然后去转移
比如1223
取123时 你的2可以从第三位和第二位的2继承过来的
dp的转移就是在前面已有的数字末尾加上一个数如果这个数字是前面没有出过的话就在该位上加上1
第一位 1(0*211)
第二位 1,12,2(1*213)
第三位 1,12,2,12,122,22(3*206)
如果前面出现过的话你发现会和之前的产生重复就是第3位12出现了两次
我们发现第三位的12其实一次从第一位的1加上2继承下去一次从第二位的1加上一个2继承下去
本质上就是从前一位多继承了一次因此减去前一位的数就行了也就是去重一下
第一位 1(0*211)
第二位 1,12,2(1*213)
第三位 1,12,2,122,22(3*20-15)
第四位1,12,2,122,22,13,123,23,1223,223,3(5*2111)
最后在开3位记录是否被3整除是多少就行了
#includeiostream
#includealgorithm
#includenumeric//accumulate(be,en,0)
#includecstring//rfind(string),s.find(string,begin)!s.npos,find_first _of(),find_last_of()
#includestring//to_string(value),s.substr(int begin, int length);
#includecstdio
#includecmath
#includevector//res.erase(unique(res.begin(), res.end()), res.end()),reverse(q.begin(),q.end());
#includequeue//priority_queue(big) /priority_queueint, vectorint, greaterint q(small)
#includestack
//#includemap//unordered_map
#includeset//iterator,insert(),erase(),lower()/upper_bound()(value)/find()return end()
#includeunordered_map
#includeunordered_set
#includebitset//size,count(size of 1),reset(to 0),any(have 1?)
//#includeext/pb_ds/assoc_container.hpp//gp_hash_table
//#includeext/pb_ds/hash_policy.hpp
//using namespace __gnu_pbds;
#define int long long//__int128 2^127-1(GCC)
#define PII pairint,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;}
