P3303 [SDOI2013] 淘金
是个简单题，可惜我代码暂时写挂了，起床再来改（）
显然先要求出 \(cnt(f(i)),(i \in [1,N]),cnt(x)\) 表示 \(x\) 的出现次数。求出来之后两两相乘贪心即可。
但 \(f(i)\) 最大可能是 \(10^{12}\) ，省略掉了大于 \(N\) 的情况。所以要探讨下 \(f(i)\) 的不同取值数量。
mapmp;
map,bool>vis;
int tot=0;
void dfs(int x,ll num) {
if(vis[make_pair(x,num)]) return ;
if(x==13) {
if(!mp[num]) mp[num]=1,++tot;
return ;
}
for(int i=1;i<=9;i++) dfs(x+1,num*i);
vis[make_pair(x,num)]=1;
}
int main() {
dfs(1,1); cout< 打表发现有 8282 种可能。
考虑求出 \(cnt(f(i))\) ，这个枚举下之后数位 dp 即可，即枚举 \(f(i)\)，然后考虑找一堆一些数使得乘积为 \(f(i)\)，这里直接转化为找到一些数，使得这些数各位都是 \(f(i)\) 的因数。用 \(f[x][id]\) 表示当前第 \(x\) 位，目前剩余的数是 \(map[id]\) 的答案，对于边界，当且仅当 \(map[id]=1\) 时能有贡献。
\(\text{Code}\)
#include
#define ll long long
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
ll lrd() {
ll f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
const int mod=(int)(1e9+7);
unordered_mapmp;
ll f[15][8300];
ll a[8300],acnt[8300];
int num[15],tot,cnt;
ll n,m;
ll dfs(int lim,int x,int id) {
if(!x) return a[id]==1;
if(!lim&&~f[x][id]) return f[x][id];
// cout<vis[14];
void dfs(int x,ll number) {
if(vis[x].count(number)) return ;
if(x==13) {
if(!mp[number]) a[++cnt]=number,mp[number]=1;
return ;
}
for(int i=1;i<=9;i++) dfs(x+1,number*i);
vis[x][number]=1;
}
}
bool cmp(ll x,ll y) {
return x>y;
}
priority_queueq;
int main() {
n=lrd(); m=lrd(); ll x=n;
while(x) num[++tot]=x%10,x/=10;
xgf::dfs(1,1); a[++cnt]=(ll)(1e12),mp[a[cnt]]=cnt; sort(a+1,a+1+cnt);
for(int i=1;i<=cnt;i++) mp[a[i]]=i;
memset(f,-1,sizeof(f));
for(int i=1;i<=cnt;i++) {
if(a[i]>n) {
cnt=i-1; break;
}
for(int j=1;j<=tot;j++) acnt[i]+=dfs(j==tot,j,i);
// cout<