P4349 [CERC2015]Digit Division 思维题 数论

题意：

有一个(N)位的数字，将其分割，保证每个区间里的数字可以被(M)整除,输出方案数，答案对(10^9+7)取模

范围&性质：(1le Nle 3 imes10^5,1le Mle 10^6)

分析：

第一眼(O(n^2))DP，一看数据范围，放弃。思考怎么优化，我们发现对于DP来说，每一个点都是由之前能够断开的地方转移而来，那么影响答案的只有可划分的间隔，所以(O(n))的扫一遍记录能够断开的区间个数，且两个断点之间的区间一定能被(M)整除，最后只需要判断一下最后一段区间能否被(M)整除，若可以，那么答案就是$ 2^{断点个数} $

代码：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	const int mod = 1e9+7;
	const int maxn = 3e5+5;
	char ch[maxn];
	int n,m,cnt=0,tmp=0;
	
	long long qpow(int x,int y)
	{
		long long res=1;
		while(y)
		{
			if(y&1) res=res*x%mod;
			x=(long long)x*x%mod;
			y>>=1;
		}
		return res;
	}
	
	void work()
	{
		scanf("%d%d",&n,&m);
		scanf("%s",ch+1);
		for(int i=1;i<n;i++)
		{
			tmp=(tmp*10+ch[i]-'0')%m;
			if(!tmp)
			{
				cnt++;
			}
		}
		tmp=(tmp*10+ch[n]-'0')%m;
		if(tmp)
		{
			printf("0
");
			return ;
		}
		else printf("%lld",qpow(2,cnt));
	}
	
}

int main()
{
	zzc::work();
	return 0;
 }