ZZNUOJ2141:2333求子串是3的倍数的子串个数(前缀和+规律(On)防T)

题目链接&＃xff1a;http://47.93.249.116/problem.php?id&＃61;2141

题意是给你给一个数字串&＃xff0c;问该数字串有多少个连续子串能整除3

因为能被3整除的数字串的和一定是3的倍数&＃xff0c;一开始的思路是记录前缀和&＃xff0c;再对每一个前缀和遍历之后的前缀和用后面的前缀和减去前面的前缀和如果差值为3的倍数则ans&＃43;&＃43;
但是时间复杂度为O(n^2)&＃xff0c;而n<&＃61;1e6&＃xff0c;肯定会T&＃xff0c;这道题的正确思路是

思考&＃xff1a;这个规律要记住&＃xff0c;如果问数字串有多少个连续子串是k的倍数&＃xff0c;该方法直接套用时间复杂度O(n)

#include
#include
#include
#include
#include
#include
#include
using namespace std;int main()
{char str[1000005];while(scanf("%s",str)!&＃61;EOF){long long sum[3]&＃61;{0};int s&＃61;0;int n&＃61;strlen(str);for(int i&＃61;0;i&＃39;0&＃39;;s%&＃61;3;sum[s]&＃43;&＃43;;//统计0, 1, 2个数}long long ans;//求组合数ans&＃61;(sum[0]&＃43;1)*sum[0]/2&＃43;sum[1]*(sum[1]-1)/2&＃43;sum[2]*(sum[2]-1)/2;printf("%lld\n",ans);}return 0;
}