社区讨论

求助(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 条回复,欢迎继续交流。

正在加载回复...