数位DP（记忆化搜索写法）

写法）"/>

数位DP（记忆化搜索写法）

题目链接

写记忆化搜索写的太少了，就很容易写错，一般记忆化搜索的函数参数是当前的位置和前面搜索的状态。这题里n>=2其实不用管，因为题目给出的l是大于10的，前导零也不需要考虑。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=210,mod=998244353;
int f[N][9*N][2];
vector<int>v;
//当前在第u位，位的总和为sum，是否和上界相等
LL dfs(int u,int sum,bool flag)
{int& res=f[u][sum][flag];if(!flag&&res!=-1) return res;int up=flag?v[u]:9;res=0;if(u==1){for(int i=1;i<=up;i++)if(sum%i==0) res=(res+1)%mod;return res;}for(int i=0;i<=up;i++)res=((LL)res+dfs(u-1,sum+i,flag&&(i==v[u])))%mod;return res;
}
LL get(string x)
{v.clear();memset(f,-1,sizeof f);v.push_back(0);for(int i=x.size()-1;i>=0;i--)v.push_back(x[i]-'0');return dfs(x.size(),0,1);
}
int main()
{string l,r;cin>>l>>r;LL res=(get(r)-get(l))%mod;int x=v[1],s=0;for(int i=2;i<v.size();i++) s+=v[i];if(l.size()>=2&&x!=0&&s%x==0) res++;res=(res+mod)%mod;cout<<res<<endl;return 0;
}