![【bzoj 3131】[Sdoi2013]淘金 【bzoj 3131】[Sdoi2013]淘金](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1)
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
题解:
开始想偏了……导致整个人都是懵逼的。
首先打个表发现,各位数字乘积不同结果大概是8000左右,然后开始乱搞。
设$f_{i,j,k}$表示总共i位,开头数字为j,乘积排名为k的总数,转移就比较显然。
然后枚举每个k,接下来就是基本的数位DP了,这样我们求出了某一列上每个位置的金块数量$ans_{k}$,然后画个图发现,在$(i,j)$位置上的数量为我们刚才DP出的$ans_{i}*ans_{j}$,给$ans$排个序,然后贪心即可。
代码:
#define Troy 10/11/2017 #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+; inline ll read(){
ll s=,k=;char ch=getchar();
while(ch<''|ch>'') ch=='-'?k=-:,ch=getchar();
while(ch>&ch<='') s=s*+(ch^),ch=getchar();
return s*k;
} const int N=1e6; ll has[N];int num,p[],tot; inline void dfs(ll x,int from,int step){
if(step>) return ;
has[++num]=x;
for(;from<;from++){
dfs(x*from,from,step+);
}
} ll f[][][],n,k,ans[];//f[i][j][k]:i位开头为j乘积为k的答案 inline void init(){
has[++num]=;
dfs(,,);
sort(has+,has+num+);
num=unique(has+,has+num+)-has-;// printf("num=%d\n",num);
for(int i=;i<=;i++)
f[][i][lower_bound(has+,has+num+,i)-has]=;
for(int i=;i<=;i++){
for(int j=;j<;j++){
for(int k=;k<;k++)
for(int l=;l<=num;l++){
if(f[i-][k][l]==) continue;
int x;
if(has[l]*j<=has[num]){
x=lower_bound(has+,has+num+,has[l]*j)-has;
f[i][j][x]+=f[i-][k][l];
}
}
}
}
do{
p[++tot]=n%;
n/=;
}while(n);
} inline ll calc(int pos){
ll ret=;
for(int i=;i<tot;i++){
for(int j=;j<=;j++){
ret+=f[i][j][pos];
}
}
ll last=;
for(int i=tot;i;i--){
if(last>has[pos]||last==||has[pos]%last!=) break;
for(int j=;j<p[i];j++){
int x=lower_bound(has+,has++num,has[pos]/last)-has;
ret+=f[i][j][x];
}
last*=p[i];
}
return ret%mod;
} bool vis[][]; struct node {
int pos[];ll val;
friend bool operator <(node a,node b){
return a.val!=b.val?a.val<b.val:a.pos[]!=b.pos[]?a.pos[]>b.pos[]:a.pos[]>b.pos[];
}
}; priority_queue<node> q; int main(){
n=read(),k=read();
n++;
init();
for(int i=;i<=num;i++)
ans[i]=calc(i);
sort(ans+,ans+num+);
q.push((node){num,num,ans[num]*ans[num]});
ll ret=;
while(k&&(!q.empty())){
k--;
node now;
do{
now=q.top();q.pop();
}while(vis[now.pos[]][now.pos[]]&&(!q.empty()));
if(!vis[now.pos[]][now.pos[]]){
ret+=now.val;
ret%=mod;
if(now.pos[]>)
q.push((node){now.pos[]-,now.pos[],ans[now.pos[]-]*ans[now.pos[]]});
if(now.pos[]>)
q.push((node){now.pos[],now.pos[]-,ans[now.pos[]]*ans[now.pos[]-]});
}
vis[now.pos[]][now.pos[]]=true;
}
printf("%lld\n",ret);
}