蒟蒻们的补番之旅题解
ouuan
2018-10-06 22:16:51
## [比赛地址](https://www.luogu.org/contestnew/show/12010)
> ~~本场比赛良心至极，除了状压之外几乎都是PJ知识点，没有任何高深的算法，也没有码量较大的题目。~~
本场比赛还是（很）有一定思维难度的...
## A 血小板与凝血因子
ctr：wjyyy
tutorial：wjyyy
~~colorful eggs~~：ouuan
彩蛋：
1. 可爱的题面与比赛页形成鲜明对比
2. （赛后提交的）评测结果有惊喜！
这道题可爱的题面、良心的题意、良心的范围是不是让您对这场比赛心生好感了呢？
这道题主要考查了对数据的排序。在$n\le 1,000$的数据中，您可以使用任何您可以想到的~~时间复杂度在O(n²logn)以内的~~排序方法来对$a_i$进行排序。
您甚至可以方便地使用`std::sort`、`std::map`来帮您减少代码复杂度，从而在这场ACM赛制的比赛中风生水起。
$\text{ctr}$相信，这道可爱又良心的题目，会让您的比赛之旅有一个好的~~1A~~开始，为您的AK之路提供有力的帮助。
因为给出了两种容器，而且容器只能统一使用一种，因此一种比较暴力的方式是枚举这两种哪种更优。
实际上我们可以先对$a_i$排序，然后看出现了多少种不同的元素，元素的种类数是只使用容器1的答案，同种元素出现次数的最大值是容器2的答案。
比较上述两者答案，选择较小的。对容器1而言，答案就是每行把同种元素分为一组；对容器2而言，假设某种元素出现了$k$次，那么它出现且仅出现在第$1\sim k$组中。这样输出每组的元素数及元素即可，同时~~因为良心的spj writer~~可以不按顺序输出。
如果迭代器使用熟练的话，可以直接用`std::map`统计答案并简洁输出。
### std::map：（wjyyy）
```
#include<cstdio>
#include<map>
using std::map;
map<int,int> m;
int a[1010];
int ans[1010][1010];
int main()
{
int n,u;
scanf("%d",&n);
int mx=0;
for(int i=1;i<=n;++i)
{
scanf("%d",&u);
m[u]++;
mx=mx>m[u]?mx:m[u];//同种元素出现的最多次数
}
ans[0][0]=mx<m.size()?mx:m.size();
printf("%d ",ans[0][0]);
if(mx<m.size())
{
printf("%d\n",2);
for(map<int,int>::iterator it=m.begin();it!=m.end();++it)
{
int num=it->second;
for(int i=1;i<=num;++i)
ans[i][++ans[i][0]]=it->first;
}
for(int i=1;i<=ans[0][0];++i)
{
for(int j=0;j<=ans[i][0];++j)
printf("%d ",ans[i][j]);
puts("");
}
}
else
{
printf("%d\n",1);
for(map<int,int>::iterator it=m.begin();it!=m.end();++it)
{
int num=it->second;
printf("%d ",num);
for(int i=1;i<=num;++i)
printf("%d ",it->first);
puts("");
}
}
return 0;
}
```
### std::sort：（ouuan）
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[1010],type,maxx,plan[1010][1010];
int main()
{
int i,j,temp=0;
cin>>n;
for (i=0;i<n;++i)
{
cin>>a[i];
}
sort(a,a+n);
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
++temp;
}
else
{
++type;
maxx=max(temp,maxx);
temp=1;
}
}
maxx=max(temp,maxx);
if (type>maxx)
{
type=0;
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
++temp;
plan[temp][++plan[temp][0]]=a[i];
}
else
{
++type;
temp=1;
plan[1][++plan[1][0]]=a[i];
}
}
cout<<maxx<<" 2";
for (i=1;i<=maxx;++i)
{
cout<<endl<<plan[i][0];
for (j=1;j<=plan[i][0];++j)
{
cout<<' '<<plan[i][j];
}
}
}
else
{
type=0;
for (i=0;i<n;++i)
{
if (i>0&&a[i]==a[i-1])
{
plan[type][++plan[type][0]]=a[i];
}
else
{
++type;
plan[type][++plan[type][0]]=a[i];
}
}
cout<<type<<" 1";
for (i=1;i<=type;++i)
{
cout<<endl<<plan[i][0];
for (j=1;j<=plan[i][0];++j)
{
cout<<' '<<plan[i][j];
}
}
}
return 0;
}
```
$\color{white}\tiny\text{wjyyy：极力吐槽ouuan的码风}$
## B 小埋与扫雷
ctr：ouuan
tutorial：ouuan
这题考察~~读题能力以及~~基本的dfs
看懂题目后，按题目所述，先求出所有的数字和空格，然后对每个空格dfs求空的个数，最后对每个数字判断周围是否有空格即可。
稍微优化一点的做法是先把所有数字记录答案，dfs时遇到数字把答案减一并不继续dfs。这样码量可以略小一点（本来就不大），时间优化也不大。
### 参考代码
```
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int dir[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}}; //用数组记录8个方向便于枚举
void dfs(int x,int y);
int n,m,g[1010][1010],ans;
bool vis[1010][1010];
int main()
{
int i,j,k;
memset(g,-1,sizeof(g)); //初始化为-1方便判断边界
cin>>n>>m;
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
cin>>g[i][j];
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (g[i][j]==1)
{
for (k=0;k<8;++k)
{
if (g[i+dir[k][0]][j+dir[k][1]]==0)
{
g[i+dir[k][0]][j+dir[k][1]]=2; //把所有数字设为2
++ans;
}
}
}
}
}
for (i=1;i<=n;++i)
{
for (j=1;j<=m;++j)
{
if (g[i][j]==0&&!vis[i][j])
{
dfs(i,j);
++ans;
}
}
}
cout<<ans;
return 0;
}
void dfs(int x,int y)
{
if (vis[x][y]||g[x][y]==-1)
{
return;
}
vis[x][y]=true;
if (g[x][y]==0)
{
for (int i=0;i<8;++i)
{
dfs(x+dir[i][0],y+dir[i][1]); //dfs到空格继续dfs
}
}
else
{
--ans; //dfs到数字将答案减一
}
}
```
## C 朋也与光玉
ctr：ouuan
tutorial：ouuan
~~小调查：多少CLer看到题面泪目了~~
先说一下数据点的（彩蛋？）：前 $7$ 个点数据都比较小，对应学园篇的（前）$7$ 个光玉；第 $8$ 个点数据同样比较小，然而是专门构造用来卡爆搜（不记忆化但剪枝）的，对应光玉消失事件；总共有 $13$ 个测试点，和数据范围最大 $13$ 一样，都对应着总共 $13$ 颗光玉。
此题无需优化，按题意搜索 / $dp$ 即可，但如果搜索必须记忆化（说不定有什么神奇的剪枝能过这道题吧...ctr不知道QAQ）。
状态的表示需要状压：$f[i][j]$ 表示从节点 $i$ 起，$j$ 中第 $k$ 位为 $1$ 表示收集了 $k$ 号光玉，的最短路径长度。
复杂度的话..共有 $n\times 2^k$ 种状态，每种状态都可以从另外 $n$ 种状态转移，所以总的复杂度是 $O(n^22^k)$。这玩意算出来有 $8\times 10^7$，实际上根本跑不满，std最慢点只用了 $0.5s$（记搜和 $dp$ 都是）。
### 记搜：
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=110;
const int K=13;
const int INF=0x7fffffff;
int dp(int x,int y);
int t,n,m,k,a[N],g[N][N],f[N][1<<K],ans;
int main()
{
int i,u,v;
memset(g,-1,sizeof(g));
memset(f,-1,sizeof(f));
ans=INF;
cin>>n>>m>>k;
for (i=1;i<=n;++i)
{
cin>>a[i];
}
for (i=0;i<m;++i)
{
cin>>u>>v;
cin>>g[u][v];
}
for (i=1;i<=n;++i)
{
if (dp(i,(1<<k)-1)!=-2) //-1表示没搜过，-2表示无解
{
ans=min(ans,f[i][(1<<k)-1]);
}
}
if (ans==INF)
{
cout<<"Ushio!\n";
}
else
{
cout<<ans<<endl;
}
return 0;
}
int dp(int x,int y)
{
if (f[x][y]!=-1)
{
return f[x][y];
}
if (y==(1<<a[x]))
{
return f[x][y]=0;
}
f[x][y]=-2;
for (int i=1;i<=n;++i)
{
if (g[x][i]!=-1&&a[x]!=a[i]&&(y&(1<<a[i]))&&dp(i,y^(1<<a[x]))!=-2&&(f[i][y^(1<<a[x])]+g[x][i]<f[x][y]||f[x][y]==-2)) //分别表示：有边、光玉不同、当前状态包含节点i的光玉、以i为起点能够收集完当前状态除了当前节点以外的光玉、从i转移比当前答案更优
{
f[x][y]=f[i][y^(1<<a[x])]+g[x][i];
}
}
return f[x][y];
}
```
### 递推：
```
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N=110;
const int K=13;
const int INF=0x7fffffff;
int n,m,k,a[N],g[N][N],f[N][1<<K],ans;
int main()
{
int i,j,u,v;
memset(g,-1,sizeof(g));
memset(f,-1,sizeof(f));
ans=INF;
cin>>n>>m>>k;
for (i=1;i<=n;++i)
{
cin>>a[i];
}
for (i=0;i<m;++i)
{
cin>>u>>v;
cin>>g[u][v];
}
for (u=1;u<=n;++u)
{
f[u][1<<a[u]]=0;
}
for (i=2;i<=k;++i)
{
for (u=1;u<=n;++u)
{
for (j=1;j<(1<<k);++j) //枚举从下一个点起的状态
{
if (__builtin_popcount(j)==i-1&&((j&(1<<a[u]))==0)) //__builtin_popcount(x)是x二进制下1的个数
{
for (v=1;v<=n;++v)
{
if (g[u][v]!=-1&&(j&(1<<a[v]))&&f[v][j]!=-1)
{
if (f[u][j|(1<<a[u])]>g[u][v]+f[v][j]||f[u][j|(1<<a[u])]==-1)
{
f[u][j|(1<<a[u])]=g[u][v]+f[v][j];
}
}
}
}
}
}
}
for (u=1;u<=n;++u)
{
if (ans>f[u][(1<<k)-1]&&f[u][(1<<k)-1]!=-1)
{
ans=f[u][(1<<k)-1];
}
}
if (ans==INF)
{
cout<<"Ushio!\n";
}
else
{
cout<<ans<<endl;
}
return 0;
}
```
## D 美樱的颜料
ctr：ouuan
tutorial：ouuan（实际上DEF的优秀做法都是sooke想出来的）
### 一、朴素做法
先考虑确定了选择的第一个数 $i$。那么必须先选择 $1$ ~ $n$ 中所有 $i$ 的倍数，再选择 $i$ 除自身外最大约数的倍数……依次类推，直到选完 $m$ 个数。
所以需要预处理的是 $1$ ~ $n$ 的除自身外最大约数，可以在线性筛素数的过程中求出。
令 $f_i$ 表示 $i$ 除自身外最大的约数，那么如果一个数是 $f_i$ 的倍数，它在计算 $i$ 的倍数的贡献时和计算 $f_i$ 的倍数的贡献时都会被计算，所以要去重。
（假设 $\lfloor \frac n {f_i}\rfloor< m$，$\lfloor \frac n {f_{f_i}}\rfloor\ge m$）
总贡献$=\lfloor \frac n i\rfloor\times i+\left(\lfloor \frac n {f_i}\rfloor-\lfloor \frac n i\rfloor\right)\times f_i+\left(m-\lfloor \frac n {f_i}\rfloor\right)\times f_{f_i}$
$\quad\quad\ \,=\lfloor \frac n i\rfloor\times (i-f_i)+\lfloor \frac n {f_i}\rfloor\times (f_i-f_{f_i})+m\times f_{f_i}$
若 $\lfloor \frac n {f_{...f_i}}\rfloor< m$，$\lfloor \frac n {f_{f_{...f_i}}}\rfloor\ge m$（层数与上面的示例不同），计算方式是类似的。
~~然后只要暴力枚举选的第一个数即可~~
要是没有sooke确实是可以的.但是在讲正解前还是看一下这个做法的参考代码吧：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10000010;
int n,m,p[N],f[N],tot,ans;
bool np[N];
int main()
{
int i,j,temp;
cin>>n>>m;
for (i=2;i<=n;++i)
{
if (!np[i])
{
p[++tot]=i;
f[i]=1;
}
for (j=1;j<=tot&&i*p[j]<=n;++j)
{
np[i*p[j]]=true;
f[i*p[j]]=i;
if (i%p[j]==0)
{
break;
}
}
}
for (i=1;i<=n;++i)
{
temp=0;
for (j=i;;j=f[j])
{
if (n/j<m)
{
temp+=n/j*(j-f[j]);
}
else
{
temp+=m*j;
break;
}
}
ans=max(ans,temp);
}
cout<<ans;
return 0;
}
```
这个做法的时间复杂度是 $O(nloglogn)$ 的（后面的枚举部分复杂度实际上和埃氏筛一样，都是质因数个数和），空间大约需要50MB。
### 二、优秀做法
可以发现，$f$ 数组占用了大量的内存（$4\times 10^7\mathrm{B}\approx38\mathrm{MB}$），有没有办法不把 $f$ 存下来做这道题呢？
注意计算 $f$ 的这个循环（也就是线性筛的循环）：
```
for (i=2;i<=n;++i)
{
if (!np[i])
{
p[++tot]=i;
f[i]=1;
}
for (j=1;j<=tot&&i*p[j]<=n;++j)
{
np[i*p[j]]=true;
f[i*p[j]]=i;
if (i%p[j]==0)
{
break;
}
}
}
```
事实上我们虽然不能快速地求出任意一个 $f_i$ ，但我们可以快速地求出满足 $f_x=i$ 的所有 $x$。
先考虑 $n=m$ 的情况，把所有数抽象成一棵树，以 $f_u$ 为 $u$ 的父亲， $f_u$ 和 $u$ 之间的边权为 $\lfloor\frac n u\rfloor\times(u-f_u)$，那么以某个数为第一个数的答案就是这个数到树根的距离。可以用dfs解决，用类似线性筛的方式找儿子。
若 $n\ne m$，考虑当前节点 $u$ 以 $ans_u$ 表示以 $u$ 为第一个数的答案，若 $\lfloor\frac n u\rfloor\ge m$，则 $ans_u=\lfloor\frac n u\rfloor\times m$，否则，令 $u$ 的父亲为 $f_u$，$ans_u=ans_{f_u}+\lfloor\frac n u\rfloor\times(u-f_u)$。仔细看看朴素算法的做法就能明白为什么是这样了。
总的时间复杂度是 $O(n)$ 的，空间消耗只有不到 $\rm 14MB$。
参考代码：
```
#include <iostream>
#include <cstdio>
using namespace std;
const int N=10000010;
void dfs(int u,int fa,int sum);
int n,m,p[N/10],tot,ans;
bool np[N];
int main()
{
int i,j;
cin>>n>>m;
for (i=2;i<=n;++i)
{
if (!np[i])
{
p[++tot]=i;
}
for (j=1;j<=tot&&i*p[j]<=n;++j)
{
np[i*p[j]]=true;
if (i%p[j]==0)
{
break;
}
}
}
dfs(1,0,0);
cout<<ans;
return 0;
}
void dfs(int u,int fa,int sum)
{
sum+=min(m,n/u)*(u-fa);
ans=max(ans,sum);
for (int i=1;i<=tot&&u*p[i]<=n;++i)
{
int v=u*p[i];
if (n/v>=m)
{
dfs(v,0,0);
}
else
{
dfs(v,u,sum);
}
if (u%p[i]==0)
{
break;
}
}
}
```
### 三、优秀的dp做法和优化的朴素做法
这两种方法的核心思想是：最优的起点一定大于等于 $\lfloor\frac n 2\rfloor+1$，因为对于 $u\le\lfloor\frac n 2\rfloor$，$f_{2u}=u$，以 $2u$ 为起点一定更优。
所以，可以得到下面的两种做法，压缩空间的核心都是只存一半，另一半直接更新答案而不保存，就不详细讲解了：
### 跑的飞快的dp做法：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10000010;
int n,m,p[N/10],f[N/2],tot,ans;
int main()
{
int i,j,v;
cin>>n>>m;
ans=max(m,n+m-1);
f[1]=m;
for (i=2;i<=n/2;++i)
{
if (!f[i])
{
p[++tot]=i;
if (n/i>=m)
{
f[i]=m*i;
}
else
{
f[i]=f[1]+n/i*(i-1);
}
}
for (j=1;j<=tot&&i*p[j]<=n;++j)
{
v=i*p[j];
if (v<=n/2)
{
if (n/v>=m)
{
f[v]=m*v;
}
else
{
f[v]=f[i]+n/v*(v-i);
}
}
else
{
if (n/v>=m)
{
ans=max(ans,m*v);
}
else
{
ans=max(ans,f[i]+n/v*(v-i));
}
}
if (i%p[j]==0)
{
break;
}
}
}
cout<<ans;
return 0;
}
```
这个dp做法也是 $O(n)$ 的，而且常数比dfs小。但是空间消耗略大一些。
### loglog的做法：
```
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10000010;
int n,m,p[N/10],f[N/2],tot,ans;
int main()
{
int i,j,k,temp;
cin>>n>>m;
ans=max(m,n+m-1);
for (i=2;i<=n/2;++i)
{
if (!f[i])
{
p[++tot]=i;
f[i]=1;
}
for (j=1;j<=tot&&i*p[j]<=n;++j)
{
if (i*p[j]<=n/2)
{
f[i*p[j]]=i;
}
else
{
temp=0;
for (k=i*p[j];;k=(k<=n/2?f[k]:i))
{
if (n/k<m)
{
temp+=n/k*(k-(k<=n/2?f[k]:i));
}
else
{
temp+=m*k;
break;
}
}
ans=max(ans,temp);
}
if (i%p[j]==0)
{
break;
}
}
}
cout<<ans;
return 0;
}
```
P.S. 为什么要加上
> 设现在已经使用了的颜料编号构成的集合为 $A$，若$\ \exists\ i,\ j\notin A,\ i,\ j\in [1,\ n],\ gcd(A,\ i)>gcd(A,\ j)$，那么就不能选择颜料 $j$。
这个限制呢？因为这并不是最优策略，如：`14 7`
按照这个限制，答案是 $27$ ：`12 6 3 9 1 2 4`
实际上，若没有这个限制，答案是 $28$ ：`12 4 8 2 6 10 14`
P.P.S. 造数据的时候没想好..$m$ 都是在 $1$ ~ $n$ 纯随机的，导致最优方案的第一个数大多都是 $2$ 的次幂，以至于@小粉兔 用并不优秀的做法进行数据分治，对于无法通过的点只计算 $2$ 的次幂通过了此题...赛后将会更新数据。事实上这题骗分不太好卡...更新了数据也不会太强吧.大家理解上面两种 $O(n)$ 做法就好。
P.P.P.S. 所以说到底为什么要加上上述限制呢？因为没有这个限制的时候ctr不会复杂度正确的做法..然后有一位julao@zhoutb2333 赛时看掉了这个限制想出了一个非常优秀的做法：
```
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int n,m;
map<pii,ll> f;
ll F(int x,int y){
if(x==1)
return y;
if(f[{x,y}])
return f[{x,y}];
ll ret=0;
for(int i=2,pos;i<=x;i=pos+1)
pos=x/(x/i),ret=max(ret,F(x/i,min(y,x/i))*pos+y-min(y,x/i));
return f[{x,y}]=ret;
}
int main(){
cin>>n>>m;
cout<<F(n,m)<<endl;
return 0;
}
```
## E 绫小路的特别考试
ctr：sooke
tutorial：ouuan
~~彩蛋：绫小路=lxl，非常好地体现了本题的输入格式之dl~~
sooke和ouuan在这道题上总计花费了十几个小时的时间...这道题的数据范围、输入格式、题面描述一改再改，而且良（du）心（liu）的sooke还提出了几个构造方案，于是maker就写了12个..
### 〇、暴力
首先这题有一个比较好想的暴力：对于每对可以传递答案的同学连单向边，然后从每个可以独立作出的同学开始dfs。
这个暴力主要有两个问题：
1. 边数太多，最多可以达到 $O(n^2)$ 的级别。
2. 每次询问都要dfs一次。
下面将分别进行讲解：
### 一、连边
其实对于每个同学，只需要向左右两边最近的能够接收到的同学各连一条边即可。
不妨令当前同学为第 $u$ 位同学，他左边最近的能够接收到他的广播的同学为 $l_u(l_u=\max\{v|v<u,v+d_v\ge u\})$.
若存在比 $l_u$ 更远的一位同学 $p(p<l_u,p+d_p\ge u)$ 能够接收到 $u$ 的广播，那么 $p$ 一定能够接收到 $l_u$ 的广播，而 $l_u$ 又能接收到 $u$ 的广播。
所以，$u$ 向左只用连 $(u,l_u)$ 这条边即可。向右是类似的。一共只要连不到 $2n$ 条边。
~~说得好，怎么实现呢？~~
用一个栈，从左往右扫一遍，如果栈顶无法接收到当前同学的广播就弹出，若栈非空就向栈顶连边，然后将当前同学入栈。然后再从右往左扫一遍就好了。
### 二、单次dfs
> 注：这里的单次dfs不是指只dfs一次，而是指所有的dfs过程总复杂度为 $O(n)$
每次询问的时候dfs的起点都是 $w_i$ 中最大的一些，所以先对 $w_i$ 排序。
~~然后按顺序依次进行dfs就可以啦！~~
停！怎么dfs？怎么回答询问？
从大到小枚举 $x$，每次把 $w_i=x$ 的点作为起点dfs，然后记录每个询问 $x$ 的答案，就可以回答询问啦！
~~你当这题没有修改吗？？？~~
事实上，修改造成的影响只有 $w_c<x$，$w_c\ge x$ 两种，所以分两种情况，$ans[0][x]$ 表示 $w_c<x$ 时询问 $x$ 的答案，$ans[1][x]$ 表示 $w_c\ge x$ 时询问 $x$ 的答案。计算 $ans[0][x]$ 时跳过 $c$，计算 $ans[1][x]$ 时先以 $c$ 为起点dfs再dfs其它点。
总复杂度：$O(n+q)$
~~等等？排序呢？？？~~
$0\le w_i<n$，所以可以用各种 $O(n)$ 排序算法，比如计数排序。
值得注意的是，vector/前向星常数可能较大。由于每个点最多只连两条边，可以用两个数组分别存向左/向右的边。同时最好不要用vector/前向星来作为桶排序的容器。
当然，~~ctr非常良心~~，实测前向星存图+前向星桶排~~只需~~$2.7s$，是可过的。两个数组存图+`std::sort`也只需 $1.8s$。
### 参考代码：
```cpp
#include <cstdio>
#include <cstring>
const int N=2000010;
void dfs(int u);
unsigned long long seed;
int n, m, c, mfq, mind, maxd, k, w[2000001], d[2000001];
int sta[N],top,tot,ans[2][N],l[N],r[N],ord[N],cnt[N];
bool vis[N];
inline int randInt() { seed = 99999989 * seed + 1000000007; return seed >> 33; }
void generate()
{
for (int i = 1; i <= n; i++) { w[i] = randInt() % n; }
for (int i = 1; i <= n; i++) { d[i] = randInt() % (maxd - mind + 1) + mind; }
}
void getOperation(int lastans, int &opt, int &x)
{
if ((0ll + randInt() + lastans) % mfq) { opt = 1; } else { opt = 2; }
x = (0ll + randInt() + lastans) % n;
}
int main()
{
int i,j,lxl;
scanf("%d %d %d", &n, &m, &c);
scanf("%llu %d %d %d %d", &seed, &mind, &maxd, &mfq, &k);
generate();
for (int i = 1; i <= k; i++)
{
int p, t;
scanf("%d %d", &p, &t);
d[p] = t;
}
lxl=w[c];
for (i=1;i<=n;++i) //连边
{
while (top&&sta[top]+d[sta[top]]<i)
{
--top;
}
if (top)
{
l[i]=sta[top];
}
sta[++top]=i;
}
top=0;
for (i=n;i>=1;--i)
{
while (top&&sta[top]-d[sta[top]]>i)
{
--top;
}
if (top)
{
r[i]=sta[top];
}
sta[++top]=i;
}
for (i=1;i<=n;++i) //计数排序
{
++cnt[w[i]];
}
for (i=n-1;i>=0;--i)
{
cnt[i]+=cnt[i+1];
}
for (i=1;i<=n;++i)
{
ord[--cnt[w[i]]]=i;
}
for (i=n-1,j=0;i>=0;--i) //计算ans[0][i]
{
while (j<n&&w[ord[j]]==i)
{
if (ord[j]!=c)
{
dfs(ord[j]);
}
++j;
}
ans[0][i]=tot;
}
tot=0;
memset(vis,false,sizeof(vis));
dfs(c);
for (i=n-1,j=0;i>=0;--i) //计算ans[1][i]
{
while (j<n&&w[ord[j]]==i)
{
if (ord[j]!=c)
{
dfs(ord[j]);
}
++j;
}
ans[1][i]=tot;
}
int lastans = 0, finalans = 0;
for (i = 1; i <= m; i++)
{
int opt, x;
getOperation(lastans, opt, x);
if (opt == 1)
{
finalans = (finalans * 233ll + ans[lxl>=x][x]) % 998244353;
lastans = ans[lxl>=x][x];
}
else
{
lxl=x;
}
}
printf("%d\n", finalans);
return 0;
}
void dfs(int u)
{
if (vis[u]||u==0)
{
return;
}
vis[u]=true;
++tot;
dfs(l[u]);
dfs(r[u]);
}
```
## F 薇尔莉特的打字机
ctr：ouuan
tutorial：sooke & ouuan
~~这题的模数为什么这么奇怪应该不用我解释了~~
一开始辣鸡ctr写了个 $O(n+m*2^{\text{字符集大小}})$ 的辣鸡做法，然后sookejulao想出了一种 $O(n+m)$ （复杂度中的 $n$ 均为读入用时）的优秀做法。然后ctr没听懂sooke的解释，对着代码看了好久才看懂。这题确实比较难讲清楚怎么做，如果下面的题解实在看不懂就对着代码啃吧...
在sooke的强烈要求下，此题的第一个提交（即std）加上了大量注释，实际上此题std只有0.6KB
> 注：在本文中序列加法定义为拼接两个序列成一个序列。如：$\{A,B\}+\{C\}=\{A,B,C\}$
### 一、
首先考虑没有退格的情况，等同于求一个序列的本质不同子序列个数。
把子串 $t_{0..i}$ 看作一个序列，用 $\widetilde{t_{0..i}}$ 代指其所有本质不同的**非空**子序列， $f_i$ 表示其本质不同的非空子序列的总个数。为得到 $f_i$，考虑线性 $dp$ 转移。
在递推过程中，如果 $t_i$ 表示的字母第一次出现，即 $t_{0..i-1}$ 中没有字符与 $t_i$ 相同。此时 $\widetilde{t_{0..i}}$ 分 $3$ 类：
- $1.\ \widetilde{t_{0..i-1}}$，共有 $f_{i-1}$ 个。
- $2.\ \widetilde{t_{0..i-1}} + \{t_i\}$，仍有 $f_{i-1}$ 个。
- $3.\ \widetilde{t_{0..i-1}}$ 不包含空序列，所以第 $2$ 类中不包含 $\{t_i\}$，单独讨论，共有 $1$ 个。
综上所述，若 $t_i$ 第一次出现，$f_i = 2f_{i-1} + 1$。
那万一 $t_i$ 不是第一次出现呢？按照上面的讨论，必定会产生重复的答案。
令 $lst[x]$ 表示字符 $x$ 上一次出现的位置。$\widetilde{t_{0..lst[t_i] - 1}} + \{t_{lst[t_i]}\}$ 与 $\widetilde{t_{0..lst[t_i] - 1}} + \{t_i\}$ 重复，$\{t_{lst[t_i]}\}$ 与 $\{t_i\}$ 重复。所以 $f_i$ 要减去 $f_{lst[t_i]-1}+1$。
为什么仅有这些子序列重复呢？因为重复的解必然以 $t_i$ 结尾，而 $f_{lst[t_i]-1}+1$ 已经包含了 $t_{0..lst[t_i]}$ 这个序列所有以 $t_i$ 结尾的本质不同子序列了（仔细想想就能明白为什么）。
总结一下转移方程：
$f_i=\begin{cases}2f_{i-1}+1\quad(t_i\text{第一次出现})\\2f_{i-1}-f_{lst[t_i]-1}\quad (t_i\text{出现过})\end{cases}$
只要 $O(m)$ 的时间复杂度便可实现以上递推。
### 二、
接着考虑如何处理退格。
打出了一个字母但被之后的退格所删除，无异于打字操作与退格操作都没有进行。所以只用考虑 $\mathrm{u}$ 排在最开头的情况。
当有效的 $\mathrm{u}$ 一共有 $k$ 个时，只用考虑这 $k$ 个 $\mathrm{u}$ 为操作串 $t$ 从左往右数的前 $k$ 个 $\mathrm{u}$ ，这包含了所有答案。
以 $pre[i]$ 表示 $t_{i+1..m-1}$ 第一个不是 $\mathrm{u}$ 的位置。同时，**下文中本质不同的子序列一律不包含 $\mathrm{u}$**。
设第 $k$ 个 $\mathrm{u}$ 的位置为 $p_k$，退 $k$ 次格新增的本质不同子序列包括 $s_{0..n-k-1} + \widetilde{t_{pre[p_k]..m-1}}$，以及 $s_{0..n-k-1}$。我们把目光放到 $\widetilde{t_{pre[p_k]..m-1}}$ 上，如果对于每个 $k$ 都做一次顺推 $dp$，时间复杂度将会退化至 $O(m ^ 2)$。但是，右端点 $m-1$ 始终不变，把顺推转换为倒推即可。
所以，$f_i$ 的意义就变为 $\widetilde{t_{i..m-1}}$ 的总个数，$lst[x]$ 的意义就变为倒推时字符 $x$ 上一次出现的位置。此外，由于退格符 $\mathrm{u}$ 的存在，转移方程中的 $f_{i-1}$ 改为 $f_{pre[i]}$。
于是，我们得到了一个（错误）的算法：
- 倒推，对于每个大写字母计算 $f_i$，对于每个 $\mathrm{u}$ 把答案加上 $f_{pre[p_k]}+1$（加一是因为 $f_{pre[p_k]..m-1}$ 不含 $s_{0..n-k-1}$），最后再加上 $f_{pre[0]}+1$ ( $pre[0]$ 表示 $t_{0..m-1}$ 中第一个非 $\mathrm{u}$ 的位置)
和第一部分类似，若退格所删去的最后一个字符即 $s_{n-k}$ 在 $t_{pre[p_k]..m-1}$ 中出现过，这个算法会产生重复的答案：第 $k$ 个 $\mathrm{u}$ 在原串 $s$ 中删除的字符是 $s_{n-k}$，而在做第 $k - 1$ 个 $\mathrm{u}$ 时，这个字符并不会被删除。想象一下，一旦 $s_{n-k}$ 在 $t_{pre[p_k]..m-1}$ 中出现过，就意味着可以把刚删除的 $s_{n-k}$ 的给打回去，这与做第 $k - 1$ 个 $\mathrm{u}$ 时的情形相同。所以重复计算的本质不同子序列为 $s_{0..n-k}+\widetilde{t_{pre[lst[s_{n-k}]]..m-1}}$ 以及 $s_{0..n-k}$，个数为 $f_{pre[lst[s_{n-k}]]}+1$，计算答案时要将这部分减去。
仅有这些重复的原因同第一部分所述。
需要注意的是，如果 $\mathrm{u}$ 的个数大于 $n$，要忽略最后面的一些 $\mathrm{u}$，只考虑前 $n$ 个。
### 代码
题解写了一大堆..然而代码非常短。
```
#include <iostream>
#include <cstdio>
using namespace std;
const int N=5000010;
const int M=0x125E591;
int uniq(char x); //计算重复
char s[N],t[N];
int n,m,lst[300],pre[N],pos,cnt,f[N],ans; //pos记录当前扫到的最后一个非u的位置，cnt表示还没扫到的u的个数
int main()
{
int i;
scanf("%d%d%s%s",&n,&m,s,t);
for (i=0;i<m;++i)
{
cnt+=t[i]=='u';
}
for (i=m-1;i>=0;--i)
{
if (t[i]!='u')
{
f[i]=(2*f[pre[i]=pos]+uniq(t[i]))%M;
pos=lst[t[i]]=i;
}
else
{
if (n-cnt>=0) //如果u的个数大于n，要忽略最后面的一些u
{
ans=(ans+f[pos]+uniq(s[n-cnt]))%M;
}
--cnt;
}
}
ans=(ans+f[pos]+1)%M;
printf("%d",ans);
return 0;
}
int uniq(char x)
{
return lst[x]?M-f[pre[lst[x]]]:1; //M-f[pre[lst[x]]]就是-f[pre[lst[x]]]，因为是在模意义下运算所以+M
}
```
最后祝大家NOIP2018rp++！