[原创]UVALive - 7344 Numbered Cards [数位dp+状压dp]【动态规划】

2017-07-05 22:42:33 Tabris_ 阅读数：382

博客爬取于2020-06-14 22:39:44
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/74505041

题目链接:https://cn.vjudge.net/problem/UVALive-7344
——————————————————————————————————————————
You have N cards and each has an unique number between 1 and N written on it. In how many
ways can you select a non-empty subset of the cards such that the number written on any two of your selected cards don’t have any common digits?
For example, when N = 12, {1, 2, 3}, {2, 11}, {3, 4, 5, 6, 7, 8, 9, 12} are some valid selections. But
{1, 2, 10}, {2, 5, 12} are not allowed.

Input
The first line of the input contains an integer T(T≤15)(T ≤ 15) which is the number of test cases. Each of
the following T lines denote a test case, containing an integer N(1≤N<109)(1 ≤ N < 10^9).

Output
For each test case, output the case number followed by the number of subsets modulo 1000000007.

Sample Input
2
3
12

Sample Output
Case 1: 7
Case 2: 1151
————————————————————————————————————————————
题目大意：
让你在[1,N]内选择一些数构成一个集合,使得集合中任意两个数没有相同的数字,(但一个数可以由相同的数字比如11.22),问你合法的集合的个数

首先能确定的是集合中数最多不超过10个，那么可以枚举来

先选择一个，在选择第二个，保证其两者不没有相同位即可

显然这个过程是可以进行dp的
用长度为10的二进制表示0~9.然后进行转移即可

设dp[i][j],表示取到第i个数是选择了j(二进制)对应的这些数字

从而有dp[i][j]=\displaystyle \sum dp[i-1][k]*A(表示k\xor j这个状态下的数的个数)

显然有一个O(1010241024)即可

但是对于A(表示k\xor j这个状态下的数的个数)我们应该怎么求呢

显然是预处理啊 ，
通过数位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
LL dp_nex[15][(1<<12)];
int n;
int num[12],len;
int dp[12][1111];
int f[1111];

int dfs(int pos,int limit,int na,int &nb){
    if(pos<0) return na==nb;
    int &t=dp[pos][na];
    if(!limit&&t!=-1) return t;

    int endi = 9;if(limit) endi=num[pos];

    int res = 0;
    for(int i=0;i<=endi;i++){
        if( (na|i) == 0 )
            res+=dfs(pos-1,endi==i&&limit,na,nb);
        else if(nb&(1<<i))
            res+=dfs(pos-1,endi==i&&limit,na|(1<<i),nb);
    }

    if(!limit) t=res;
    return res;
}

void solve(int x){

    for(len=0;x;x/=10) num[len++]=x%10;

    f[0]=f[1]=0;
    for(int i=2;i<(1<<10);i++){
        memset(dp,-1,sizeof(dp));
        f[i]=dfs(len-1,1,0,i);
    }
}

LL qmod(LL a,LL b){
    LL res = 1;
    while(b){
        if(b&1) res=res*a%MOD;
        b>>=1;  a  =a  *a%MOD;
    }
    return res;
}

int main(){
    int t,kcase=0;scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);

        memset(dp_nex,0,sizeof(dp_nex));

        solve(n);

        dp_nex[0][0]=1;
        int endi=(1<<10);

        for(int i=1;i<=10;i++){
            for(int j=0;j<endi;j++){
                for(int k=0;k<endi;k++){
                    if(j==k)continue;
                    if(((j&k)==k))
                        dp_nex[i][j]=(dp_nex[i][j]+dp_nex[i-1][k]*f[j-k])%MOD;
                }
            }
        }

        LL output=0;
        for(int i=1;i<=10;i++){
            int tmp=1;
            for(int j=1;j<=i;j++) tmp*=j;

            for(int j=0;j<endi;j++)
                output=(output+qmod(tmp,MOD-2)*dp_nex[i][j])%MOD;
        }
        printf("Case %d: %lld\n",++kcase,output);
    }
    return 0;
}