题干：
给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模
输入描述:
输入一个字符串，由数字构成，长度小于等于50 输出描述:
输出一个整数 示例1
输入
132 输出
3 示例2
输入
9 输出
1 示例3
输入
333 输出
7 示例4
输入
123456 输出
23 示例5
输入
00 输出
3 备注:
n为长度
子任务1: n <= 5
子任务2: n <= 20
子任务3: 无限制 解题报告：
不难发现长度为50的串最大可以到达的数字就是50*9 = 450 ，所以dp[i][j]代表前i个数 可以组成的和为j的方法数。然后分选和不选两种决策转移就行了。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
char s[MAX];
ll dp[55][555];//dp[i][j]代表前i个数 可以组成的和为j的方法数。
const ll mod = 1e9 + 7;
int f(char c) {
return c - '0';
}
int main()
{
//dp[0][0]=1;
cin>>(s+1);
int len = strlen(s+1);
for(int i = 1; i<=len; i++) {
// dp[i][f(s[i])] = 1;
for(int j = 0; j<555; j++) {
dp[i][j] = dp[i-1][j];
if(j == f(s[i])) dp[i][j]++;
if(j >= f(s[i])) dp[i][j] += dp[i-1][j-f(s[i])];
dp[i][j] %= mod;
}
}
//printf("**%d\n",dp[len][3]);
ll ans = 0;
for(int j = 0; j<555; j++) if(j % 3 == 0) ans = (ans + dp[len][j]) % mod;
printf("%lld\n",ans);
return 0 ;
} AC代码2：（这样写更简短一点）
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
char s[MAX];
ll dp[55][555];//dp[i][j]代表前i个数 可以组成的和为j的方法数。
const ll mod = 1e9 + 7;
int f(char c) {
return c - '0';
}
int main()
{
//dp[0][0]=1;
cin>>(s+1);
int len = strlen(s+1);
for(int i = 1; i<=len; i++) {
// dp[i][f(s[i])] = 1;
for(int j = 0; j<555; j++) {
dp[i][j] = dp[i-1][j];
if(j >= f(s[i])) dp[i][j] += dp[i-1][j-f(s[i])];
dp[i][j] %= mod;
}
dp[i][f(s[i])]++;
}
ll ans = 0;
for(int j = 0; j<555; j++) if(j % 3 == 0) ans = (ans + dp[len][j]) % mod;
printf("%lld\n",ans);
return 0 ;
} 注意到这题不能直接想当然的dp[0][0]=0，，如果是这样的话那代码就更简短了，，为什么不能这样呢？因为这题中 0 也算状态之一，所以不能这样来初始化，考虑一般写dp[0][0]的影响，无非就是加上自己的一次。所以我们虽然不写dp[0][0]=0了，但是相应的把这个状态自己加上就行了。注意AC代码2，这一句++必须放在for之后，不能放在for之前，因为不然后面for中那个等号就把这个++ 操作给覆盖了。（其实放在for之前也行，但是就得变成dp[i][j] += dp[i-1][j];了？）
同时通过观察我们发现，最后答案只跟模数有关，所以我们直接记录模数也可以。
AC代码3：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#include<cctype>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
char s[MAX];
ll dp[55][3];//dp[i][j]代表前i个数 可以组成的和为j的方法数。
const ll mod = 1e9 + 7;
int f(char c) {
return c - '0';
}
int main()
{
//dp[0][0]=1;
cin>>(s+1);
int len = strlen(s+1);
for(int i = 1; i<=len; i++) {
// dp[i][f(s[i])] = 1;
for(int j = 0; j<3; j++) {
dp[i][j] = dp[i-1][j];
dp[i][j] += dp[i-1][(j+15-f(s[i]))%3];
dp[i][j] %= mod;
}
dp[i][f(s[i])%3]++;
}
ll ans = dp[len][0];
//for(int j = 0; j<555; j++) if(j % 3 == 0) ans = (ans + dp[len][j]) % mod;
printf("%lld\n",ans%mod);
return 0 ;
}
京公网安备 11010502036488号