自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:47:31，当前版本为作者最后更新于2018-04-02 21:31:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

反过来想：对于一个$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;
}