[原创]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(T15)(T ≤ 15) which is the number of test cases. Each of
the following T lines denote a test case, containing an integer N(1N<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;
}