2023.3.6 外培 Day 0 日寄
\(~~~~\) 这天主打的就是一个摆。
\(~~~~\) 上午上车前在看《基督山伯爵》，上了车本性暴露直接拿出电脑开摆。先解了半个多小时baba is you，然后打了把以撒，接下来重头戏ser来了于是就全是ser了。
\(~~~~\) 车上最重要的事就是打了个三级袭击，场面大概是两岸猿声啼不住，以及下图是死亡坐标点：
\(~~~~\) 五彩斑斓的世界了属于是。
\(~~~~\) 然后下午到了酒店出去吃了个饭（说实话到外地没吃特色菜感觉有点？？？来点热干面也不是不行），然后对这顿中式快餐的评价是：不如乡村基。
\(~~~~\) 晚上回去继续摆ser，然后 Rainybunny 这边炸脖龙解放末地，crashed 这边搞了个（半）自动农场，我这边造了个刷怪塔来支持杂七杂八东西的消耗，造完时间不早了没做效率测试。
2023.3.7 外培 Day 1 日寄
模拟赛
递归函数
题意
\(~~~~\) 定义 \(F(n,m)\)，当 \(n=0\) 时 \(F(n,m)=1\)，当 \(m=0\) 时 \(F(n,m)=n\)，否则 \(F(n,m)=F(n-1,m)\times F(n,m-1)\).求 \(F(n,m)\) 在 \(b\) 进制下末尾 \(0\) 的个数对质数 \(998444353\) 取模。
\(~~~~\) \(1\leq n\leq 10^9,1\leq m\leq 16,1\leq b\leq 10\).
题解
\(~~~~\) 怎么办呢，坐牢了呢。
\(~~~~\) 注意到答案也就是求最后的结果可以表示成多少个 \(b\) 的积，当然当 \(b\) 为素数时直接看这个素数的指数，否则看 \(b\) 的最大质因子（针对 \(6,10\)）。而当某个质因子指数不为 \(1\) 的时候（针对 \(4,8,9\)） 那发现最后答案是这个除以指数取下整，那为了实现取下整维护结果 \(\bmod~k\times 998444353\) 即可。\(k\) 显然小于等于 \(3\) ，所以可以存。
\(~~~~\) 那么枚举 \(i,j\) 得到 \(p^i\times j\) ，其中 \(p\) 为最大的质因子，我们发现只有 \(F(p^i\times j,0)\) 会产生这个数，所以我们就是求有多少个 \(F(p^i\times j,0)\) 会被计算，显然这是一个在两维上走路的问题，注意到最后一步必须是 \(F(p^i\times j,1) \rightarrow F(p^i\times j,0)\) ，所以是 \(\binom{n-p^i\times j+m-1}{m-1}\) ，不过很显然这个东西不能快速计算。
\(~~~~\) 考虑组合数的递推：\(\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}\) 这是一个线性递推，而且我们是存的下的，所以我们考虑用矩阵快速幂算出每个倍数结果。而指数就直接枚举即可。
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
ll n,m,b,Ans,MOD=998444353;
struct Matrix
{
ll a[20][20];
Matrix(){memset(a,0,sizeof(a));}
}E,Trans,lst;
Matrix operator*(const Matrix &A,const Matrix &B)
{
Matrix res;
for(ll i=0;i<=m;i++)
for(ll j=0;j<=m;j++)
for(ll k=0;k<=m;k++)
res.a[i][k]=(res.a[i][k]+A.a[i][j]*B.a[j][k])%MOD;
return res;
}
void Solve()
{
for(ll i=0;i<=m;i++) E.a[i][i]=1;
Trans.a[0][0]=1;
for(ll i=1;i<=m;i++)
for(ll j=i;j<=m;j++) Trans.a[i][j]=1;
Matrix mul=Trans,add=E;
add.a[0][1]=1;
for(ll p=n;p>0;p/=b)
{
Matrix Tmp=Trans;
for(ll i=1;i<b;i++) Trans=Trans*Tmp;
Matrix Base=Trans*add,res=E;
ll s=p/b;
while(s)
{
if(s&1) res=res*Base;
Base=Base*Base,s>>=1;
}
for(ll i=0;i<p%b;i++) mul=mul*Tmp;
res=res*mul;
Ans=(Ans+res.a[0][m])%MOD;
}
}
int main() {
freopen("function.in","r",stdin);
freopen("function.out","w",stdout);
read(n);read(m);read(b);ll Div=1;
if(b==6) b=3;
if(b==10) b=5;
if(b==4) b=2,MOD*=2,Div=2;
if(b==9) b=3,MOD*=2,Div=2;
if(b==8) b=2,MOD*=3,Div=3;
Solve();
printf("%lld",Ans/Div);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
*/
火力规划 / 「CF575I」 Robots protection
题意
\(~~~~\) \(q\) 次询问，每次覆盖一个点某四分之一个曼哈顿距离圆，或者查询一个点被多少四分之一圆覆盖。保证被覆盖的区域横纵坐标都在 \([1,n]\) 之中。
\(~~~~\) \(1\leq n\leq 1000,1\leq q\leq 10^5\).
题解
\(~~~~\) 这题评分只有 \(\text{2800}\) /jk
\(~~~~\) 首先注意到通过坐标变换，四种四分之一曼哈顿圆都可以看做一种来处理，我们就只考虑向左下的那一个。
\(~~~~\) 如图，紫红色的那个就是需要覆盖的区域，那么我们可以看做黄色和紫红色整个减去两个紫红色部分的值。
\(~~~~\) 两个部分的并是一个一维区间和问题，那直接用BIT维护即可。
\(~~~~\) 重点在于两个部分的值，我们发现我们可以把黄色部分看做平行四边形。（如果在方框里“看起来”不是你也可以把他拓展成平行四边形，因为四周反正不影响）具体来说记平行四边形内点变换后的坐标 \((x',y')\) 那我们一定有 \(x'+y'\in [x+y-r,x+y]\)，并且两个部分分别为 \(x'<x\) 或 \(y'<y\) 。
\(~~~~\) 那么两个部分分别有两个维上的限制，那用两个二维BIT维护即可。
代码
查看代码
#include <bits/stdc++.h>
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
struct node{
int op,dir,x,y,r;
}Q[100005];
int n,q;
struct BIT{
int tr[2][5005][10005];
inline int lowbit(int x){return x&(-x);}
void Add(int x,int Y,int op,int val)
{
for(;x<=n;x+=lowbit(x))
for(int y=Y;y<=2*n;y+=lowbit(y)) tr[op][x][y]+=val;
}
int Query(int x,int Y,int op)
{
int ret=0;
for(;x;x-=lowbit(x))
for(int y=Y;y;y-=lowbit(y)) ret+=tr[op][x][y];
return ret;
}
void Clear(){memset(tr,0,sizeof(tr));}
}BIT;
int Ans[100005];
int main() {
// freopen("planning.in","r",stdin);
// freopen("planning.out","w",stdout);
read(n);read(q);
for(int qwq=1;qwq<=q;qwq++)
{
read(Q[qwq].op);
if(Q[qwq].op==1)
{
read(Q[qwq].dir),read(Q[qwq].x),read(Q[qwq].y),read(Q[qwq].r);
if(Q[qwq].dir==4) Q[qwq].dir=1; else if(Q[qwq].dir==3) Q[qwq].dir=2;
else if(Q[qwq].dir==1) Q[qwq].dir=3; else if(Q[qwq].dir==2) Q[qwq].dir=4;
}
else read(Q[qwq].x),read(Q[qwq].y);
}
for(int d=1;d<=4;d++)
{
BIT.Clear();
for(int i=1;i<=q;i++)
{
if(Q[i].op==1&&Q[i].dir==d)
{
int X=Q[i].x,Y=Q[i].y,R=Q[i].r;
BIT.Add(X-R,X+Y-R,0,1); BIT.Add(X+1,X+Y-R,0,-1);
BIT.Add(X-R,Y+1,1,-1); BIT.Add(X+1,Y+1,1,1);
}
else if(Q[i].op==2)
{
int X=Q[i].x,Y=Q[i].y;
Ans[i]+=BIT.Query(X,X+Y,0);
Ans[i]+=BIT.Query(X,Y,1);
}
}
for(int i=1;i<=q;i++) swap(Q[i].x,Q[i].y),Q[i].x=n+1-Q[i].x;
}
for(int i=1;i<=q;i++) if(Q[i].op==2) printf("%d\n",Ans[i]);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
曼哈顿转切比雪夫，可以先维护行的前缀和
以dir=1为例：
维护列的前缀和
然后就是维护每一行和列的前后缀和
打差分维护二维前缀和
等等哦，开不下欸
那就不转切比雪夫直接来
*/
再生核希尔伯特空间
题意
\(~~~~\) 给出 \(n\) 个字符串，\(q\) 次询问 \([l,r]\) 内的字符串在 \(s_k\) 内共出现了几次。
\(~~~~\) \(1\leq n\leq 2\times 10^5,1\leq \sum |s_i|\leq 2\times 10^5\).
题解
\(~~~~\) 对于这种题，带佬教我：看到这种数据范围就想根号分治/阈值分治。（不过我很怀疑难道不是有了两种做法就开始想这个吗）
\(~~~~\) 那我们先想一些暴力的做法，比如说：如果我们建出AC自动机，那么对于 \(s_k\) 我们将 \(s_k\) 一路上的结点的值都加上 \(1\)。那么对于询问 \([l,r]\) ，实际就是询问 \([l,r]\) 内的字符串在 \(\text{fail}\) 树上的结尾点子树和。当 \(|s_k|\) 非常大的时候这样的询问就很少，我们直接做 \(\mathcal{O(n)}\) 即可。
\(~~~~\) 另一个暴力的想法是降低插入的复杂度。我们求解 \([1,l]\) 的字符串在 \(s_k\) 中出现多少次.插入串的时候我们就把这个串结束结点在 \(\text{fail}\) 树上的子树全部 \(+1\) ，而查询就只能暴力累加 Trie 树上 \(s_k\) 的结束点所有祖先的值。当 \(|s_k|\) 非常小的时候单次复杂度就很优。
\(~~~~\) 具体来说，我们认为当 \(|s_k|>B\) 时采用第一种做法，否则采用第二种做法。记 \(m=\sum_{i=1}^n |s_i|\) 那么复杂度是：\(\mathcal{O(\frac{m^2}{B}+qB\log m)}\) ，那么用均值不等式，得到 \(B=\frac{m}{\sqrt{q \log m}}\)
代码
查看代码
#include <bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define mp(a,b) make_pair(a,b)
using namespace std;
template<typename T>void read(T &x)
{
T f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
x*=f;
}
ll L[200005],R[200005],Ans[200005];
char S[200005],Tmp[200005];
vector <ll> G[2000005];
vector <PII> Q[2000005];
struct AC_Machine{
ll ch[200005][27],tot,End[200005],fail[200005];
AC_Machine(){tot=0;}
void Insert(ll l,ll r,ll id)
{
ll now=0;
for(ll i=l;i<=r;i++)
{
ll To=S[i]-'a'+1;
if(!ch[now][To]) ch[now][To]=++tot;
now=ch[now][To];
}
End[id]=now;
}
void GetFail()
{
queue<ll>QQ;
for(ll i=1;i<=26;i++) if(ch[0][i]) QQ.push(ch[0][i]);
while(!QQ.empty())
{
ll u=QQ.front();QQ.pop();
for(ll i=1;i<=26;i++)
{
if(ch[u][i]) fail[ch[u][i]]=ch[fail[u]][i],QQ.push(ch[u][i]);
else ch[u][i]=ch[fail[u]][i];
}
}
}
}AC;
ll In[200005],Out[200005],Times,Sum[200005],Sum2[200005];
void dfs(ll u)
{
In[u]=++Times;
for(ll i=0;i<(ll)G[u].size();i++) dfs(G[u][i]);
Out[u]=Times;
}
struct Ask{
ll l,r,k;
}A[200005];
struct BIT{
ll tr[200005];
inline ll lowbit(ll x){return x&(-x);}
inline void Add(ll x,ll Val){for(;x<=AC.tot+1;x+=lowbit(x)) tr[x]+=Val;}
inline ll Query(ll x){ll ret=0;for(;x;x-=lowbit(x)) ret+=tr[x];return ret;}
}BIT;
bool cmp(ll x,ll y){return A[x].k<A[y].k;}
int main() {
// freopen("rkhs.in","r",stdin);
// freopen("rkhs.out","w",stdout);
ll n,m;read(n);read(m);
for(ll i=1;i<=n;i++)
{
scanf("%s",Tmp+1);
ll len=strlen(Tmp+1);
L[i]=R[i-1]+1; R[i]=L[i]+len-1;
for(ll j=L[i];j<=R[i];j++) S[j]=Tmp[j-L[i]+1];
AC.Insert(L[i],R[i],i);
}
AC.GetFail();
ll B=(ll)R[n]/sqrt(m*log(R[n])/log(2));
for(ll i=1;i<=AC.tot;i++) G[AC.fail[i]].push_back(i);dfs(0);
for(ll i=0;i<=AC.tot;i++) reverse(G[i].begin(),G[i].end());
vector<ll>F;//Big enourh to do force method.
for(ll i=1,l,r,k;i<=m;i++)
{
read(l);read(r);read(k);
A[i].l=l; A[i].r=r; A[i].k=k;
if(R[k]-L[k]+1>B) F.push_back(i);
else Q[l-1].push_back(mp(i,-1)),Q[r].push_back(mp(i,1));
}
sort(F.begin(),F.end(),cmp);
for(ll i=0;i<(ll)F.size();i++)
{
if(i==0||A[F[i]].k!=A[F[i-1]].k)
{
ll id=A[F[i]].k,now=0;
memset(Sum,0,sizeof(Sum));
memset(Sum2,0,sizeof(Sum2));
for(ll j=L[id];j<=R[id];j++) now=AC.ch[now][S[j]-'a'+1],Sum[In[now]]++;
for(ll j=1;j<=AC.tot+1;j++) Sum[j]+=Sum[j-1];
for(ll j=1;j<=n;j++)
Sum2[j]=Sum2[j-1]+Sum[Out[AC.End[j]]]-Sum[In[AC.End[j]]-1];
}
Ans[F[i]]=Sum2[A[F[i]].r]-Sum2[A[F[i]].l-1];
}
for(ll i=1;i<=n;i++)
{
BIT.Add(In[AC.End[i]],1); BIT.Add(Out[AC.End[i]]+1,-1);
for(ll j=0;j<(ll)Q[i].size();j++)
{
ll id=Q[i][j].first,Mul=Q[i][j].second,now=0;
ll ret=0;
for(ll k=L[A[id].k];k<=R[A[id].k];k++) now=AC.ch[now][S[k]-'a'+1],ret+=BIT.Query(In[now]);
Ans[id]+=ret*Mul;
}
}
for(ll i=1;i<=m;i++) printf("%lld\n",Ans[i]);
return 0;
}
/*
瑶草一何碧，春入武陵溪。溪上桃花无数，花上有黄鹂。我欲穿花寻路，直入白云深处，浩气展虹霓。只恐花深里，红露湿人衣。
坐玉石，欹玉枕。拂金徽。谪仙何处，无人伴我白螺杯。我为灵芝仙草，不为朱唇丹脸，长啸亦何为。醉舞下山去，明月逐人归。
16 1
t
h
dvawooggk
ztqlqgvhzikkynxgbohjcptimzuothen
r
ucqy
rieye
eyklxwlvea
tf
h
chhvhhqro
uhymlqtrxpagbmn
j
hmo
hlzqe
k
6 14 4
*/