「kuangbin带你飞」专题十五 数位DP

Diposting di | Edited on

传送门

A.CodeForces - 55D Beautiful numbers

题意

一个正整数是 漂亮数 ，当且仅当它能够被自身的各非零数字整除。我们不必与之争辩，只需计算给定范围中有多少个漂亮数。

思路

因为问你的是一段区间内有多少数能整除他的所有非零数位

1-9，1，一定能被任何正整数整除，1-9的最小公倍数为2520

而1-2520中真正是1-9中的最小公倍数的只有48个

dp i j k:因为dp25,2520,[2520]开不下，所以我们要进行适当离散化

index[]数组标记1-2520，哪些是真正的最小公倍数，是第几个

所以dp[i][j][k]:长度为i的数，该数对2520取模为j，它的数位和的最小公倍数是第k个->index[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const int mod=2520;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){if(b==0)return a;else return gcd(b,a%b);}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int islcm[mod+10];
int num[200];
ll dp[200][2550][50];
void init(){
    int num=0;
    for(int i=1;i<=2520;i++){
        if(2520%i==0)islcm[i]=++num;
    }
}
ll dfs(int pos,int nownum,int nowlcm,bool limit){
    if(pos==-1)return nownum%nowlcm==0;
    if(!limit&&dp[pos][nownum][islcm[nowlcm]]!=-1)return dp[pos][nownum][islcm[nowlcm]];
    int up=limit?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        int nowsum=(nownum*10+i)%mod;
        int nowl=nowlcm;
        if(i)nowl=lcm(nowl,i);
        ans+=dfs(pos-1,nowsum,nowl,limit&&i==num[pos]);
    }
    if(!limit)dp[pos][nownum][islcm[nowlcm]]=ans;
    return ans;
}
ll ac(ll x){
    ll pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,1,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    init();
    int t;
    cin>>t;
    while(t--){
        ll n,m;
        cin>>n>>m;
        cout<<ac(m)-ac(n-1)<<endl;
    }
    return 0;
}

B.HDU - 4352 XHXJ’s LIS

题意

问你一个longlong范围内（a,b）中每一位的数字组成的最长严格递增子序列（LIS）长度为K的个数

题意

首先 关系到数字和位数 数位DP

然后LIS 最长递增子序列利用二分查找当前递增子序列中是否有大于它的数，如果有替换最小的哪一个,如果没有就加入长度+1;可以利用状态压缩保存当前的最长递增子序列的类型;因为数字最多十个所以类型最多长度为10,用二进制的1表示当前位数的这个数在最长递增子序列中;

然后注意前导0的处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int k;
int num[21];
ll dp[21][1<<11][11];
int numcnt(int x){
    int cnt=0;
    for(int i=0;i<10;i++){
        if(x&(1<<i))cnt++;
    }
    return cnt;
}
int numchange(int x,int p){
    for(int i=p;i<=9;i++){
        if(x&(1<<i))return (x^(1<<i))|(1<<p);
    }
    return x|(1<<p);
}
ll dfs(int pos,int nownum,bool limit,bool zero){
    if(pos==-1)return numcnt(nownum)==k;
    if(!limit&&dp[pos][nownum][k]!=-1)return dp[pos][nownum][k];
    int up=limit?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,(zero&&i==0)?0:numchange(nownum,i),limit&&i==num[pos],zero&&i==0);
    }
    if(!limit)dp[pos][nownum][k]=ans;
    return ans;
}
ll ac(ll x){
    ll pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    ll a,b;
    int cnt=0;
    while(t--){
        cin>>a>>b>>k;
        cout<<"Case #"<<++cnt<<": "<<ac(b)-ac(a-1)<<endl;
    }
    return 0;
}

C.HDU - 2089 不要62

题意

中文题

思路

