【xsy1143】兔子的数字搜索

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目大意：请找到第$k$大的数，满足各位数字之和等于各位数字之积。其中$k≤10^{18}$。

首先我们要确定这个第$k$大的数有多大

我们用$f[i][j][he][ji]$表示我们要搜索一个$i$位的数字，还有$j$位没有确定，且确定的位总和为$i$，积为$j$的方案数。

我们发现：若$he+j<ji$，则$f[i][j][he][ji]=0$(假设后面大量地补$1$，即只增加各位数字之和而不增加各位数字之积，如果积过大，那么显然这种方法并不奏效）

若$he+j=ji$，则$f[i][j][he][ji]=\binom{i}{j}$(这种情况下，余下的j位均为$1$恰好可以让和等于积，组合数的意义为将$j$个$1$插入到已经确定的i-j位数中）

若$j=0$，那么显然只需要判一下和是否等于积即可。

若在这三种情况外，直接枚举下一位数字（$2$到$9$枚举）。

我们设第$k$大的数字位数为$x$，每次计算$f[x][x][0][1]$，若$f[x][x][0][1]<n$，则$n-=f[x][x][0][1]$，并且$x++$，否则这个$x$即为第$k$大数的位数。

接着从大到小枚举每一位，随后计算当该数前若干位确定时的方案数，借此逐位确定整个数

时间复杂度为$O(??)$

#include<bits/stdc++.h>
#define L long long
#define M 505
using namespace std;
L n,c[M][M]={}; L calc(int n,int m,int he,int ji){
if(he+m<ji) return ;
if(!m) return he==ji;
if(he+m==ji&&ji!=)
return c[n][m];
L cnt=;
for(int i=;i<;i++)
cnt+=calc(n,m-,he+i,ji*i);
return cnt;
} int main(){
cin>>n;
for(int i=;i<M;i++){
c[i][]=;
for(int j=;j<=i;j++)
c[i][j]=c[i-][j]+c[i-][j-];
}
if(n<){printf("%d\n",n); return ;}
n--;
int hh=;
while(){
L now=calc(hh,hh,,);
if(now<n) n-=now,hh++;
else break;
}
int he=,ji=;
for(int i=hh;i;i--){
for(int j=;j<;j++){
L now=calc(i-,i-,he+j,ji*j);
if(now<n)n-=now;
else{
printf("%d",j);
he+=j; ji*=j;
break;
}
}
}
}