http://www.lydsy.com/JudgeOnline/problem.php?id=3131
如果已知 s[i]=j 表示有j个<=n数的数码乘积=i
那么就会有 s[a1]*s[a2] 个数 在一阵风之后到（a1，a2）位置
把所有的j用一个数组b存起来，从大到小排序
开始把（1,1）存入堆，表示当前最多的是b[1]*b[1]
每次取出堆顶(i,j)，累加 b[i]*b[j]，存入（i+1，j），（i，j+1），map 判重
就可以解决前k大之和的问题
i的上限是n，存不下，怎么办
我们发现 n以内 有大量的i 是无用的
只有质因数分解之后 质因子为2、3、5、7 的i 才是合法状态
所以 dp[len][0/1][c2][c3][c5][c7] 表示前len位，是否卡上界，当前i=2^c2 * 3^c3 * 5^c5 * 7^c7 的 j是多少
数位dp
注意不能放0，但是可以有前导0，所以除了最高位，都要加上前导0的贡献，即dp[][0][0][0][0][0]++ (前导0不卡上界)
#include<map>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> using namespace std; typedef long long LL; const int mod=1e9+; LL dp[][][][][][];
int f[][]; int a[]; int cnt;
LL b[]; priority_queue< pair<LL,pair<int,int> > >q;
map<pair<int,int>,bool>vis; void pre()
{
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
f[][]=;
} void reverse(int len)
{
int k=len/;
for(int i=;i<=k;++i) swap(a[i],a[len-i+]);
} void ADD(int &x,int y)
{
x+=y;
x-=x>=mod ? mod : ;
} LL Pow(LL a,int b)
{
LL res=;
for(;b;a*=a,b>>=)
if(b&) res*=a;
return res;
} void numberDP(LL n)
{
int len=;
LL m=n;
while(m) a[++len]=m%,m/=;
reverse(len);
int up,J;
int now=,nxt=;
for(int i=;i<len;++i,swap(now,nxt))
{
if(!i) dp[now][][][][][]++;
else dp[now][][][][][]++;
memset(dp[nxt],,sizeof(dp[nxt]));
for(int j=;j<=;++j)
for(int c2=;c2<=;++c2)
for(int c3=;c3<=;++c3)
for(int c5=;c5<=;++c5)
for(int c7=;c7<=;++c7)
if(dp[now][j][c2][c3][c5][c7])
{
if(j) up=a[i+];
else up=;
for(int k=;k<=up;++k)
{
J=(j && k==up);
dp[nxt][J][c2+f[k][]][c3+f[k][]][c5+f[k][]][c7+f[k][]]+=dp[now][j][c2][c3][c5][c7];
}
}
}
LL sum,tmp;
for(int c2=;c2<=;++c2)
{
tmp=Pow(,c2);
if(tmp>n) break;
for(int c3=;c3<=;++c3)
{
tmp=Pow(,c2)*Pow(,c3);
if(tmp>n) break;
for(int c5=;c5<=;++c5)
{
tmp=Pow(,c2)*Pow(,c3)*Pow(,c5);
if(tmp>n) break;
for(int c7=;c7<=;++c7)
{
tmp=Pow(,c2)*Pow(,c3)*Pow(,c5)*Pow(,c7);
if(tmp>n) break;
sum=dp[now][][c2][c3][c5][c7]+dp[now][][c2][c3][c5][c7];
if(sum) b[++cnt]=sum;/*,printf("%d %d %d %d %I64d\n",c2,c3,c5,c7,sum)*/;
}
}
}
}
} void get_kth(int k)
{
sort(b+,b+cnt+,greater<int>());
int i=,j=;
int ans=;
pair<LL,pair<int,int> >pr;
int x,y;
q.push(make_pair(b[]*b[],make_pair(,)));
while(k-- && !q.empty())
{
pr=q.top();
q.pop();
if(!pr.first) break;
ADD(ans,pr.first%mod);
x=pr.second.first;
y=pr.second.second;
if(!vis[make_pair(x+,y)])
{
q.push(make_pair(b[x+]*b[y],make_pair(x+,y)));
vis[make_pair(x+,y)]=true;
}
if(!vis[make_pair(x,y+)])
{
q.push(make_pair(b[x]*b[y+],make_pair(x,y+)));
vis[make_pair(x,y+)]=true;
}
}
printf("%d",ans);
} int main()
{
//freopen("gold.in","r",stdin);
//freopen("gold.out","w",stdout);
LL n; int k;
scanf("%lld%d",&n,&k);
pre();
numberDP(n);
get_kth(k);
return ;
}