数位计数问题

首页 > 代码库 > 数位计数问题

2024-11-25 05:38:39 203人阅读

　　在信息学竞赛中，有一类难度不大但异常麻烦的问题——数位计数问题，这类问题的主要特点是询问的答案和一段连续的数的各个数位相关，并且需要对时间效率有一定要求。由于解决这类问题往往意味着巨大的代码量，而众多的特

殊情况又意味着出现错误的巨大可能性，因此很少有人愿意解决此类问题，但只要掌握好的方法，解决这类问题也并非想象中的那样困难------<<数位计数问题解法研究>>高逸涵。

其实数位DP或者说数位计数问题没这么难，只要构造出合适的状态，就能解决。

动态规划的核心就是在于状态的设计，如何能使重叠的自问题更多，使转移更快速？

一道简单的题：

1009 数字1的数量

基准时间限制：1 秒空间限制：131072 KB

给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。

Input

输入N(1 <= N <= 10^9)

Output

输出包含1的个数

Input示例

Output示例

这道题非常简单，相信不用数位DP都能快速解决，我们不妨用它来感受一下数位DP。

一个有效的状态：dp[i][j]表示到第i位前面一的个数是j的1个数。（这里的1个数说的是i后面的数产生完的所有1的个数）。

转移也很简单，枚举每一位。但题目给定上下界了呀，因为这个数满足，区间加减，所以只要求出（1~b的）-（1~a-1的）就可以了。

能上界怎么做。我们于是多了一位dp[i][j][k]k表示前面枚举的是不是刚好是上界。如果是只能枚举0-a[i+1]否则可以枚举0-9。

动态规划有两种实现方式，一种是有上到小带备忘的搜索，一种是由下到上的递推，

如果用递推实现的话发现有部分没有的状态和重复，并且转移实现较难，于是我们用前者。

没带备忘的搜索：

int dfs(int x,int h,int f){
    if (!x) return h;
    int N=(f)?a[x]:9,sum=0;
    for (int i=0;i<=N;i++){
        sum+=dfs(x-1,h+(i==1),f&(i==N));
    }
    return sum;
}

理解一下代码。

当然它会很慢，其实我们又发现k这一维在搜索中没必要用，因为只有没限制的数才能重复使用。

所以变成了这样：

int dfs(int x,int h,int f){
    if (!x) return h;
    if (!f && dp[x][h]!=-1) return dp[x][h];
    int N=(f)?a[x]:9,sum=0;
    for (int i=0;i<=N;i++){
        sum+=dfs(x-1,h+(i==1),f&(i==N));
    }
    if (!f) dp[x][h]=sum;
    return sum;
}

完整代码（不要慌，前面30多行头文件，请自行无视）：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 int dp[11][11],a[11];
38 int dfs(int x,int h,int f){
39     if (!x) return h;
40     if (!f && dp[x][h]!=-1) return dp[x][h];
41     int N=(f)?a[x]:9,sum=0;
42     for (int i=0;i<=N;i++){
43         sum+=dfs(x-1,h+(i==1),f&(i==N));
44     }
45     if (!f) dp[x][h]=sum;
46     return sum;
47 }
48 int solve(int x){
49     int nu=0;
50     while (x){
51         a[++nu]=x%10; x/=10;
52     }
53     return dfs(nu,0,1);
54 }
55 int main()
56 {
57     memset(dp,-1,sizeof(dp));
58     int n=read();
59     printf("%d",solve(n)); 
60     return 0;
61  }

View Code

1042 数字0-9的数量

基准时间限制：1 秒空间限制：131072 KB

给出一段区间a-b，统计这个区间内0-9出现的次数。比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。

Input

两个数a,b（1 <= a <= b <= 10^18)

Output

输出共10行，分别是0-9出现的次数

Input示例

10 19

Output示例

和上面一题类似多做几遍就可以了

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 ll dp[30][30];
38 int a[30];
39 ll dfs(int x,int l,int h,int f,int u){
40     if (!x) return h;
41     if (!f && !l && dp[x][h]!=-1) return dp[x][h];
42     int N=(f)?a[x]:9; ll sum=0;
43     sum+=dfs(x-1,l,(!l)?h+(0==u):h,f&(0==N),u);
44     for (int i=1;i<=N;i++){
45         sum+=dfs(x-1,0,h+(i==u),f&(i==N),u);
46     }
47     if (!f && !l) dp[x][h]=sum;
48     return sum;
49 }
50 ll solve(ll x,int num){
51     int nu=0;
52     while (x){
53         a[++nu]=x%10; x/=10;
54     }
55     return dfs(nu,1,0,1,num);
56 }
57 int main()
58 {
59     ll a=read(),b=read();
60     for (int i=0;i<=9;i++){
61         memset(dp,-1,sizeof(dp));
62         printf("%lld\n",solve(b,i)-solve(a-1,i)); 
63     }
64     return 0;
65  }

