3131: [Sdoi2013]淘金
Time Limit: 30 Sec Memory Limit: 256 MB
Submit: 847 Solved: 423
[Submit][Status][Discuss]
Description
小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候，所有的整数坐标点上均有一块金子，共N*N块。
一阵风吹过，金子的位置发生了一些变化。细心的小Z发现，初始在(i，j)坐标处的金子会变到(f(i)，fIj))坐标处。其中f(x)表示x各位数字的乘积，例如f(99)=81，f(12)=2，f(10)=0。如果金子变化后的坐标不在1..N的范围内，我们认为这块金子已经被移出游戏。同时可以发现，对于变化之后的游戏局面，某些坐标上的金子数量可能不止一块，而另外一些坐标上可能已经没有金子。这次变化之后，游戏将不会再对金子的位置和数量进行改变，玩家可以开始进行采集工作。
小Z很懒，打算只进行K次采集。每次采集可以得到某一个坐标上的所有金子，采集之后，该坐标上的金子数变为0。
现在小Z希望知道，对于变化之后的游戏局面，在采集次数为K的前提下，最多可以采集到多少块金子？
答案可能很大，小Z希望得到对1000000007(10^9+7)取模之后的答案。
Input
共一行，包含两介正整数N，K。
Output
一个整数，表示最多可以采集到的金子数量。
Sample Input
Sample Output
HINT
N < = 10^12 ,K < = 100000
对于100%的测试数据：K < = N^2
题解：
发现题目变成了scoi2012某道题简化版。
可以很轻松愉快的发现如果是各位数字相乘，质因子只有2357,又限制最多只有12位，所以发现预处理出来可以得到数就一万多个。
于是我们就轻松愉快的处理出了，g[i][j]，i位数乘积为j的数出现次数。
j很大，但数只有一万多个，hash走起。
好，数位dp转移也很明显了，不想太讲太多，f[i][j] i位数内乘积为j的数出现次数。。
好了，发现转移完毕后我们要找所有数次数相乘的前k大。
暴力枚举所有数是10000^2的。
我们发现每个数都是从第一个数转移起走，那么我们对于10000多个数把它记录成三元组（i，j，k）当前价值为i，当前数位j，匹配数位k，每次选了当前三元组后
又加入（v[j] * v[k + 1]，j，k + 1）放入优先队列即可
AC代码：
# include <iostream>
# include <cstdio>
# include <queue>
# include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + ;
const int M = 2e5 + ;
const LL mod = 1e9 + ;
LL g[][N],state[N],s[N],n,K;int dt,hs[M],data[],len;
struct node{
LL val;int id;
bool operator <(const node & other)const{return val > other.val;}
}a[N];
struct e{
LL w;int id,Id;
bool operator <(const e & other)const{return w < other.w;}
};
priority_queue<e>st;
void insert(LL s)
{
int p = s % M;
while(hs[p])
{
if(state[hs[p]] == s)return;
p++;
if(p == M)p = ;
}
hs[p] = ++dt;state[hs[p]] = s;
}
int id(LL s)
{
int p = s % M;
while(hs[p])
{
if(state[hs[p]] == s)return hs[p];
p++;
if(p == M)p = ;
}
return ;
}
void init()
{
for(int i = ;i <= ;i++)
{
insert(i);
g[][id(i)] = ;
}
for(int i = ;i <= ;i++)
{
int tmp = dt;
for(int j = ;j <= tmp;j++)
{
LL x = state[j];int v = j,u;
for(LL k = ;k <= ;k++)
{
insert(x * k);
u = id(x * k);
g[i + ][u] += g[i][v];
}
}
}
}
LL dfs(int now,LL K,bool lim,bool first)
{
if(!now)return K == && !first;
if(!lim && !first)return g[now][id(K)];
LL ret = ;int p = lim ? data[now] : ;
if(first)ret += dfs(now - ,K,false,first);
for(LL i = ;i <= p;i++)if(!(K % i))
ret += dfs(now - ,K / i,lim && i == p,false);
return ret;
}
void calc(LL k)
{
len = ;
while(k)data[++len] = k % ,k /= ;
for(int i = ;i <= dt;i++)a[i] = (node){dfs(len,state[i],true,true),i};
sort(a + ,a + dt + );
for(int i = ;i <= dt;i++)if(a[i].val)
st.push((e){a[i].val * a[].val,i,});
}
int main()
{
init();
scanf("%lld %lld",&n,&K);
calc(n);LL ans = ,ret;int u,v;
while(K && !st.empty())
{
(ans += st.top().w) %= mod;u = st.top().id;v = st.top().Id + ;
st.pop();
if(!a[v].val)continue;
st.push((e){a[u].val * a[v].val,u,v});
K--;
}
printf("%lld\n",ans);
}