Codeforces 628D 数位dp

时间:2021-11-14 20:37:33

题意:d magic number(0<=d<9)的意思就是一个数,从最高位开始奇数位不是d,偶数位是d

题目问,给a,b,m,d(a<=b,m<2000)问,a,b之间有多少个数满足既是d magic number,又可以被m整除

a,b的范围很大,都是2000位,且a,b的位数一样,这一点很重要

分析:这题一看又有取模,又是大整数,那肯定是要用数位dp做,

通常的数位dp,我们要解决(0,x)的区间中的答案,但是这个题不需要,

注意刚才我说过一点,a,b是位数相同的整数,假设solve()函数能解决x到和它同位的最小整数的区间范围内的答案

那么最终答案,就是solve(b)-solve(a)+is(a),

这样我们的工作就简单了,不需要统计位数比它小的数

我们从高位开始进行dp

下面定义状态

1: dp[i][j][1],代表现在处理到第 i 位 且前缀 i 位形成的整数n%m=j 的 方案数,且现在形成的整数等于上限

2: dp[i][j][0],代表现在处理到第 i 位 且前缀 i 位形成的整数n%m=j 的 方案数,且现在形成的整数小于上限

那么状态转移方程就很好想了

设字符串长度为n  那么时间复杂度是O(nm)的

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 2e3+;
const int mod = 1e9+;
int dp[N][N][],num[N],m,d;
char a[N],b[N];
int solve(char *s)
{
int l=strlen(s+);
memset(dp,,sizeof(dp));
for(int i=; i<=l; ++i)
num[i]=s[i]-'';
for(int i=; i<=; ++i)
{
if(i==d)continue;
if(i<num[])++dp[][i%m][];
else if(i==num[])++dp[][i%m][];
}
for(int i=; i<=l; ++i)
{
if(i%==)
{
for(int j=; j<m; ++j)
{
int cur=(j*+d)%m;
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
if(d<num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
else if(num[i]==d)
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
}
}
else
{
for(int k=; k<; ++k)
{
if(k==d)continue;
for(int j=; j<m; ++j)
{
int cur=(j*+k)%m;
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
if(k<num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
else if(k==num[i])
dp[i][cur][]=(dp[i][cur][]+dp[i-][j][])%mod;
}
}
}
}
return (dp[l][][]+dp[l][][])%mod;
}
int judge(char *s)
{
int l=strlen(s+),sum=;
for(int i=;i<=l;++i)
{
int x=s[i]-'';
if(i%&&x==d)return ;
if(!(i%)&&x!=d)return ;
sum=(sum*+x)%m;
}
if(!sum)return ;
return ;
}
int main()
{
scanf("%d%d%s%s",&m,&d,a+,b+);
int ans=(solve(b)-solve(a)+judge(a)+mod)%mod;
printf("%d\n",ans);
return ;
}