因为是子序列,所以可以不连续,因此需要保存每个区间上余数为0,1,2的数目 用dp[i][k] 表示从0到i区间上,余数为k的数目 因为每次区间扩张一个数时,如果这个数的对3的余数为1,那么只要这个新的数结合上上一个区间余数为2的数列,新的子序列的余数就是0了,
别忘了还有原先子序列本来余数就是0的数,对于这些数来讲,不需要加上新来的数,因此直接继承即可。
也就是 dp[i][0]=dp[i-1][0]+dp[i-1][2];
同样的,dp[i][1]=dp[i-1][1]+dp[i-1][0]+1;
只要0~i-1区间上余数为0的数列,加上新来的第i个数后,就是余数为1了。另外因为新的数本身就是余数为1,它自己就能构成只有它自己的子序列,所以需要加1。另外还加上原来余数就为1的数。
那么同理,dp[i][2]=dp[i-1][1]+dp[i-1][2].
另外还需讨论新的数余数为0,2的情况。不再赘述。
代码:
#include<iostream>
#include<string>
using namespace std;
long long mod=1e9+7;
long long dp[55][5]; //从0到j区间上,余数为k的数目
int main()
{
string num;
cin>>num;
int n=num.length();
for(int i=0;i<n;i++)
{
dp[i][(num[i]-'0')%3]=1;
}
for(int i=1;i<=n-1;i++)
{
if((num[i]-'0')%3==0)
{
dp[i][0]=2*dp[i-1][0]+1;
dp[i][1]=2*dp[i-1][1];
dp[i][2]=2*dp[i-1][2];
}
else if((num[i]-'0')%3==1)
{
dp[i][0]=dp[i-1][0]+dp[i-1][2];
dp[i][1]=dp[i-1][0]+dp[i-1][1]+1;
dp[i][2]=dp[i-1][1]+dp[i-1][2];
}
else
{
dp[i][0]=dp[i-1][0]+dp[i-1][1];
dp[i][1]=dp[i-1][1]+dp[i-1][2];
dp[i][2]=dp[i-1][2]+1+dp[i-1][0];
}
for(int j=0;j<3;j++) dp[i][j]%=mod;
}
cout<<dp[n-1][0];
}
全部评论
(1) 回帖