数位DP模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int num[20];
int dp[20][2];
int dfs(int pos,int pre,int sta,bool first){
    if(pos==-1)return 1;
    if(!first&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=first?num[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++){
        if(pre==6&&i==2)continue;
        if(i==4)continue;
        ans+=dfs(pos-1,i,i==6,first&&i==num[pos]);
    }
    if(!first)dp[pos][sta]=ans;
    return ans;
}
int ac(int x){
    int pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n,m;
    memset(dp,-1,sizeof(dp));
    while(cin>>n>>m&&(n&&m)){
        cout<<ac(m)-ac(n-1)<<endl;
    }
    return 0;
}

D.HDU - 3555 Bomb

题意

求1-n中出现49的数的个数，不要62的反例

思路1

不要62的反解 注意ac(n)算的是0-n之前的数其中包括了0 因为多减去了一个0所以结果要再加上0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int num[50];
ll dp[50][2];
ll dfs(int pos,int pre,int sta,bool first){
    if(pos==-1)return 1;
    if(!first&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=first?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(pre==4&&i==9)continue;
        ans+=dfs(pos-1,i,i==4,first&&i==num[pos]);
    }
    if(!first)dp[pos][sta]=ans;
    return ans;
}
ll ac(ll x){
    int pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    ll n;
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<n-ac(n)+1<<endl;
    }
    return 0;
}

思路2

正着做 DP[第几个数]//[这个数这个位是不是4]///[这个数前面存不存在49]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int num[200];
ll dp[200][2][2];
ll dfs(int pos,int pre,int sta,bool first,bool ok){
    if(pos==-1){
        if(ok)return 1;
        else
            return 0;
    }
    if(!first&&dp[pos][sta][ok]!=-1)return dp[pos][sta][ok];
    int up=first?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,i,i==4,first&&i==num[pos],pre==4&&i==9||ok);
    }
    if(!first)dp[pos][sta][ok]=ans;
    return ans;
}
ll ac(ll x){
    ll pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,-1,0,true,false);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<ac(n)<<endl;
    }
    return 0;
}

E.POJ - 3252 Round Numbers

题意

求L到R中二进制里面0的数量大于等于1的数量的个数

思路

二进制的数位DP,但是注意这个有关前导0,如果有前导零的话遇到0就不能加上0的数量；

dp【第几位】【0的数量】【1的数量】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int num[200];
ll dp[200][200][200];
ll dfs(int pos,int num0,int num1,bool limit,bool zero){
    if(pos==-1)return num0>=num1;
    if(!limit&&dp[pos][num0][num1]!=-1)return dp[pos][num0][num1];
    int up=limit?num[pos]:1;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(i)ans+=dfs(pos-1,num0,num1+1,limit&&i==num[pos],zero&&i==0);
        else ans+=dfs(pos-1,num0+(zero?0:1),num1,limit&&i==num[pos],zero&&i==0);
    }
    if(!limit)dp[pos][num0][num1]=ans;
    return ans;
}
ll ac(ll x){
    ll pos=0;
    while(x){
        num[pos++]=x&1;
        x/=2;
    }
    return dfs(pos-1,0,0,true,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    ll n,m;
    cin>>n>>m;
    cout<<ac(m)-ac(n-1)<<endl;
    return 0;
}

F.HDU - 3709 Balanced Number

题意

求范围内的平衡数字的个数，从数字到枢轴的距离是它与枢轴之间的偏移。然后可以计算左右部分的扭矩。如果它们是相同的，它是平衡的。平衡数字必须与其某些数字处的枢轴平衡。例如，4139是一个平衡数字，其中枢轴固定为3.对于左侧部分和右侧部分，扭矩分别为4 2 + 1 1 = 9和9 * 1 = 9。

思路

枚举枢轴的位置（1-len)然后和加起来,易知一个数最多只能有一个枢轴,假设有一个枢轴 后移动枢轴位置的,那么 平衡数字不可能会变成0.

然后再减去前导0的数比如00 000 0000

如果中间的平衡数的值小于0了那么这个数的这个位置为枢轴的肯定没有平衡数；比如前面已经4359以3为枢轴 左边是4*1 右边是5 ->4-5=-1 在过去值肯定比-1要小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int num[21];
ll dp[21][21][2200];
ll dfs(int pos,int on,int nownum,bool limit){
    if(pos==-1)return nownum==0;
    if(nownum<0)return 0;
    if(!limit&&dp[pos][on][nownum]!=-1)return dp[pos][on][nownum];
    int up=limit?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,on,nownum+(pos+1-on)*i,limit&&i==num[pos]);
    }
    if(!limit)dp[pos][on][nownum]=ans;
    return ans;
}
ll ac(ll x){
    if(x<0)return 0;
    ll pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    ll ans=0;
    for(int i=1;i<=pos;i++)ans+=dfs(pos-1,i,0,1);
    return ans-(pos-1);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    ll a,b;
    int cnt=0;
    while(t--){
        cin>>a>>b;
        cout<<ac(b)-ac(a-1)<<endl;
    }
    return 0;
}

