数位dp
- 求 $ [X,Y] $ 满足的数,则 $ f(Y)-f(X-1) $
- 用树的方式考虑(迭代写法)
- 时间复杂度：定义的状态数*10(10为枚举0-9)
- pos: 当前数位
- limit: 为
true为从0-nums[pos],为false为从0-9 - last: 上一位,往往出现于数位之间有关联的
- lead: 前导零
有前导零的情况？- 统计0的出现次数
- 相邻数字的差值
- 以最高位为起点确定的奇偶位
- r: 表示整个数前缀取模某个数
m的余数- 该参数一般会用在：约束中出现了能被整除
- 当然也可以拓展为数位和取模的结果
- st: 用于状态压缩对一个集合的数在数位上的出现次数的奇偶性有要求时，其二进制形式就可以表示每个数出现的奇偶性
cpp
//求区间内0-9的出现次数
int f[20][20];
vector<int> nums;
int dfs(int pos,int sum,int d,bool limit,bool lead){
if(!pos)return sum;
if(!limit&&!lead&&~f[pos][sum])return f[pos][sum];
int up=limit?nums[pos-1]:9;
int ans=0;
for(int i=0;i<=up;i++){
if(lead)ans+=dfs(pos-1,sum+(i==d&&d),d,limit&&i==up,lead&&i==0);
else ans+=dfs(pos-1,sum+(i==d),d,limit&&i==up,0);
}
if(!limit&&!lead)f[pos][sum]=ans;
return ans;
}
int dp(int n,int d){
nums.clear();
memset(f,-1,sizeof f);
while(n)nums.push_back(n%10),n/=10;
return dfs(nums.size(),0,d,1,1);
}
void solve(){
int l,r;
cin>>l>>r;
for(int i=0;i<=9;i++){
cout<<dp(r,i)-dp(l-1,i)<<" ";
}
}cpp
//给m,d,l,r四个数
//找出x满足以下条件：
//l<=x<=r
//x的偶数位是d，奇数位是d
//m|x
//1<=l,r<=10^2000 1<=m<=2000
//l,r范围很大，需要用字符串读入，此时使用l-1可能会产生退位(要写高精减),因此减去dp(l)然后单独判断l即可
```cpp
int f[2010][2010],m,d;
vector<int> nums;
int MOD(int x,int y=mod){
return (x%y+y)%y;
}
int dfs(int pos,int sum,bool limit){
if(!pos)return sum==0;
if(!limit&&~f[pos][sum])return f[pos][sum];
int up=limit?nums[pos-1]:9;
int res=0;
bool g=(nums.size()-pos+1)&1;
for(int i=0;i<=up;i++){
if(g){
if(i==d)continue;
res=MOD(dfs(pos-1,(sum*10%m+i)%m,limit&&i==up)+res);
}
else{
if(i!=d)continue;
res=MOD(dfs(pos-1,(sum*10%m+i)%m,limit&&i==up)+res);
}
}
if(!limit)f[pos][sum]=res;
return res;
}
int dp(string n){
nums.clear();
memset(f,-1,sizeof f);
for(auto c:n)nums.push_back(c-'0');
reverse(nums.begin(),nums.end());
return dfs(nums.size(),0,1);
}
bool check(string n){
int sum=0;
for(int i=0;i<n.size();i++){
if(i%2==1&&n[i]-'0'!=d)return false;
if(i%2==0&&n[i]-'0'==d)return false;
sum=((sum*10)%m+n[i]-'0')%m;
}
return sum==0;
}
void solve(){
cin>>m>>d;
string l,r;
cin>>l>>r;
cout<<MOD(MOD(dp(r)-dp(l))+check(l))<<"\n";
}