int nextt[1000005]; void get_nextt(char pattern[]){//为pattern字符串创建nextt数组 nextt[0] = 0; int max_length = 0; for(int i = 1;pattern[i];i++){ while(max_length > 0 && pattern[max_length] != pattern[i]) max_length = nextt[max_length-1]; if(pattern[i] == ...

动态规划这玩意在ACM中比较重要，但个人对其理解不深，所以想刷刷相关题目，就在此记录下所刷题目（点击标题可进入原题地址） 1、被3整除的子序列 描述 给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除，答案对1e9+7取模 思路 对于一个整数，如果其所有位数之和是3的倍数，那么这个整数也就是3的倍数，证明很容易，这里略过。那么，假设dp[i][j]表示前i个数字中的子序列，对3取余为j的数量，则dp[i+1][j]就可由前面和第i+1个数字推出。举个例子，第i+1个数字取余3为2，那么dp[i+1][0] += dp[i][1] //前面i个子序列中，余数为1的组合，加上余数...