G.HDU - 3652 B-number

题意

要13并且能被13整除的数；模板题，要标记当前余的数和前面的那个数！！和是否有13

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int num[11];
int dp[11][15][2][15];
int dfs(int pos,int pre,bool flag,int nownum,bool limit){
    if(pos==-1)return (flag)&&(nownum==0);
    if(dp[pos][nownum][flag][pre]!=-1&&!limit)return dp[pos][nownum][flag][pre];
    int up=limit?num[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,i,flag||(pre==1&&i==3),(nownum*10+i)%13,limit&&(i==num[pos]));
    }
    if(!limit)dp[pos][nownum][flag][pre]=ans;
    return ans;
}
int ac(int x){
    int ans=0;
    while(x){
        num[ans++]=x%10;
        x/=10;
    }
    return dfs(ans-1,0,false,0,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    memset(dp,-1,sizeof(dp));
    while(cin>>n){
        cout<<ac(n)<<endl;
    }
    return 0;
}

H.HDU - 4734 F(x)

题意

一个A 一个B，给出一个F(x)的定义，让你求出0-B中有多少个F(x)<=F(a)

思路

一开始是想直接存每个数的F(x)然后和F(a)比较,不过这样就不能记忆化搜索了，后来发现直接存F(a)-F(x)的差值就行了如果差值小于0就直接返回 ，而且F(a)的最大值只有20736左右

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int num[11];
int dp[11][20736];
int dfs(int pos,bool limit,int sum){
    if(pos==-1)return sum>=0;
    if(sum<0)return 0;
    if(dp[pos][sum]!=-1&&!limit)return dp[pos][sum];
    int up=limit?num[pos]:9;
    int ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,limit&&(i==num[pos]),sum-i*(1<<pos));
    }
    if(!limit)dp[pos][sum]=ans;
    return ans;
}
int ac(int x,int sum){
    int ans=0;
    while(x){
        num[ans++]=x%10;
        x/=10;
    }
    return dfs(ans-1,true,sum);
}
int getA(int x){
    int ans=0;
    while(x){
        num[ans++]=x%10;
        x/=10;
    }
    int sum=0;
    for(int i=0;i<ans;i++){
        sum+=(1<<i)*num[i];
    }
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    int cnt=0;
    while(t--){
        int a,b;
        cin>>a>>b;
        int sum=getA(a);
        cout<<"Case #"<<++cnt<<": ";
        cout<<ac(b,sum)<<endl;
    }
    return 0;
}

I.ZOJ - 3494 BCD Code

题意

给定N个01串，再给定区间[a,b]，问区间[a,b]里面有多少个数转化成BCD码之后不包含任何前面给出01串。1 <= A <= B <= 10^200

题解

正好最近都在做AC自动机,一看到不包括前面的01串马上想到自动机….首先把前面的N个01串扔进AC自动机里面求出坏点,表示当前当前点可以走那些数字,然后判断0-9的BCD码有没有接触到不能走的点

注意数字太大要用字符串存取

