Description
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.
Input
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.
Output
Print the number of ways Rocket323 can choose some consecutive digits to form a number which multiples of 64.
Sample Input
64064
Sample Output
5
Hint
There are five
substrings which multiples of 64.
[64]064
640[64]
64[0]64
[64064]
[640]64
这里提供两种思路，一种是对于64取模总共就64种状态，那么只要开一个64的数组每次递推记录下从第i位(i<=j)到第j位的数字对于64取模的答案即可。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=3e5+10;
LL f[2][65],ans;
int flag;
char s[maxn];
int main()
{
while (~scanf("%s",s))
{
int now=ans=0;
for (int i=0;i<64;i++) f[0][i]=f[1][i]=0;
for (int i=flag=0;s[i];i++,now^=1)
{
int k=s[i]-'0';
for (int j=0;j<64;j++) f[now^1][j]=0;
for (int j=0;j<64;j++) f[now^1][(j*10+k)%64]+=f[now][j];
if (k) f[now^1][k]++; else flag++;
ans+=f[now^1][0];
}
printf("%lld\n",ans+flag);
}
return 0;
}
另一种想法是64是2^6，也就是说10^6对于64取模为0，那么每次保存6位对于64取模的答案，然后统计之前的0的个数减掉就好了。
#include<cstdio>
#include<string>
#include<cstring>
#include<vector>
#include<iostream>
#include<queue>
#include<map>
#include<bitset>
#include<algorithm>
using namespace std;
typedef long long LL;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 3e5 + 10;
int a[maxn] = { 100000, 10000, 1000, 100, 10, 1 };
int cnt[maxn];
char s[maxn];
int main()
{
while (scanf("%s", s) != EOF)
{
LL ans = 0, now = cnt[0] = 0;
for (int i = 0; s[i]; i++)
{
if (s[i] == '0') cnt[i] = cnt[max(0, i - 1)] + 1; else cnt[i] = cnt[max(0, i - 1)];
now = (now * 10 + s[i] - '0') % 1000000;
if (now % 64 == 0 && i >= 6) ans += i - 6 + 1 - cnt[i - 6];
for (int j = 0, k = now; j < 6; j++)
{
if (!(k / a[j])) continue;
if (k % 64 == 0) ans++; k %= a[j];
}
}
printf("%lld\n", ans + cnt[strlen(s) - 1]);
}
return 0;
}