自动搬运

查看原文

来自洛谷，原作者为

	Genius_Star 跟你爆了

搬运于2025-08-24 21:59:15，当前版本为作者最后更新于2024-02-01 11:18:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

简单题，考虑找到可以分割的点的个数 $x$，每一个点可以选择分割或者不分割，总方案数为 $2^x$。（运用快速幂）

注意到，每个区间都被 $m$ 整除，则选几个区间合并起来也能被 $m$ 整除，于是可以从左到右扫一遍，如果当前 $1 \sim i$ 的数字能被 $m$ 整除，则该点可以作为分割点。

但是如果最后一个点是分割点的话，分割或者不分割是一样的，所以不算这个答案；无解的话是整个数字都不被 $m$ 整除的情况。

时间复杂度为 $O(N + \log{p})$。

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=300300,mod=1e9+7; 
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,m,sum,ans;
char c;
ll qpow(ll sum,ll b){
	ll ans=1;
	while(b){
		if(b&1ll)
		  ans=(ans*sum)%mod;
		sum=(sum*sum)%mod;
		b>>=1ll;
	}
	return ans;
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
		scanf("%c",&c);
		sum=(sum*10%m+c-'0')%m;
		if(!sum)
		  ans++;
	}
	write(sum?0:qpow(2ll,ans-1));
	return 0;
}