View Code

1043 幸运号码

基准时间限制：1 秒空间限制：131072 KB

1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。例如：99、1230、123312是幸运号码。给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。

Input

输入N(1<= N <= 1000)

Output

输出幸运号码的数量 Mod 10^9 + 7

Input示例

Output示例

这道题和前面两道不太一样，因为它没有限制，

仔细分析一下，求出每种（N个数的和）的和的个数会比较方便。

暴力找肯定太慢了，因为有很多重复的状态，于是我们有找到了动规，

dp[i][j]表示i个数和为j的方案数，dp[i][j]=dp[i-1][j-k]+dp[i][j]。（k为0-9）。

当然这是有前导零的情况，在算一算，搞一搞就做出了，（有点卡常，无耻的打了点表）

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 int ans[]={232650649,720937918,921442020,928735687,103605794,601085237,154776706,547911408,386614805,685161562};
38 ll dp[1005][10000];
39 int main()
40 {
41     int n=read();
42     if (n>990){
43         printf("%d",ans[n-991]);
44         return 0;
45     }
46     dp[0][0]=1;
47     for (int i=1;i<=n;i++)
48         for (int j=0;j<=(9*i);j++){
49             for (int k=0;k<=9;k++)
50                 if (j>=k){
51                     dp[i][j]=(dp[i-1][j-k]+dp[i][j])%pp;
52                 }
53         }
54     ll ans=0;
55     for (int i=0;i<=(9*n);i++){
56         ans=(ans+dp[n][i]*(dp[n][i]-dp[n-1][i]))%pp;
57     }
58     printf("%d",ans);
59     return 0;
60 }

View Code

1232 完美数

基准时间限制：2 秒空间限制：131072 KB

如果一个数能够被组成它的各个非0数字整除，则称它是完美数。例如：1-9都是完美数，10,11,12,101都是完美数，但是13就不是完美数（因为13不能被数字3整除）。现在给定正整数x,y，求x和y之间（包含x和y的闭区间）共有多少完美数。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数，X, Y中间用空格分割。(1 <= X <= Y <= 10^18)

Output

输出共T行，对应区间中完美数的数量。

Input示例

2
1 9
12 15

Output示例

这道题RYZ老师讲过，%%%，还考过（当时还写挂了）。

这题状态中你要记位置吧，要记非零数的lcm吧，但总不能把那个数都记下来吧，

我们又有一个发现我们只要记那个数模2520的值，2520是所有lcm的公倍数，模一个2520没事。

19*2520*2520还是要炸啊。我们存的时候还要压一压，哇lcm不是很多啊，就不足50个离散一下就行。

PS:代码我上次打的找不到了，随便拉了一份。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define rep(i,n) for(int (i)= 0;i < (n);i++)
 4 #define MS0(a) memset(a,0,sizeof(a))
 5 #define MS1(a) memset(a,-1,sizeof(a))
 6 typedef long long ll;
 7 const int MOD = 2520;
 8 ll dp[21][2520][50];
 9 int d[21],index[MOD+5];
10 void init()
11 {
12     for(int i = 1,tot = 0;i <= MOD;i++)
13         if(MOD % i == 0)  index[i] = tot++;
14     MS1(dp);
15 }
16 int lcm(int a,int b)
17 {
18     return a/__gcd(a,b)*b;
19 }
20 ll dfs(int pos,int prev,int prelcm,int edge)
21 {
22     if(pos == -1) return prev % prelcm?0:1; // ***
23     ll ans = dp[pos][prev][index[prelcm]];
24     if( !edge && ~ans) return ans;
25     ans = 0;
26     int e = edge ? d[pos]:9;
27     for(int i = 0;i <= e;i++){
28         int nowlcm = i ? lcm(prelcm,i) : prelcm;
29         int nowv = (prev * 10 + i)%MOD;
30         ans += dfs(pos - 1,nowv,nowlcm,edge && i == e);
31     }
32     if(!edge) dp[pos][prev][index[prelcm]] = ans;
33     return ans;
34 }
35 ll query(ll n)
36 {
37     MS0(d);int tot = 0;
38     while(n){
39         d[tot++] = n%10;
40         n /= 10;
41     }
42     return dfs(tot - 1,0,1,1);
43 }
44 int main()
45 {
46     init();
47     int T;
48     cin>>T;
49     while(T--){
50         ll l,r;
51         scanf("%I64d%I64d",&l,&r);
52         printf("%I64d\n",query(r) - query(l-1));
53     }
54 }

