Digit Division
Time limit: 1 s Memory limit: 512 MiB
We are given a sequence of n decimal digits. The sequence needs to be partitioned into one or more contiguous subsequences such that each subsequence, when interpreted as a decimal number, is divisible by a given integer m.
Find the number of different such partitions modulo 109 + 7. When determining if two partitions are different, we only consider the locations of subsequence boundaries rather than the digits themselves, e.g. partitions 2|22 and 22|2 are considered different.
Input
The first line contains two integers n and m (1 ≤ n ≤ 300 000, 1 ≤ m ≤ 1 000 000) – the length of the sequence and the divisor respectively. The second line contains a string consisting of exactly n digits.
Output
Output a single integer – the number of different partitions modulo 109 + 7.
Example
input
4 2
1246
output
4
input
4 7
2015
output
0
//题意: n 位长的十进制数字，在其中可以任意插入分割线，分割后，要使每一段不为空，并且可以整除 m ，合法分割的方案数
//题目是极其简单的，如果前一部分可以整除 m ，那么，这部分乘10的x次方后依然可以整除，然后算出所有可分割的位置后
C(0,all),C(1,all)+...+C(all,all); 这些必然合法
= 2^all
但是，此题如果没想清楚，写代码会进坑，此题是对方案数取模，all 是%m==0的方案数，进了坑半天想不出来，唉，还是太菜啊，一度wa在第三组，真是日狗了
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <sstream>
# include <set>
# include <cmath>
# include <algorithm>
# pragma comment(linker,"/STACK:102400000,102400000")
using namespace std;
# define LL long long
# define pr pair
# define mkp make_pair
# define lowbit(x) ((x)&(-x))
# define PI acos(-1.0)
# define INF 0x3f3f3f3f
# define eps 1e-
# define MOD inline int scan() {
int x=,f=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-; ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
}
inline void Out(int a) {
if(a<) {putchar('-'); a=-a;}
if(a>=) Out(a/);
putchar(a%+'');
}
# define MX
/**************************/
char num[MX]; LL qk_mi(LL base,LL x)
{
LL res = ;
while (x)
{
if (x%==) res = (res*base)%MOD;
base=base*base%MOD;
x/=;
}
return res;
} int main()
{
int n,m;
while (scanf("%d%d",&n,&m)!=EOF)
{
scanf("%s",num);
LL zuo = ;
LL all = ;
for (int i=;i<n;i++)
{
zuo=(zuo*+(num[i]-''))%m;
if (zuo%m==) all++;
}
all--;
if (zuo%m!=)
printf("0\n");
else
{
LL ans = qk_mi(,all);
printf("%lld\n",ans);
}
}
return ;
}