1599 - Multiple
时间限制:2秒 内存限制:64兆 461 次提交 111 次通过 题目描述 Rocket323 loves math very much. One day, Rocket323 got a number string. He could choose some consecutive digits from the string to form a number. Rocket323 loves 64 very much, so he wanted to know how many ways can he choose from the string so the number he got multiples of 64 ?
A number cannot have leading zeros. For example, 0, 64, 6464, 128 are numbers which multiple of 64 , but 12, 064, 00, 1234 are not. 输入 Multiple cases, in each test cases there is only one line consist a number string. Length of the string is less than 3 * 10^5 .
Huge Input , scanf is recommended. 输出 Print the number of ways Rocket323 can choose some consecutive digits to form a number which multiples of 64. 样例输入 64064 样例输出 5 提示 There are five substrings which multiples of 64. [64]064 640[64] 64[0]64 [64064] [640]64 来源 Problem Setter : Yang Xiao
思路: 根据同余定理,每次枚举到一个数,都把前面的存在的余数乘以10加上这个数再对64取余,就产生新的余数,最后统计余数是0的个数有多少
#include <iostream>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
char a[300005];
long long int dp[2][65];
long long int tag[65];
long long int ans;
long long int res;
int now;
int main()
{
while(scanf("%s",a)!=EOF)
{
ans=0;res=0;
int len=strlen(a);
memset(dp,0,sizeof(dp));
now=0;
for(int i=0;i<len;i++)
{
for(int j=63;j>=0;j--)
dp[now^1][j]=0;
for(int j=63;j>=0;j--)
{
int num=(j*10+a[i]-'0'+64)%64;
dp[now^1][num]+=dp[now][j];
}
if(a[i]!='0')
dp[now^1][a[i]-'0']++;
else
ans++;
res+=dp[now^1][0];
now^=1;
}
printf("%lld\n",res+ans);
}
return 0;
}