View Code

1310 Chandrima and XOR

基准时间限制：1 秒空间限制：131072 KB

有这样一个小到大排列的无穷序列S：1, 2, 4, 5, 8......，其中任何一个数转为2进制不包括2个连续的1。给出一个长度为N的正整数数组A，A1, A2......An记录的是下标（下标从1开始）。求S[A1] Xor S[A2] Xor S[A3] ..... Xor S[An]的结果（Xor 为异或运算），由于该数很大，输出Mod 1000000007的结果。

例如：A = {1, 2, 3}，对应S[1] = 1, S[2] = 2, S[3] = 4。1 Xor 2 Xor 4 = 7。

Input

第1行：1个数N，表示数组A的长度(1 <= N <= 50000)。
第2 - N + 1行：每行一个数，对应数组A的元素A[i]（1 <= A[i] <= 10^18)。

Output

输出一个数，S[A1] Xor S[A2] Xor S[A3] ..... Xor S[An]的结果Mod 1000000007。

Input示例

Output示例

这题我们的目光要放到S序列上，我们求个S在二进制下长度i位的个数是（有前导零和无前导零的都记下）可以由递推求得。sum是有前导零，dp是无前导零。（这应该比较水吧，写几个数都能写出来）。

sum[1]=1; dp[1]=1;
for (int i=2;i<N;i++){
    dp[i]=sum[i-2]+1; sum[i]=sum[i-1]+dp[i];
}

然后对于每个数在递归确定哪一位上有1（确定可以用二分）。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef unsigned long long ull;
11 typedef long double ld;
12 typedef pair<int,int> pr;
13 const double pi=acos(-1);
14 #define rep(i,a,n) for(int i=a;i<=n;i++)
15 #define per(i,n,a) for(int i=n;i>=a;i--)
16 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
17 #define clr(a) memset(a,0,sizeof(a))
18 #define pb push_back
19 #define mp make_pair
20 #define fi first
21 #define sc second
22 #define pq priority_queue
23 #define pqb priority_queue <int, vector<int>, less<int> >
24 #define pqs priority_queue <int, vector<int>, greater<int> >
25 #define vec vector
26 ld eps=1e-9;
27 ll pp=1000000007;
28 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
29 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
30 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
31 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
32 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
33 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
34 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
35 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
36 if(last==‘-‘)ans=-ans; return ans;
37 }
38 const int N=87;
39 ll sum[N],dp[N],ans[N],Ans;
40 int search(int l,int r,ll key){
41     while (l<r){
42         int mid=(l+r)>>1;
43         if (sum[mid]<key) l=mid+1;
44         else r=mid;
45     }
46     return l;
47 }
48 int main()
49 {
50     int n=read(); sum[1]=1; dp[1]=1;
51     for (int i=2;i<N;i++){
52         dp[i]=sum[i-2]+1; sum[i]=sum[i-1]+dp[i];
53     }
54     for (int i=1;i<=n;i++){
55         ll a=read(); int len=search(0,N-1,a);
56         while (len){
57             ans[len]^=1; a-=sum[len-1]+1;
58             len=search(0,len-1,a);
59         }
60     }
61     for (int i=N-1;i;i--){
62         Ans=(Ans*2+ans[i])%pp;
63     }
64     printf("%lld",Ans);
65     return 0;
66  }

View Code

1230 幸运数

基准时间限制：1 秒空间限制：131072 KB

如果一个数各个数位上的数字之和是质数，并且各个数位上的数字的平方和也是质数，则称它为幸运数。

例如：120是幸运数，因为120的数字之和为3，平方和为5，均为质数，所以120是一个幸运数字。

给定x，y，求x，y之间（包含x，y，即闭区间[x,y]）有多少个幸运数。

Input

第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10000)
第2 - T + 1行：每行2个数，X, Y中间用空格分割。(1 <= X <= Y <= 10^18)

Output

输出共T行，对应区间中幸运数的数量。

Input示例

2
1 20
120 130

Output示例

