20241024比赛总结

T1 数位

设\(dp_{i,0/1}\)表示前i位，最后一段是/不是d倍数的方案数

令\(d=2^x 5^y m\)

可以将模d同余转化为模\(2^x\)，\(5^y\),\(m\)分别同余

因为\(2^{20}=1048576>10^6\) 所以，当\(j<=i-20\)时，前两项的结果均为0

所以首先可以开两个前缀和，求sum[i-1]*10+s[i]-'0'对前两项的取模结果，不为0则直接跳过

接下来考虑m，记\(pre_i=pre_{i-1}+s_i*10^{n-i}\)，则合法必然满足\((pre_i-pre_j)/10^{i-j}\equiv 0(\bmod m)\)

因为\(m\)和10互质，所以\(pre_i-pre_j=0\),可以按照\(pre_i\)的值开桶，记录每个值的\(dp_{i,0}\)之和

\(j>i-20\)部分按第一档部分分的方法解决即可

代码：

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int T,d,p[100005],sum[100005],dp[100005][2],p1[100005];
int sum1[100005],sum2[100005],sum3[100005],n;
int pre[1000005][2],cnt;
string s;
int main()
{
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>s>>d;
		n=s.size();
		s=" "+s;
		p[0]=p1[0]=1;
		for(int i=1;i<=n;i++)
		{
			p[i]=p[i-1]*10%d;
		}
		int cnt2=1,cnt5=1,x=d;
		while(x%2==0) x/=2,cnt2*=2;
		while(x%5==0) x/=5,cnt5*=5;
		for(int i=1;i<=n;i++)
		{
			p1[i]=p1[i-1]*10%x;
		}
		for(int i=1;i<=n;i++)
		{
			sum[i]=(sum[i-1]*10+s[i]-'0')%d;
			sum3[i]=(sum3[i-1]+(s[i]-'0')*p1[n-i])%x;
			sum1[i]=(sum1[i-1]*10+(s[i]-'0'))%cnt2;
			sum2[i]=(sum2[i-1]*10+(s[i]-'0'))%cnt5;
		//	printf("%d %d %d %d\n",sum[i],sum1[i],sum2[i],sum3[i]);
		}
		dp[0][0]=1,cnt=0;
		for(int i=1;i<=n;i++)
		{
			if(i>=20)
			{
				pre[sum3[i-20]][0]=(pre[sum3[i-20]][0]+dp[i-20][0])%mod;
				pre[sum3[i-20]][1]=(pre[sum3[i-20]][1]+dp[i-20][1])%mod;
				cnt=(cnt+dp[i-20][0])%mod;
			}
			if(sum1[i]!=0||sum2[i]!=0)
			{
				dp[i][1]=cnt,dp[i][0]=0;
			}
			else
			{
				dp[i][1]=(cnt-pre[sum3[i]][0]+mod)%mod;
				dp[i][0]=(pre[sum3[i]][0]+pre[sum3[i]][1])%mod;
			//	printf("%d %d %d\n",cnt,pre[sum3[i]][0],pre[sum3[i]][1]);
			}
			for(int j=max(0,i-19);j<i;j++)
			{
				int x=sum[i]-1ll*sum[j]*p[i-j]%d;
				if(x==0) dp[i][0]=(1ll*dp[i][0]+dp[j][0]+dp[j][1])%mod;
				else dp[i][1]=(1ll*dp[i][1]+dp[j][0])%mod;
			}
		//	printf("%d %d\n",dp[i][0],dp[i][1]);
		}
		for(int i=0;i<=n;i++) pre[sum3[i]][1]=pre[sum3[i]][0]=0;
		cout<<(dp[n][1]+dp[n][0])%mod<<"\n";
	}
	return 0;
}