网站规划与建设进度,广州做网站的网络公司,海口专业网站搭建厂,wordpress重定向seo题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/1080/E 来源#xff1a;牛客网
tokitsukaze有一个长度为n的字符串#xff0c;字符串仅包含0-9。 tokitsukaze要把这个字符串切割成若干个子串#xff0c;每个子串作为一个十进制的数#xff0c;…题干
链接https://ac.nowcoder.com/acm/contest/1080/E 来源牛客网
tokitsukaze有一个长度为n的字符串字符串仅包含0-9。 tokitsukaze要把这个字符串切割成若干个子串每个子串作为一个十进制的数能被3整除且不含前导0。 问有多少种切割的方案。由于答案可能很大请输出mod 998244353 后的结果。
输入描述:
第一行包含一个正整数n,(1≤n≤10^5)。
第二行包含一个长度为n的字符串s,(0≤s[i]≤9)。
输出描述:
输出一个整数表示方案数mod 998244353 后的结果。
示例1
输入
复制
1
1输出
复制
0示例2
输入
复制
1
0输出
复制
1示例3
输入
复制
4
1203输出
复制
3说明
(1) 1203
(2) 120|3
(3) 12|0|3
所以方案数为3。
注意12|03视作不合法因为有前导0。解题报告 看似一个dp题其实直接递推就可以了。其实如果数字中没有0的话直接一个变量就可以了。但是这题有零所以需要开两个变量。
先来一个TLE代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
const ll mod 998244353;
char s[MAX];
ll dp[MAX];
int cur,tmp,n;
int main()
{cinn;cin(s1);for(int i 1; in; i) s[i] - 0;dp[0] 1;for(int i 1; in; i) {cur (curs[i])%3;tmp cur;for(int j i; j1; j--) {tmp (tmp9-s[j])%3;if(!tmp cur tmp (s[j]!0 || ji)) dp[i] (dp[i] dp[j-1]) % mod;}}ll ans 0;printf(%lld\n,dp[n]%mod);return 0 ;
}
可以发现可以化简成这样来自题解
for(int i1;in;i) dp[i]0;
dp[0]1;
for(int i1;in;i)
{suf0;for(int ji;j;j--){suf(sufs[j]-0)%3;if(s[j]0ji) continue;if(!suf) (dp[i]dp[j-1])%mod;}
}
也就是说特点就是要找前缀数字和是0的方案数然后累加一下就行了。但是因为有前导0所以要开两个变量分别记录。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
const ll mod 998244353;
char s[MAX];
ll dp,sum;
int cur,tmp,n;
int main()
{cinn;cin(s1);sum 1;for(int i 1; in; i) s[i] - 0;for(int i 1; in; i) {cur (curs[i])%3;if(cur 0) {if(s[i] 0) sum (sumdp)%mod;else sum dp (sumdp)%mod;}}if(cur 0) printf(%lld\n,sum);else printf(0\n);return 0 ;
}
