P6973 [NEERC2016]List of Primes
Alex_Wei
·
·
题解
题目传送门。
题意简述：将质数集合的所有子集按照子集和为第一关键字，字典序为第二关键字从小到大排序，求最终形成的字符串的第 l\sim r 个字符。
在 cnblogs 内查看。
又是一道妙妙题。
首先考虑当 r\leq 10^5 时直接搜索，首先枚举子集和 i，状态是 sum,len,lim 表示剩余子集和为 sum，大小为 len，接下来只能使用第 lim 个及以后的质数。边界是 sum=0，表示找到一个符合题意的子集。
直接暴力跑大概可以过 r\leq 10^5，不过有一个显然的剪枝：预处理 f_{i,j} 表示只用第 j 个及以后的质数能否拼出 sum=i，爆搜下一个分支时可以快速判断是否合法，从而避免进入不合法的分支。这样一来复杂度就变成了线性 \mathcal{O}(r)。
爆搜时，我们记录一个全局变量 $acc(umulation)$ 表示已经遍历过的子集长度，此外还要在状态中加入 $slen$ 表示当前分支已经选择的质数的长度之和，即 $\sum_{p\in \mathrm{chosen}}bit(p)$（原因接下来会讲）。
---
首先判断搜索边界：$sum$ 是否 $=0$。是 $0$ 就表示遍历到了一个子集，将该子集计入答案并返回，否则根据已有的信息算出**该分支接下来所能产生的所有子集的长度之和**，与 $acc$ 求和后看是否小于 $l$，若小于，则直接更新 $acc$ 并返回即可。否则继续搜索即可。
接着考虑到了搜索边界该干什么：如果遍历到了一个子集，那么一个字符一个字符地考虑：插入一个字符时，首先将 $acc$ 自增 $1$，如果 $acc>r$ 那么退出程序；否则，如果 $acc\geq l$ 那么输出该字符；否则啥也不干。
怎么根据已有的信息算出该分支的子集长度总和呢？因为能产生 $f_{sum,lim}$ 个子集，因此 $acc$ 长度加上：
- $4f_{sum,lim}$ 表示边界的四个字符：$\texttt{'[', ']', ',', ' '}$。
- $(len-1)\times 2f_{sum,lim}$ 表示已经选择的 $len$ 个数所产生的 $len-1$ 个长度为 $2$ 的间隔 $\texttt{‘,’, ‘ ’}$（代码中 $len$ 的初始值为 $1$，所以是 $2len$）。
- $g_{sum,lim}$（这个就不用解释了吧 = . =）。
- $slen\times f_{sum,lim}$ 表示已经选择的质数长度在所有 $f_{sum,lim}$ 个子集中所贡献的长度之和，这也是我们要记录 $slen$ 的原因。
时间复杂度 $\mathcal{O}(r-l)$，也可以说是 $\mathcal{O}(n\pi(n))$，其中 $n\approx 2100$。
此外，今天是 2021 年的七夕节（8.14），祝大家七夕快乐，早日脱单（大雾）！
```cpp
const int N=2100+5;
const int P=350;
int cnt,vis[N],pr[N],bt[N];
ll f[N][P],g[N][P];
void init(){
for(int i=2;i<N;i++){
if(vis[i])continue;
pr[++cnt]=i,f[i][cnt]=1,g[i][cnt]=bt[i]=log10(i)+1;
for(int j=i+i;j<N;j+=i)vis[j]=1;
}
for(int i=cnt;i;i--){
int len=bt[pr[i]]+2;
for(int j=pr[i];j<N;j++)
f[j][i]+=f[j-pr[i]][i+1]+f[j][i+1],
g[j][i]+=g[j-pr[i]][i+1]+g[j][i+1]+f[j-pr[i]][i+1]*len;
}
}
ll l,r,acc,p[N];
string to_str(int x){
string s;
while(x)s+=x%10+'0',x/=10;
reverse(s.begin(),s.end());
return s;
}
void add(char s){
if(++acc>r)exit(0);
if(acc>=l)cout<<s;
}
void dfs(int sum,int len,int lim,ll slen){
if(!sum){
add('[');
for(int i=1;i<=len;i++){
string s=to_str(p[i]);
for(int j=0;j<s.size();j++)add(s[j]);
if(i<len)add(','),add(' ');
} add(']'),add(','),add(' ');
return;
}
ll nw=acc+(len*2+4+slen)*f[sum][lim]+g[sum][lim];
if(nw<l)return acc=nw,void();
len++;
for(int j=lim;j<=cnt;j++){
int res=sum-pr[j]; p[len]=pr[j];
if(res<0)break;
if(res==0||f[res][j])dfs(res,len,j+1,slen+bt[pr[j]]);
}
}
int main(){
init(),cin>>l>>r;
for(int i=2;i<N;i++)dfs(i,0,1,0);
return 0;
}
```