这题真有趣,真好AC自动机和数位DP的结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+9;
const int maxn=1500;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
struct Trie{
    int next[2010][2],fail[2010];bool end[2010];
    int L,root;
    int newnode(){
        for(int i=0;i<2;i++){
            next[L][i]=-1;
        }
        end[L++]=false;
        return L-1;
    }
    void init(){
        L=0;
        root=newnode();
    }
    void insert(char buf[]){
        int len=strlen(buf);
        int now=root;
        for(int i=0;i<len;i++){
            if(next[now][buf[i]-'0']==-1)
                next[now][buf[i]-'0']=newnode();
            now=next[now][buf[i]-'0'];
        }
        end[now]=true;
    }
    void build(){
        queue<int>Q;
        fail[root]=root;
        for(int i=0;i<2;i++)
            if(next[root][i]==-1)next[root][i]=root;
            else{
                fail[next[root][i]]=root;
                Q.push(next[root][i]);
            }
        while(!Q.empty()){
            int now=Q.front();
            Q.pop();
            if(end[fail[now]]==true)end[now]=true;
            for(int i=0;i<2;i++)
                if(next[now][i]==-1)next[now][i]=next[fail[now]][i];
                else{
                    fail[next[now][i]]=next[fail[now]][i];
                    Q.push(next[now][i]);
                }
        }

    }
};
Trie ac;
int num[250];
ll dp[250][2005];
ll dfs(int pos,int sta,bool limit,bool zero){
    if(pos==-1)return !zero;
    if(!zero&&!limit&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=limit?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(zero&&i==0)ans=(ans+dfs(pos-1,sta,limit&&i==up,zero&&i==0)+mod)%mod;
        else{
            int nex=sta,x=i;
            bool flag=true;
            for(int j=(1<<3);j;j>>=1){
                int bit=x/j;x=x-bit*j;
                nex=ac.next[nex][bit];
                if(ac.end[nex]){
                    flag=false;break;
                }
            }
            if(flag)ans=(ans+dfs(pos-1,nex,limit&&i==up,zero&&i==0)+mod)%mod;
        }
    }
    if(!zero&&!limit)dp[pos][sta]=ans;
    return ans;
}
ll acc(char x[]){
    int len=strlen(x);
    for(int i=0;i<len;i++)num[i]=x[len-1-i]-'0';
    return dfs(len-1,0,true,true);
}
char str[220];
char st[220],ed[220];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        ac.init();
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++){
            cin>>str;
            ac.insert(str);
        }
        ac.build();
        cin>>st>>ed;
        int lena=strlen(st),p=lena-1;
        while(st[p]=='0')st[p--]='9';
        st[p]=st[p]-1;
        cout<<((acc(ed)-acc(st)+mod)%mod)<<endl;
    }
    return 0;
}

J.HDU - 4507 吉哥系列故事――恨7不成妻

题意

求指定范围内与7不沾边的所有数的平方和。结果要mod 10^9+7

思路

与7不沾边的数需要满足三个条件。

①不出现7

②各位数和不是7的倍数

③这个数不是7的倍数

这三个条件都是基础的数位DP。

但是这题要统计的不是符合条件个数，而是平方和。

也就是说在DP时候，要重建每个数，算出平方，然后求和。

需要维护三个值（推荐使用结构体）, 假定dfs推出返回的结构体是next，当前结果的结构体是ans

①符合条件数的个数 cnt

②符合条件数的和 sum

③符合添加数的平方和 sqsum

其中①是基础数位DP。②next.sum+(10^len×i)×ans.cnt，其中(10^len×i)×ans.cnt代表以len为首位的这部分数字和。

③首先重建一下这个数，(10^len×i+x),其中x是这个数的后面部分，则平方和就是(10^len×i)^2+x^2+2×10^len×i×x，其中x^2=next.sqsum

整体还要乘以next.cnt，毕竟不止一个。

这样sqsum+=next.sqsum

