题解 P3303 【[SDOI2013]淘金】

· · 题解

反过来想：对于一个i，求有多少个j满足f(j)=i（下面记作c(i)）。

可以发现在f(j)=i中，数i必然可以分解成2^a\times3^b\times5^c\times7^d的形式。

所以虽然N\leq 10^{12}，但是满足c(i)>0的i是不多的（实测最多14672个）。

因此设状态：dp[i,j,0/1]表示从低到高位到了第i位，各位数的积为j（需要离散化），第三维表示小于等于/大于N的从低到高前i位。

转移即枚举第i位数k，如果k|j，

那么dp[i,j,0/1]可以从dp[i-1,\frac j k,0/1]转移过来。

这样就能算出所有>0的c(i)。

回到题目，可以得出，位置(x,y)的金子数目为c(x)\times c(y)。

所以要求的就是c(x)\times c(y)的前K大值之和。

由于K较小，因此可以将c从小到大排序，用大根堆维护t（有效的c(x)的个数）个指针（如果第i个指针在j位置，则关键字为c(i)\times c(j)，这里的c是排序后的，因此c(i)在这里是指排序后第i小的c值），每次贪心选择关键字最大的指针向左移，统计答案。

代码：

#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
using namespace std;
typedef long long ll;
const int N = 15, M = 15000, MX = 1e9 + 7;
ll n, otz[M], f[N][M][2], sum[M];
int K, QAQ, a[N], ans;
map<ll, int> orz;
struct cyx
{
    int id, pos;
    cyx() {}
    cyx(int _x, int _y) :
        id(_x), pos(_y) {}
    friend inline bool operator < (cyx a, cyx b)
    {
        return sum[a.id] * sum[a.pos] < sum[b.id] * sum[b.pos];
    }
};
priority_queue<cyx> pq;
void DP(ll num)
{
    int i, j, k, n = 0;
    while (num) a[++n] = num % 10, num /= 10;
    For (k, 1, 9)
        f[1][orz[k]][k > a[1]]++;
    For (i, 2, n) For (j, 1, QAQ) For (k, 1, 9)
    {
        ll q = otz[j]; if (q % k != 0) continue;
        int h = orz[q / k];
        if (k < a[i]) f[i][j][0] += f[i - 1][h][0] + f[i - 1][h][1];
        else if (k > a[i])
            f[i][j][1] += f[i - 1][h][0] + f[i - 1][h][1];
        else f[i][j][0] += f[i - 1][h][0],
            f[i][j][1] += f[i - 1][h][1];
    }
    For (j, 1, QAQ) For (i, 1, n)
        sum[j] += f[i][j][0] + (i == n ? 0 : f[i][j][1]);
    sort(sum + 1, sum + QAQ + 1);
    K = min(1ll * K, 1ll * QAQ * QAQ);
}
int main()
{
    int i, j, k, h;
    ll x = 1;
    cin >> n >> K;
    For (i, 0, 39)
    {
        ll t = x;
        For (j, 0, 25)
        {
            ll r = x;
            For (k, 0, 17)
            {
                ll w = x;
                For (h, 0, 14)
                {
                    otz[orz[x] = ++QAQ] = x;
                    x *= 7;
                    if (x > n) break;
                }
                x = w * 5;
                if (x > n) break;
            }
            x = r * 3;
            if (x > n) break;
        }
        x = t * 2;
        if (x > n) break;
    }
    DP(n);
    For (i, 1, QAQ) pq.push(cyx(i, QAQ));
    For (i, 1, K)
    {
        cyx u = pq.top(); pq.pop();
        ans = (ans + sum[u.id] * sum[u.pos] % MX) % MX;
        if (u.pos == 1) continue;
        pq.push(cyx(u.id, u.pos - 1));
    }
    cout << ans << endl;
    return 0;
}