Loading [MathJax]/jax/output/HTML-CSS/jax.js

BZOJ 3131 「SDOI2013」淘金

发表于 | 分类于 | 24

设 c(x) 为满足 f(i)=x 即各位数字之积 =x 的 i 的个数。
那么变化之后格子 (x,y) 上有的金块个数就是 c(x)⋅c(y)。

容易发现 c(x) 中的 x 分解后若除了 2,3,5,7 还有其他质因子，c(x)=0。

问题就在于 c(x) 的求法，我们可以用数位 DP（个人喜欢记搜），状态需要记录搜到第 x 位，组成的数 =2a⋅3b⋅5c⋅7d 中的指数 a,b,c,d。
然后用一个常量数组记录一下 1−9 分解之后的四个指数，搜索的时候注意除了前导 0 的时候都不能选 0，以及所有位都是 0 时最后一位会算作前导 0 需要特判。

于是我们 DFS 一遍 n 以内的质因子只有 2,3,5,7 的数（或者直接枚举四个指数就行），求出其对应的 c 函数值，然后把所有的 c 函数值从大到小排个序。
然后我们设 c 函数值有 cnt 个，往大根堆里面丢 cnt 个形如 (x,1) 的二元组，大根堆的优先级是二元组两个数的 c 值之积。
从大根堆取出一个二元组，计算对答案的贡献，再把第二个数加一丢回去。这样执行 k 次就行了。

注意实现细节。
以及，不要问为什么我用 pbds 的优先队列。

代码： 

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <functional>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
const int LEN = 12;
const int divi[10][4] = {
    {0,0,0,0},
    {0,0,0,0},
    {1,0,0,0},
    {0,1,0,0},
    {2,0,0,0},
    {0,0,1,0},
    {1,1,0,0},
    {0,0,0,1},
    {3,0,0,0},
    {0,2,0,0}
};
const long long N = 1e12;
const int CNT = 2e4;
const long long mod = 1e9 + 7;
long long n;
int k;
int tot,d[LEN + 5];
long long f[LEN + 5][LEN * 3 + 5][LEN * 2 + 5][LEN + 5][LEN + 5][2];
long long h[CNT + 5],c[CNT + 5];
int cnt;
void dfs(int x,long long prod)
{
    static const long long d[4] = {2,3,5,7};
    if(prod > n)
        return ;
    h[++cnt] = prod;
    for(register int i = x;i < 4;++i)
        dfs(i,prod * d[i]);
}
long long dfs(int x,int _2,int _3,int _5,int _7,int lead,int top)
{
    if(_2 < 0 || _3 < 0 || _5 < 0 || _7 < 0)
        return 0;
    if(!x)
        return !_2 && !_3 && !_5 && !_7;
    if(!top && ~f[x][_2][_3][_5][_7][lead])
        return f[x][_2][_3][_5][_7][lead];
    long long ret = 0;
    int bound = top ? d[x] : 9;
    for(register int i = x > 1 ? 0 : 1;i <= bound;++i)
    {
        if(!lead && !i)
            continue;
        ret += dfs(x - 1,_2 - divi[i][0],_3 - divi[i][1],_5 - divi[i][2],_7 - divi[i][3],lead && !i,top && i == bound);
    }
    if(!top)
        f[x][_2][_3][_5][_7][lead] = ret;
    return ret;
}
long long solve(long long x)
{
    int _2 = 0;
    while(!(x % 2))
        x /= 2,++_2;
    int _3 = 0;
    while(!(x % 3))
        x /= 3,++_3;
    int _5 = 0;
    while(!(x % 5))
        x /= 5,++_5;
    int _7 = 0;
    while(!(x % 7))
        x /= 7,++_7;
    return dfs(tot,_2,_3,_5,_7,1,1);
}
struct note
{
    int x,y;
    inline bool operator<(const note &a) const
    {
        return c[x] * c[y] < c[a.x] * c[a.y];
    }
};
__gnu_pbds::priority_queue<note> pq;
long long ans;
int main()
{
    memset(f,-1,sizeof f);
    scanf("%lld%d",&n,&k);
    dfs(0,1);
    long long temp = n;
    while(temp)
    {
        d[++tot] = temp % 10;
        temp /= 10;
    }
    for(register int i = 1;i <= cnt;++i)
        c[i] = solve(h[i]);
    sort(c + 1,c + cnt + 1,greater<long long>());
    k = min(k,cnt * cnt);
    for(register int i = 1;i <= cnt;++i)
        pq.push((note){i,1});
    for(register int i = 1;i <= k;++i)
    {
        note cur = pq.top();
        pq.pop();
        ans = (ans + c[cur.x] * c[cur.y]) % mod;
        if(cur.y == cnt)
            continue;
        pq.push((note){cur.x,cur.y + 1});
    }
    printf("%lld\n",ans);
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment