邢台网站建设网络公司,海珠建设网站,重庆企业黄页大全电话,网站备案后会被注销吗题解#xff1a; 考虑数位DP,状压出现过的数字集合S#xff0c;f ( l , x , S , pz , lim )表示到第 l 位#xff0c;数字为x#xff0c; 数字集合为S #xff0c;是否为前导0#xff0c;是否贴上界 然后同时定义g为该状态下的数字和#xff0c;利用 10^(l-1) * f(l , x…题解 考虑数位DP,状压出现过的数字集合Sf ( l , x , S , pz , lim )表示到第 l 位数字为x 数字集合为S 是否为前导0是否贴上界 然后同时定义g为该状态下的数字和利用 10^(l-1) * f(l , x, S, pz, lim)计算该位的贡献然后加上所有后继的g就行了 1 #includebits/stdc.h2 #define ll long long3 using namespace std;4 const ll mod 998244353;5 ll l,r;6 int k;7 int num[22],cnt;8 ll f[22][10][1050][2][2],g[22][10][1050][2][2];9 bool vis[22][10][1050][2][2];
10 ll fastpow(ll a,ll p)
11 {
12 ll ans1;
13 while(p)
14 {
15 if(p1)ansans*a%mod;
16 aa*a%mod;p1;
17 }
18 return ans;
19 }
20 void dfs(int l,int x,int S,bool pz,bool lim)
21 {
22 if(vis[l][x][S][pz][lim])return;
23 vis[l][x][S][pz][lim]1;
24 int t0;
25 for(int i0;i10;i)if(S(1i))t;
26 if(tk)return;
27 if(l1)
28 {
29 f[l][x][S][pz][lim]1,g[l][x][S][pz][lim]x;
30 return;
31 }
32 int up(lim)?num[l-1]:9;
33 for(int i0;iup;i)
34 {
35 dfs(l-1,i,(pz(!i))?0:(S|(1i)),pz(!i),lim(inum[l-1]));
36 f[l][x][S][pz][lim](f[l][x][S][pz][lim]f[l-1][i][(pz(!i))?0:(S|(1i))][pz(!i)][lim(inum[l-1])])%mod;
37 g[l][x][S][pz][lim](g[l][x][S][pz][lim]g[l-1][i][(pz(!i))?0:(S|(1i))][pz(!i)][lim(inum[l-1])])%mod;
38 }
39 g[l][x][S][pz][lim](g[l][x][S][pz][lim]f[l][x][S][pz][lim]*x%mod*fastpow(10,l-1)%mod)%mod;
40 }
41 ll solve(ll n)
42 {
43 if(!n)return 0;
44 memset(num,0,sizeof(num));
45 memset(f,0,sizeof(f));
46 memset(g,0,sizeof(g));
47 memset(vis,0,sizeof(vis));
48 cnt0;
49 ll xn;
50 while(x)
51 {
52 num[cnt]x%10;
53 x/10;
54 }
55 ll ans0;
56 for(int i0;inum[cnt];i)
57 {
58 dfs(cnt,i,(i0)?0:(1i),(i0),(inum[cnt]));
59 ans(ansg[cnt][i][(i0)?0:(1i)][(i0)][(inum[cnt])])%mod;
60 }
61 return ans;
62 }
63 int main()
64 {
65 scanf(%I64d%I64d%d,l,r,k);
66 printf(%I64d\n,(solve(r)-solve(l-1)mod)%mod);
67 return 0;
68 } View Code 转载于:https://www.cnblogs.com/uuzlove/p/10612406.html
