BZOJ 3131 淘金

Link

震惊!某ZZ OIer此题WA了半天竟是因为[点击查看]() # Solution 感觉第一步是最难想的。。但看了题解之后又觉得是很显然的。。只是不敢想罢了。 因为数字乘积的个数比较少,离散化一下就可以开到一维状态里。 然后一切都明朗了。 然而WA了很长时间,竟然因为 1. \(10^{12}\)居然是\(13\)位数?????? 2. 把数字分解的时候中间变量写成了int????

Tips

数据范围吓人的但是似乎比较显然的算法也不能不想。因为也许吓人的范围后面隐藏着一些可以减小范围的性质。 在可能爆int的题目中WA了,试试

1
#define int int64

不要数错数字位数。。。23333 # Code

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
#include "lucida"
using std::sort;
using std::unique;
using std::lower_bound;
using std::priority_queue;
const int P=1000000007,MAXCOUNT=203491+11,MAXINSCNT=11026+11;
int64 nums[MAXCOUNT];int nc;
#define ref(x) (lower_bound(nums+1,nums+1+nc,(x))-nums)
void DFS(int pos,int maxNumber,int64 prod) {
if(!pos) {
nums[++nc]=prod;
} else {
for(int d=maxNumber;d<10;++d) {
DFS(pos-1,d,prod*d);
}
}
}
void Prep() {
nums[nc=1]=0;//数组开小愣是看不着 233
DFS(13,1,1);
sort(nums+1,nums+1+nc);
nc=unique(nums+1,nums+1+nc)-nums-1;
}
struct Node {
int64 val;
int id,ext;
Node(int64 val,int id,int ext):val(val),id(id),ext(ext) {}
friend bool operator <(const Node &a,const Node &b) {
return a.val<b.val;
}
};
int main() {
freopen("input","r",stdin);
static int64 f[14][10][2][MAXINSCNT],g[MAXINSCNT];
Prep();
int64 n;int K;is>>n>>K;
//g[pos] 乘积为pos位置的个数
int bit[14],len=0;
for(int64 x=n;x;x/=10) {
bit[++len]=x%10;
}
for(int d=1;d<=bit[len];++d) {
f[len][d][d==bit[len]][ref(d)]=1;
}
for(int i=len-1;i;--i) {
for(int d=1;d<10;++d) {
f[i][d][0][ref(d)]=1;
}
}
for(int i=len-1;i;--i) {
for(int cd=1;cd<10;++cd) {
for(int pd=1;pd<10;++pd) {
for(int pu=0;pu<2;++pu) if(!(pu && bit[i]<cd)) {
for(int prod=1;prod<=nc;++prod) if(f[i+1][pd][pu][prod]) {
if(nums[ref(nums[prod]*cd)]!=nums[prod]*cd) {
throw;
}
f[i][cd][pu && cd==bit[i]][ref(nums[prod]*cd)]+=f[i+1][pd][pu][prod];
}
}
}
}
}
for(int prod=2;prod<=nc;++prod) {
for(int d=1;d<10;++d) {
for(int u=0;u<2;++u) if(!(u && bit[1]<d)) {
g[prod-1]+=f[1][d][u][prod];
}
}
}
nc--;
sort(g+1,g+1+nc);
priority_queue<Node> Q;
for(int i=1;i<=nc;++i) {
Q.push(Node(g[i]*g[nc],i,nc));
}
int64 Ans=0;
for(int i=1;i<=K && !Q.empty();++i) {
Node cur=Q.top();Q.pop();
(Ans+=cur.val)%=P;
if(cur.ext!=1) {
Q.push(Node(g[cur.id]*g[cur.ext-1],cur.id,cur.ext-1));
}
}
os<<Ans<<'\n';
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2013 - 2017 Hey,Lucida here. All Rights Reserved.

Lucida Lu 保留所有权利