太水了吧，题解请脑补。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 const int N_2=81*19,N=9*19;
38 int f[N_2],p[N_2],a[19],nu;
39 ll dp[19][N][N_2];
40 void pre(){
41     f[0]=1; f[1]=1;
42     for (int i=2;i<=N_2;i++){
43         if (!f[i]) p[++nu]=i;
44         for (int j=1;j<=nu && i*p[j]<=N_2;j++){
45             f[i*p[j]]=1;
46             if (i%p[j]==0) break;
47         }
48     }
49 }
50 ll dfs(int x,int h,int h_2,int f_){
51     if (!x) return ((!f[h]) && (!f[h_2]))?1:0;
52     if (!f_ && dp[x][h][h_2]!=-1) return dp[x][h][h_2];
53     int M; ll sum=0;
54     if (f_) M=a[x]; else M=9;
55     for (int i=0;i<=M;i++)
56         sum+=dfs(x-1,h+i,h_2+i*i,f_&(i==M));
57     if (!f_) dp[x][h][h_2]=sum;
58     return sum;
59 }
60 ll solve(ll x){
61     int num=0;
62     while (x){
63         a[++num]=x%10; x/=10;
64     }
65     return dfs(num,0,0,1);
66 }
67 int main()
68 {
69     int T=read();
70     pre();
71     memset(dp,-1,sizeof(dp));
72     while (T--){
73         ll a=read(),b=read();
74         printf("%lld\n",solve(b)-solve(a-1));
75     }
76     return 0;
77  }

View Code

1623 完美消除

基准时间限制：1 秒空间限制：131072 KB

定义数的消除操作为选定[L，R，x]，如果数的第L到第R位上的数字都大于等于x，并且这些数都相等，那么该操作是合法的(从低位到高位编号，个位是第一位，百位是第二位……),然后将这些位数上的数减x；否则就是不合法的，不能进行操作。对一个数操作最少的次数使得这个数变成0，这个操作次数称为该数的最小操作数。如：1232的最小操作数为3，一个合法解是[2,2,1],[1,3,2],[4,4,1]。

求L~R中最小操作数为k的数的个数。

例如：132，需要操作3次才能变为0。而131131 => 111131 => 111111 =>0

Input

单组测试数据。
三个整数L、R和k(1<=L<=R<=10^18,1<=k<=18)。

Output

一个整数表示答案。

Input示例

10 21 2

Output示例

这题你要想想一个数字造成贡献的情况，在记下你需要的情况即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<cstdlib>
 7 #include<vector>
 8 using namespace std;
 9 typedef long long ll;
10 typedef long double ld;
11 typedef pair<int,int> pr;
12 const double pi=acos(-1);
13 #define rep(i,a,n) for(int i=a;i<=n;i++)
14 #define per(i,n,a) for(int i=n;i>=a;i--)
15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])
16 #define clr(a) memset(a,0,sizeof(a))
17 #define pb push_back
18 #define mp make_pair
19 #define fi first
20 #define sc second
21 #define pq priority_queue
22 #define pqb priority_queue <int, vector<int>, less<int> >
23 #define pqs priority_queue <int, vector<int>, greater<int> >
24 #define vec vector
25 ld eps=1e-9;
26 ll pp=1000000007;
27 ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
28 ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
30 //void add(int x,int y,int z){ v[++e]=y; next[e]=head[x]; head[x]=e; cost[e]=z; }
31 int dx[5]={0,-1,1,0,0},dy[5]={0,0,0,-1,1};
32 ll read(){ ll ans=0; char last=‘ ‘,ch=getchar();
33 while(ch<‘0‘ || ch>‘9‘)last=ch,ch=getchar();
34 while(ch>=‘0‘ && ch<=‘9‘)ans=ans*10+ch-‘0‘,ch=getchar();
35 if(last==‘-‘)ans=-ans; return ans;
36 }
37 int a[20];
38 ll dp[20][2000][30];
39 ll dfs(int x,int s,int h,int k,int f){
40     if (!x) return (h==k)?1:0;
41     if (!f && dp[x][s][h]!=-1) return dp[x][s][h];
42     int N=(f)?a[x]:9; ll sum=dfs(x-1,0,h,k,f&(0==N)); int s_=0;
43     for (int i=1;i<=N;i++){
44         s_+=s&(1<<i);
45         sum+=dfs(x-1,s_|(1<<i),h+((s&(1<<i))==0),k,f&(i==N));
46     }
47     if (!f) dp[x][s][h]=sum;
48     return sum;
49 }
50 ll solve(ll x,int k){
51     int num=0;
52     while (x){
53         a[++num]=x%10; x/=10;
54     }
55     return dfs(num,0,0,k,1);
56 }
57 int main()
58 {
59     memset(dp,-1,sizeof(dp));
60     ll l=read(),r=read(),k=read();
61     printf("%lld",solve(r,k)-solve(l-1,k)); 
62     return 0;
63  }

View Code

数位计数问题

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 数位计数问题