sqsum+=(2×10^len×i×x)×next.cnt=(2×10^len×i)×next.sum(神奇的化简）

sqsum+=(10^len×i)^2×next.cnt

mod之后统计函数也有个小陷阱，那就是f(r)在mod之后有可能小于f(l-1)。也就是要对负数取正数模。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=1e9+7;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
int num[20];
ll ten[20];
struct node{
    ll cnt,sqr,sum;
    bool vis;
    node(ll a=0,ll b=0,ll c=0,bool d=0):cnt(a),sqr(b),sum(c),vis(d){}
}dp[20][11][11];
node dfs(int pos,ll mod1,ll mod2,bool limit){
    if(pos==-1){
        if(mod1%7==0||mod2%7==0)return node(0);
        return node(1);
    }
    if(dp[pos][mod1][mod2].vis&&!limit)return dp[pos][mod1][mod2];
    int up=limit?num[pos]:9;
    node now;
    for(int i=0;i<=up;i++){
        if(i==7)continue;
        node tmp=dfs(pos-1,(mod1+i)%7,(mod2*10+i)%7,limit&&i==num[pos]);
        ll aa=i*ten[pos]%mod;
        now.cnt=(now.cnt+tmp.cnt)%mod;
        now.sum=(now.sum+aa*tmp.cnt%mod+tmp.sum)%mod;
        now.sqr=(aa*aa%mod*tmp.cnt%mod+2*aa*tmp.sum%mod+tmp.sqr+now.sqr)%mod;
    }
    if(!limit){
        dp[pos][mod1][mod2]=now;
        dp[pos][mod1][mod2].vis=1;
    }
    return now;
}
ll ac(ll x){
    int ans=0;
    while(x){
        num[ans++]=x%10;
        x/=10;
    }
    node ret=dfs(ans-1,0,0,1);
    return ret.sqr%mod;
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t;
    cin>>t;
    ten[0]=1;for(int i=1;i<=18;i++)ten[i]=ten[i-1]*10;
    while(t--){
        ll a,b;
        cin>>a>>b;
        cout<<(ac(b)-ac(a-1)+mod)%mod<<endl;
    }
    return 0;
}

K.SPOJ - BALNUM Balanced Numbers

题意

问[L, R]内有多少数字，满足每个奇数都出现了偶数次，每个偶数都出现了奇数次（没有出现的数不考虑）

题解1

用三进制来表示状态，0表示没出现，1表示出现奇数次，2表示出现偶数次。

然后就是裸的数位DP了

特别注意&&的优先度是低于==的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1e5+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int num[25];
int three[10];
ll dp[25][maxn];
int isok(int sta){
    for(int i=0;i<=9;i++,sta/=3){
        int k=sta%3;
        if(!k)continue;
        if((i&1)&&(k&1))return 0;
        if(((i&1)==0)&&(k==2))return 0;
    }
    return 1;
}

int change(int sta,int i){
    int nu[10];
    for(int j=0;j<=9;j++,sta/=3)nu[j]=sta%3;
    if(nu[i]==0)nu[i]=1;
    else nu[i]=3-nu[i];
    for(int j=9;j>=0;j--)sta=sta*3+nu[j];
    return sta;
}
ll dfs(int pos,int sta,bool first,bool zero){
    if(pos==-1)return isok(sta);
    if(!first&&dp[pos][sta]!=-1)return dp[pos][sta];
    int up=first?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        if(zero&&i==0)
            ans+=dfs(pos-1,sta,first&&i==num[pos],zero&&i==0);
        else
            ans+=dfs(pos-1,change(sta,i),first&&i==num[pos],zero&&i==0);
    }
    if(!first)dp[pos][sta]=ans;
    return ans;
}
ll ac(ll x){
    int pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,true,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    while(t--){
        ll m,n;
        cin>>n>>m;
        cout<<ac(m)-ac(n-1)<<endl;
    }
    return 0;
}

解法2

可以多出一阶存1-9是否出现过 不过数组不能开到1<<11 要开到1<<10+50左右不然会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include  <stdio.h>
#include   <math.h>
#include   <time.h>
#include   <vector>
#include   <bitset>
#include    <queue>
#include      <map>
#include      <set>
using namespace std;
typedef long long ll;
#define pp pair<int,int>
const ll mod=998244353;
const int maxn=1024+5;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;}
int num[25];
ll dp[25][maxn][maxn];
int isok(int sta,int haha){
    for(int i=0;i<=9;i++){
        if((haha&(1<<i))==0)continue;
        if(i&1){//奇数出现偶数次
            if(sta&(1<<i)){
                return 0;
            }
        }
        else{
            if((sta&(1<<i))==0){
                return 0;
            }
        }
    }
    return 1;
}
int change(int sta,int i){
    return sta^(1<<i);
}
ll dfs(int pos,int sta,int haha,bool first,bool zero){
    if(pos==-1)return isok(sta,haha);
    if(!first&&dp[pos][sta][haha]!=-1)return dp[pos][sta][haha];
    int up=first?num[pos]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ll now=change(sta,i);
        if(zero&&i==0)
            ans+=dfs(pos-1,sta,haha,first&&i==num[pos],zero&&i==0);
        else
            ans+=dfs(pos-1,change(sta,i),haha|(1<<i),first&&i==num[pos],zero&&i==0);
    }
    if(!first)dp[pos][sta][haha]=ans;
    return ans;
}
ll ac(ll x){
    int pos=0;
    while(x){
        num[pos++]=x%10;
        x/=10;
    }
    return dfs(pos-1,0,0,true,true);
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    memset(dp,-1,sizeof(dp));
    int t;
    cin>>t;
    while(t--){
        ll m,n;
        cin>>n>>m;
        cout<<ac(m)-ac(n-1)<<endl;
    }
    return 0;
}