社区讨论
求助(Wrong answer)
P3303[SDOI2013] 淘金参与者 5已保存回复 21
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 21 条
- 当前快照
- 1 份
- 快照标识符
- @mi7dkm84
- 此快照首次捕获于
- 2025/11/20 19:55 4 个月前
- 此快照最后确认于
- 2025/11/20 23:37 4 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
#define nxt m%10,m/=10
#define lli long long int
const int mod=1e9+7;
const int maxn=15e3+5;
map<lli,lli> m;
lli w[maxn],dp[maxn][12+5],Ans,rnt;
lli n,k,v[12+5],tot,vnt,cnt,etp[maxn];
struct node{
lli id;
lli pos;
bool operator<(const node &a)const{
return w[id]*w[pos]<w[a.id]*w[a.pos];
}
};
priority_queue<node> que;
inline lli swdp(lli top,bool sx,bool qdl,lli mtp){
if(!top)
return mtp==etp[vnt];
int ___=etp[vnt]/mtp;
if(!sx && !qdl && ~dp[m[___]][top])
return dp[m[___]][top];
lli up=(sx?v[top]:9),ans=0;
for(int i=(!qdl || top==1);i<=up;i++)
if((!i && qdl) || (i && ___%i==0))
ans+=swdp(top-1,sx && i==up,qdl && !i,mtp*i+!i);
if(!sx && !qdl)
dp[m[___]][top]=ans;
return ans;
}
inline lli __Init(lli l){
for(lli i=2;i<=9;i++)
if(l*i<=n && !m[l*i]){
etp[++cnt]=l*i;
m[__Init(l*i)]=++tot;
}
return l;
}
inline void solve(int m){
do{
v[++rnt]=nxt;
}while(m);
sort(etp+1,etp+cnt+1);
memset(dp,-1,sizeof(dp));
for(vnt=0;vnt<=cnt;vnt++)
w[vnt]=swdp(rnt,true,true,1);
}
int main(){
scanf("%lld %lld",&n,&k);
__Init(1);
etp[0]=1;
solve(n);
sort(w,w+vnt+1);
k=min(k,vnt*vnt);
for(int i=0;i<=vnt;i++)
que.push((node){ i,vnt });
for(int i=1;i<=k;i++){
node u=que.top();
que.pop();
Ans=(Ans+w[u.id]*w[u.pos])%mod;
if(u.pos==1)
continue;
que.push((node){ u.id,u.pos-1 });
}
printf("%lld\n",Ans);
return 0;
}
回复
共 21 条回复,欢迎继续交流。
正在加载回复...