每周好题分享

2025/3/18 OI 题解

第一周（2025/03/17~2025/03/23）

T1

P7671 [GDOI2016] 疯狂动物城

Solution

省流：推式子+树剖+主席树。

对于操作一，直接树剖后即可解决。
对于操作三，写主席树维护即可。
操作二的话，推式子就可以了。

\[ \begin{aligned} &\sum_{i\in S(x,y)}\sum_{j=1}^{dis(i,y)}a_{i}\cdot j\\ =&\sum_{i\in S(x,y)}a_{i}\frac{dis(i,y)^{2}+dis(i,y)}{2}\\ =&\sum_{i\in S(x,y)}a_{i}\frac{(dep_{i}+dep_{y}-2dep_{\operatorname{LCA}(i,y)})^{2}+(dep_{i}+dep_{y}-2dep_{\operatorname{LCA}(i,y)})}{2}\\ =&\sum_{i\in S(x,y)}a_{i}\frac{dep^{2}_{i}+dep^{2}_{y}+2dep_{i}dep_{y}+4dep^{2}_{\operatorname{LCA}(i,y)}-4dep_{\operatorname{LCA}(i,y)}dep_{i}-4dep_{\operatorname{LCA}(i,y)}dep_{y}+dep_{i}+dep_{y}-2dep_{\operatorname{LCA}(i,y)}}{2}\\ =&\sum_{i\in S(x,y)}a_{i}\left(\frac{dep^{2}_{i}+dep_{i}}{2}+\frac{dep^{2}_{y}+2dep_{i}dep_{y}+dep_{y}}{2}+2dep^{2}_{\operatorname{LCA}(i,y)}-dep_{\operatorname{LCA}(i,y)}-2dep_{\operatorname{LCA}(i,y)}(dep_{i}+dep_{y})\right)\\ =&\sum_{i\in S(x,y)}a_{i}\frac{dep^{2}_{i}+dep_{i}}{2}+\sum_{i\in S(x,y)}a_{i}\frac{dep^{2}_{y}+dep_{y}}{2}+\sum_{i\in S(x,y)}a_{i}dep_{i}dep_{y}+\sum_{i\in S(x,y)}a_{i}(2dep^{2}_{\operatorname{LCA}(i,y)}-dep_{\operatorname{LCA}(i,y)})-\sum_{i\in S(x,y)}2a_{i}dep_{\operatorname{LCA}(i,y)}(dep_{i}+dep_{y})\\ +&\sum_{i\in S(x,y)}a_{i}\frac{dep^{2}_{i}+dep_{i}}{2}\\ +&\sum_{i\in S(x,y)}a_{i}\frac{dep^{2}_{y}+dep_{y}}{2}=\frac{dep^{2}_{y}+dep_{y}}{2}\sum_{i\in S(x,y)}a_{i}\\ +&\sum_{i\in S(x,y)}a_{i}dep_{i}dep_{y}=dep_{y}\sum_{i\in S(x,y)}a_{i}dep_{i}\\ +&\sum_{i\in S(x,y)}a_{i}(2dep^{2}_{\operatorname{LCA}(i,y)}-dep_{\operatorname{LCA}(i,y)})=(2dep_{\operatorname{LCA}(x,y)}^{2}-dep_{\operatorname{LCA}(x,y)})\sum_{i\in S(x,\operatorname{LCA}(x,y))}a_{i}+\sum_{i\in S(\operatorname{LCA}(x,y),y)}a_{i}(2dep_{i}^{2}-dep_{i})-a_{\operatorname{LCA}(x,y)}(2dep_{\operatorname{LCA}(x,y)}^{2}-dep_{\operatorname{LCA}(x,y)})\\ -&\sum_{i\in S(x,y)}2a_{i}dep_{\operatorname{LCA}(i,y)}(dep_{i}+dep_{y})=\sum_{i\in S(x,\operatorname{LCA}(x,y))}2a_{i}dep_{\operatorname{LCA}(x,y)}(dep_{i}+dep_{y})+\sum_{i\in S(\operatorname{LCA}(x,y),y)}2a_{i}dep_{i}(dep_{i}+dep_{y})-2a_{\operatorname{LCA}(x,y)}dep_{\operatorname{LCA}(x,y)}(dep_{\operatorname{LCA}(x,y)}+dep_{y})\\ &\sum_{i\in S(x,\operatorname{LCA}(x,y))}2a_{i}dep_{\operatorname{LCA}(x,y)}(dep_{i}+dep_{y})=2dep_{\operatorname{LCA}(x,y)}\sum_{i\in S(x,\operatorname{LCA}(x,y))}a_{i}dep_{i}+2dep_{\operatorname{LCA}(x,y)}dep_{y}\sum_{i\in S(x,\operatorname{LCA}(x,y))}a_{i}\\ &\sum_{i\in S(\operatorname{LCA}(x,y),y)}2a_{i}dep_{i}(dep_{i}+dep_{y})=2\sum_{i\in S(\operatorname{LCA}(x,y),y)}a_{i}dep_{i}^{2}+2dep_{y}\sum_{i\in S(\operatorname{LCA}(x,y),y)}a_{i}dep_{i}\\ \end{aligned} \] 维护： \[ \sum dep_{i}\\ \sum dep_{i}^{2}\\ \sum a_{i}\\ \sum a_{i}dep_{i}\\ \sum a_{i}dep_{i}^{2}\\ \]

照着式子维护就好了。
一般的主席树是单点改，这里区间改的话，挨着挨着改显然会 TLE，我们把区间先留下来，要 pushdown 的时候，新建一下儿子节点就好了。

（似乎有相对简单的做法，但我觉得我这样拆的方法更通用一点？比如这道题）

注意：在极限数据下，我的代码会 RE，但其实可以优化一下，懒的改了）

代码

// Problem: P7671 [GDOI2016] 疯狂动物城
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7671
// Memory Limit: 2 GB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod=20160501;
const int inv2=10080251;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

bool awa;
int n,m,k,q,lastans,qcnt,cnt,tree_cnt,idq[MAXN],root[MAXN],head[MAXN],siz[MAXN],dep[MAXN],hson[MAXN],top[MAXN],dfsnum[MAXN],dfsnod[MAXN],fa[MAXN],a[MAXN];
struct node{
    int to,next;
}edge[MAXN<<1];
struct node2{
    int id,l,r,lson,rson,val1,val2,val3,val4,val5,lazy;
}tree[MAXN*200];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void dfs(int u,int f){
    siz[u]=1;
    int maxsiz=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==f) continue;
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs(v,u);
        siz[u]+=siz[v];
        if(maxsiz<siz[v]){
            maxsiz=siz[v];
            hson[u]=v;
        }
    }
}

void dfs2(int u,int f){
    top[u]=f;
    dfsnum[u]=++cnt;
    dfsnod[cnt]=u;
    if(hson[u]==0) return;
    dfs2(hson[u],f);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[u]||v==hson[u]) continue;
        dfs2(v,v);
    }
}

void newnode(int l,int r,int ID){
    int id=++tree_cnt;
    tree[id].id=ID;
    tree[id].l=l;
    tree[id].r=r;
}

void pushup(int id){
    tree[id].val1=tree[tree[id].lson].val1+tree[tree[id].rson].val1;
    tree[id].val2=tree[tree[id].lson].val2+tree[tree[id].rson].val2;
    tree[id].val3=tree[tree[id].lson].val3+tree[tree[id].rson].val3;
    tree[id].val4=tree[tree[id].lson].val4+tree[tree[id].rson].val4;
    tree[id].val5=tree[tree[id].lson].val5+tree[tree[id].rson].val5;
    tree[id].val1-=tree[id].val1>=mod?mod:0;
    tree[id].val2-=tree[id].val2>=mod?mod:0;
    tree[id].val3-=tree[id].val3>=mod?mod:0;
    tree[id].val4-=tree[id].val4>=mod?mod:0;
    tree[id].val5-=tree[id].val5>=mod?mod:0;
}

void pushdown(int id){
    if(tree[id].lazy==0) return;
    tree[tree[id].lson].val3+=(tree[tree[id].lson].r-tree[tree[id].lson].l+1)*(tree[id].lazy%mod)%mod;
    tree[tree[id].lson].val4+=tree[tree[id].lson].val1*(tree[id].lazy%mod)%mod;
    tree[tree[id].lson].val5+=tree[tree[id].lson].val2*(tree[id].lazy%mod)%mod;
    tree[tree[id].lson].val3-=tree[tree[id].lson].val3>=mod?mod:0;
    tree[tree[id].lson].val4-=tree[tree[id].lson].val4>=mod?mod:0;
    tree[tree[id].lson].val5-=tree[tree[id].lson].val5>=mod?mod:0;
    tree[tree[id].lson].lazy+=tree[id].lazy;
    tree[tree[id].rson].val3+=(tree[tree[id].rson].r-tree[tree[id].rson].l+1)*(tree[id].lazy%mod)%mod;
    tree[tree[id].rson].val4+=tree[tree[id].rson].val1*(tree[id].lazy%mod)%mod;
    tree[tree[id].rson].val5+=tree[tree[id].rson].val2*(tree[id].lazy%mod)%mod;
    tree[tree[id].rson].val3-=tree[tree[id].rson].val3>=mod?mod:0;
    tree[tree[id].rson].val4-=tree[tree[id].rson].val4>=mod?mod:0;
    tree[tree[id].rson].val5-=tree[tree[id].rson].val5>=mod?mod:0;
    tree[tree[id].rson].lazy+=tree[id].lazy;
    tree[id].lazy=0;
}

void build_tree(int ID,int id,int l,int r){
    if(l==r){
        tree[id].val1=dep[dfsnod[l]];
        tree[id].val2=dep[dfsnod[l]]*dep[dfsnod[l]]%mod;
        tree[id].val3=a[dfsnod[l]];
        tree[id].val4=a[dfsnod[l]]*tree[id].val1%mod;
        tree[id].val5=a[dfsnod[l]]*tree[id].val2%mod;
        return;
    }
    int mid=(l+r)>>1;
    newnode(l,mid,ID);
    tree[id].lson=tree_cnt;
    build_tree(ID,tree[id].lson,l,mid);
    newnode(mid+1,r,ID);
    tree[id].rson=tree_cnt;
    build_tree(ID,tree[id].rson,mid+1,r);
    pushup(id);
}

void update(int ID,int last,int id,int l,int r,int L,int R,int val){
    if(r<L||R<l) return;
    if(L<=l&&r<=R){
        tree[id].val3+=(r-l+1)*val%mod;
        tree[id].val4+=tree[id].val1*val%mod;
        tree[id].val5+=tree[id].val2*val%mod;
        tree[id].val3-=tree[id].val3>=mod?mod:0;
        tree[id].val4-=tree[id].val4>=mod?mod:0;
        tree[id].val5-=tree[id].val5>=mod?mod:0;
        tree[id].lazy+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(tree[tree[id].lson].id!=ID){
        newnode(l,mid,ID);
        tree[tree_cnt]=tree[tree[id].lson];
        tree[tree_cnt].id=ID;
        tree[id].lson=tree_cnt;
    }
    if(tree[tree[id].rson].id!=ID){
        newnode(mid+1,r,ID);
        tree[tree_cnt]=tree[tree[id].rson];
        tree[tree_cnt].id=ID;
        tree[id].rson=tree_cnt;
    }
    pushdown(id);
    if(L<=mid) update(ID,tree[last].lson,tree[id].lson,l,mid,L,R,val);
    if(R>mid) update(ID,tree[last].rson,tree[id].rson,mid+1,r,L,R,val);
    pushup(id);
}

void change(int ID,int last,int rt,int u,int v,int val){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        update(ID,last,rt,1,cnt,dfsnum[top[u]],dfsnum[u],val);
        // int pos=u;
        // while(pos!=fa[top[u]]){
            // update(ID,last,rt,1,cnt,dfsnum[pos],dfsnum[pos],val);
            // pos=fa[pos]; 
        // }
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    // int pos=u;
    // while(pos!=fa[v]){
        // update(ID,last,rt,1,cnt,dfsnum[pos],dfsnum[pos],val);
        // pos=fa[pos]; 
    // }
    update(ID,last,rt,1,cnt,dfsnum[v],dfsnum[u],val);
}

int query(int id,int l,int r,int L,int R,int type){
    if(id==0||r<L||R<l) return 0;
    if(L<=l&&r<=R){
        if(type==1) return tree[id].val1;
        if(type==2) return tree[id].val2;
        if(type==3) return tree[id].val3;
        if(type==4) return tree[id].val4;
        if(type==5) return tree[id].val5;
    }
    int res=0,mid=(l+r)>>1;
    if(tree[tree[id].lson].id!=tree[id].id){
        newnode(l,mid,tree[id].id);
        tree[tree_cnt]=tree[tree[id].lson];
        tree[tree_cnt].id=tree[id].id;
        tree[id].lson=tree_cnt;
    }
    if(tree[tree[id].rson].id!=tree[id].id){
        newnode(mid+1,r,tree[id].id);
        tree[tree_cnt]=tree[tree[id].rson];
        tree[tree_cnt].id=tree[id].id;
        tree[id].rson=tree_cnt;
    }
    pushdown(id);
    if(L<=mid&&tree[id].lson){
        int val=query(tree[id].lson,l,mid,L,R,type);
        res+=val;
        res-=res>=mod?mod:0;
    }
    if(R>mid&&tree[id].rson){
        int val=query(tree[id].rson,mid+1,r,L,R,type);
        res+=val;
        res-=res>=mod?mod:0;
    }
    return res;
}

int ask(int rt,int u,int v,int type){
    int res=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        res+=query(rt,1,cnt,dfsnum[top[u]],dfsnum[u],type);
        res-=res>=mod?mod:0;
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    res+=query(rt,1,cnt,dfsnum[v],dfsnum[u],type);
    res-=res>=mod?mod:0;
    return res;
}

int lca(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]<dep[v]) swap(u,v);
    return v;
}

int work(int rt,int u,int v){
    int res=((ask(rt,u,v,4)+ask(rt,u,v,5))*inv2)%mod,lc=lca(u,v);
    res+=((dep[v]*dep[v]+dep[v])*inv2)%mod*ask(rt,u,v,3)%mod;
    res-=res>=mod?mod:0;
    res+=dep[v]*ask(rt,u,v,4)%mod;
    res-=res>=mod?mod:0;
    res+=(2ll*dep[lc]*dep[lc]%mod-dep[lc]+mod)%mod*ask(rt,u,lc,3)%mod;
    res-=res>=mod?mod:0;
    res+=(2ll*ask(rt,lc,v,5)%mod-ask(rt,lc,v,4)+mod)%mod;
    res-=res>=mod?mod:0;
    res-=(2ll*dep[lc]*dep[lc]%mod-dep[lc]+mod)%mod*ask(rt,lc,lc,3)%mod;
    res+=res<0?mod:0;
    res-=(2ll*dep[lc]*ask(rt,u,lc,4)%mod+2ll*dep[lc]*dep[v]%mod*ask(rt,u,lc,3)%mod)%mod;
    res+=res<0?mod:0;
    res-=(2ll*ask(rt,lc,v,5)%mod+2ll*dep[v]*ask(rt,lc,v,4)%mod)%mod;
    res+=res<0?mod:0;
    res+=2ll*ask(rt,lc,lc,3)%mod*dep[lc]%mod*(dep[lc]+dep[v])%mod;
    res-=res>=mod?mod:0;
    return res;
}

bool qwq;

signed main(){
    // cout<<(&awa-&qwq)/1024.0/1024.0<<endl;
    read(n,m);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        build(u,v);
        build(v,u);
    }
    for(int i=1;i<=n;i++) read(a[i]);
    dfs(1,1);
    dfs2(1,1);
    idq[0]=0;
    newnode(1,cnt,0);
    root[0]=tree_cnt;
    build_tree(0,root[0],1,cnt);
    for(int i=1;i<=m;i++){
        int opt,x,y,w;
        read(opt);
        if(opt==1){
            read(x,y,w);
            x=x^lastans;
            y=y^lastans;
            idq[++qcnt]=i;
            newnode(1,cnt,i);
            root[i]=tree_cnt;
            tree[root[i]]=tree[root[i-1]];
            tree[root[i]].id=i;
            change(i,root[i-1],root[i],x,y,w);
        }
        if(opt==2){
            read(x,y);
            x=x^lastans;
            y=y^lastans;
            root[i]=root[i-1];
            lastans=work(root[i],x,y);
            cout<<lastans<<'\n';
        }
        if(opt==3){
            read(x);
            x=x^lastans;
            root[i]=root[idq[x]];
        }
        // for(int j=1;j<=n;j++) cout<<query(root[i],1,cnt,dfsnum[j],dfsnum[j],3)<<" ";
        // cout<<endl;
    }
    return 0;
}

T2

P2387 [NOI2014] 魔法森林

Solution

虽然大部分人还不会 LCT（也可以看看我的博客，我觉得写得挺清楚的qwq），但可以先不管，总之就是可以在 \(O(\log n)\) 的时间内连边和断边就行了，思考一下怎么维护这道题需要的就可以了。
如果见过类似的题那其实很简单，可能有人很快就秒了。

这题相对于一般的维护链上最大值，变成了两种权值各自的最大值后相加的结果。
首先可以按照任意一种权值排序，这样的话，只需要看另一种权值就可以了。
设当前考虑的边的两端点为 \(u\) 和 \(v\)，两个权值分别为 \(a_{i}\) 和 \(b_{i}\)，类似于 P4172 [WC2006] 水管局长，以及严格最小生成树以及 kruskal 算法，我们贪心地进行加边，分三种情况考虑：

\(u\) 和 \(v\) 尚未联通，显然先连起来，因为如果后面有更优的，是可以把这条边替换掉的。
\(u\) 和 \(v\) 已经联通了，但 \(1\) 和 \(n\) 还没有联通。那说明权值小于 \(a_{i}\) 的边没法生成一颗树。那么此时，我们去找 \(u\) 到 \(v\) 路径上 \(b_{j}\) 最大的边，如果 \(b_{i}<b_{j}\)，那么我们把原来的那条边删掉，把新的边连起来，绝对是当前最优的。
\(u\) 和 \(v\) 已经联通了，且 \(1\) 和 \(n\) 也是联通的。那么我们现在已经求出了权值小于 \(a_{i}\) 的所有边的最小的答案，那么此时和上面一样，找最大的边，如果 \(b_{i}<b_{j}\)，把原来的那条边删掉，把新的边连起来，这样可以得到边权小于等于 \(a_{i}\) 的最小答案。

那么就结束了。

代码

// Problem: P2387 [NOI2014] 魔法森林
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2387
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans=-1,fa[MAXN],maxa[MAXN],maxb[MAXN],a[MAXN],b[MAXN],ida[MAXN],idb[MAXN],son[MAXN][2],tag[MAXN];
struct node{
    int maxa,maxb,ida,idb;
};
struct node2{
    int u,v,a,b;
}e[MAXN];

bool get(int x){return x==son[fa[x]][1];}
bool isroot(int x){return x!=son[fa[x]][0]&&x!=son[fa[x]][1];}
void rev(int x){swap(son[x][0],son[x][1]);tag[x]^=1;}

void pushup(int x){
    if(maxa[son[x][0]]>maxa[son[x][1]]){
        maxa[x]=maxa[son[x][0]];
        ida[x]=ida[son[x][0]];
    }
    else{
        maxa[x]=maxa[son[x][1]];
        ida[x]=ida[son[x][1]];
    }
    if(a[x]>maxa[x]){
        maxa[x]=a[x];
        ida[x]=x;
    }
    if(maxb[son[x][0]]>maxb[son[x][1]]){
        maxb[x]=maxb[son[x][0]];
        idb[x]=idb[son[x][0]];
    }
    else{
        maxb[x]=maxb[son[x][1]];
        idb[x]=idb[son[x][1]];
    }
    if(b[x]>maxb[x]){
        maxb[x]=b[x];
        idb[x]=x;
    }
}

void pushdown(int x){
    if(tag[x]){
        if(son[x][0]) rev(son[x][0]);
        if(son[x][1]) rev(son[x][1]);
        tag[x]=0;
    }
}

void update(int x){
    if(!isroot(x)) update(fa[x]);
    pushdown(x);
}

void rotate(int x){
    int y=fa[x],z=fa[y],ch=get(x);
    if(!isroot(y)) son[z][get(y)]=x;
    son[y][ch]=son[x][ch^1];
    if(son[x][ch^1]) fa[son[x][ch^1]]=y;
    son[x][ch^1]=y;
    fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}

void Splay(int x){
    update(x);
    for(int f=fa[x];!isroot(x);f=fa[x]){
        if(!isroot(f)) rotate(get(x)==get(f)?f:x);
        rotate(x);
    }
}

int access(int x){
    int pos=0;
    for(;x;pos=x,x=fa[x]) Splay(x),son[x][1]=pos,pushup(x);
    pushup(x);return pos;
}

void makeroot(int x){x=access(x);Splay(x);rev(x);}

int findroot(int x){
    access(x);Splay(x);pushdown(x);
    while(son[x][0]) x=son[x][0],pushdown(x);
    Splay(x);return x;
}

void link(int x,int y){
    makeroot(x);Splay(x);
    if(findroot(y)!=x) fa[x]=y;
}

void cut(int x,int y){makeroot(x);access(y);fa[y]=son[x][1]=0;}
void split(int x,int y){makeroot(x);access(y);Splay(y);}
node query(int x,int y){split(x,y);return (node){maxa[y],maxb[y],ida[y],idb[y]};}

void Link(int x,int y,int w1,int w2,int id){
    makeroot(x);Splay(x);
    if(findroot(y)!=x) link(x,id+n),link(id+n,y);
    else{
        node now=query(x,y);
        if(w2<=now.maxb){
            cut(e[now.idb-n].u,now.idb),cut(now.idb,e[now.idb-n].v);
            link(x,id+n),link(id+n,y);
        }
    }
    makeroot(1);
    node now=query(1,n);
    if(findroot(n)==1) ans=ans==-1?now.maxa+now.maxb:min(ans,now.maxa+now.maxb);
}

bool cmp(node2 n1,node2 n2){return n1.a<n2.a;}

signed main(){
    read(n,m);
    for(int i=1;i<=m;i++) read(e[i].u,e[i].v,e[i].a,e[i].b);
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;i++) Link(e[i].u,e[i].v,a[i+n]=e[i].a,b[i+n]=e[i].b,i);
    cout<<ans;
    return 0;
}

第二周（2025/03/24~2025/03/30）

T1

这次来一道简单的水题。
P10463 Interval GCD

Solution

区间加很烦，\(\gcd(a,b)+c\not ={\gcd(a+c,b+c)}\)。
但是单点改则是可行的。

我们知道求 \(\gcd\) 的方法一般使用辗转相除法，但其实还有一种“更相减损术”，或者说是辗转相减法，也就是：

\[ a\ge b\\ \gcd(a,b)= \begin{cases} b&,a=b\\ gcd(a-b,b)&,a\not ={b} \end{cases} \]

于是我们将原数组进行差分后，设原数组为 \(A\)，差分数组为 \(B\)，\(\gcd\) 的值是不变的。我们也就将区间加，变成了单点加。
而求 \([L,R]\) 的 \(\gcd\) 时，也就应该是 \(\gcd(A_{L},gcd_{i=L+1}^{R}B_{i})\)。
于是就做完了。

代码

// Problem: P10463 Interval GCD
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P10463
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,val[MAXN],t[MAXN];
struct node{
    int l,r,val;
}tree[MAXN<<2];

int gcd(int x,int y){
    if(x==0||y==0) return x+y;
    if(x%y==0) return y;
    return gcd(y,x%y);
}

void pushup(int id){
    tree[id].val=gcd(tree[id*2].val,tree[id*2+1].val);
}

void build(int id,int l,int r){
    tree[id].l=l;
    tree[id].r=r;
    if(l==r){
        tree[id].val=val[l];
        return;
    }
    int mid=(l+r)>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
    pushup(id);
}

void update(int id,int l,int r,int pos,int val){
    if(pos<=0||pos>n) return;
    if(r<pos||pos<l) return;
    if(l==r){
        tree[id].val+=val;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(id*2,l,mid,pos,val);
    else update(id*2+1,mid+1,r,pos,val);
    pushup(id);
}

int query(int id,int l,int r,int L,int R){
    if(l>r||r<L||R<l) return 0;
    if(L<=l&&r<=R) return tree[id].val;
    int res=0,mid=(l+r)>>1;
    if(L<=mid) res=query(id*2,l,mid,L,R);
    if(R>mid) res=gcd(res,query(id*2+1,mid+1,r,L,R));
    return res;
}

int lowbit(int x){return x&(-x);}

void update(int pos,int val){
    while(pos<=n){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=0;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>val[i];
    for(int i=n;i>=1;i--) val[i]-=val[i-1];
    for(int i=1;i<=n;i++) update(i,val[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        char opt;int x,y,z;
        cin>>opt;
        if(opt=='Q'){
            cin>>x>>y;
            cout<<abs(gcd(query(x),query(1,1,n,x+1,y)))<<'\n';
        }
        else{
            cin>>x>>y>>z;
            update(1,1,n,x,z);
            update(x,z);
            update(1,1,n,y+1,-z);
            update(y+1,-z);
        }
    }
    return 0;
}

T2

P6790 [SNOI2020] 生成树

Solution

广义串并联图。
不会的可以去看看我的博客。

这张图为什么是广义串并联图？
首先，仙人掌是广义串并联图，加一条边有六种可能：

自环，显然不影响。
重边，直接进行叠合重边操作后不影响。
链连链，此时我们先将原来仙人掌上的环经过三种操作后缩成一个点，此时图变成了一棵树多一条边，显然这个图是广义串并联图。
环连自环，显然这个依然可以缩成一个点，因此这张图是广义串并联图。
链连环，可以看作是一个大环内部加了一条边，同上。
环连异环，我们可以看作是一个大环内加了两条边，且环长大于等于 \(5\)，只有当环长为 \(4\) 的时候，可能出现不合法情况，因此这张图是广义串并联图。

以上情况涵盖了所有情况，因此这张图是广义串并联图。

设 \(f_{i}\) 表示第 \(i\) 条边选择的时候的方案数，\(g_{i}\) 表示第 \(i\) 条边不选的时候的方案数。

那么对于一张图，其生成树数量，等于对于每种不同的生成树，其选了的边的 \(f_{i}\) 之积，乘上没选的边的 \(g_{i}\) 之积。

对于这道题而言，因为这张图是一张广义串并联图，因此经过删 \(1\) 度点、缩 \(2\) 度点，叠合重边操作后，最后会变成一个点，此时答案就已经求出来了。

显然进行“删 \(1\) 度点”操作后，这条边必须得选，直接将答案乘上 \(f_{i}\) 就行了。
进行“缩 \(2\) 度点”操作后，原来的两条边不能同时不选。两条边都选了这条边才算选了。也就是 \(f_{i}=f_{j}f_{k},g_{i}=f_{j}g_{k}+f_{k}g_{j}\)。
进行“叠合重边”操作后，原来的两条边不能同时选。两条边都不选这条边才不选，也就是 \(f_{i}=f_{j}g_{k}+f_{k}g_{j},g_{i}=g_{j}g_{k}\)。

那么就结束了。

代码

// Problem: P6790 [SNOI2020] 生成树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6790
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=4e5+10;
const int mod=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,cnt,ans=1,d[MAXN],u[MAXN],v[MAXN],f[MAXN],g[MAXN];
bool vis[MAXN];
map<pair<int,int>,int> mp;
set<int> s[MAXN];
queue<int> q;

signed main(){
    read(n,m);
    for(int i=1;i<=m;i++){
        int U,V;read(U,V);
        if(U==V) continue;
        if(mp.find(make_pair(U,V))==mp.end()){
            u[++cnt]=U,v[cnt]=V;
            mp[make_pair(U,V)]=mp[make_pair(V,U)]=cnt;
            s[U].insert(cnt);s[V].insert(cnt);
            g[cnt]=1;
            d[U]++;d[V]++;
        }
        f[mp[make_pair(U,V)]]++;
    }
    for(int i=1;i<=n;i++) if(d[i]<=2) q.push(i);
    while(!q.empty()){
        int U=q.front();q.pop();
        if(vis[U]) continue;
        vis[U]=true;
        if(d[U]==1){
            int id=*s[U].begin(),V=(v[id]==U?u[id]:v[id]);s[U].erase(id);
            mp.erase(mp.find(make_pair(U,V)));mp.erase(mp.find(make_pair(V,U)));
            ans=ans*f[id]%mod;
            s[V].erase(id);
            d[V]--;
            if(d[V]<=2) q.push(V);
        }
        if(d[U]==2){
            int id1=*s[U].begin();s[U].erase(id1);int id2=*s[U].begin();s[U].erase(id2);
            int V1=(v[id1]==U?u[id1]:v[id1]),V2=(v[id2]==U?u[id2]:v[id2]);
            mp.erase(mp.find(make_pair(U,V1)));mp.erase(mp.find(make_pair(V1,U)));
            mp.erase(mp.find(make_pair(U,V2)));mp.erase(mp.find(make_pair(V2,U)));
            s[V1].erase(id1);s[V2].erase(id2);
            d[V1]--;d[V2]--;
            int F=f[id1]*f[id2]%mod,G=(f[id1]*g[id2]%mod+g[id1]*f[id2]%mod)%mod;
            if(mp.find(make_pair(V1,V2))!=mp.end()){
                int id=mp[make_pair(V1,V2)];
                int FF=f[id],GG=g[id];
                f[id]=(FF*G%mod+GG*F%mod)%mod;
                g[id]=G*GG%mod;
            }
            else{
                u[++cnt]=V1,v[cnt]=V2;
                mp[make_pair(V1,V2)]=mp[make_pair(V2,V1)]=cnt;
                s[V1].insert(cnt);s[V2].insert(cnt);
                d[V1]++;d[V2]++;
                f[cnt]=F;g[cnt]=G;
            }
            if(d[V1]<=2) q.push(V1);
            if(d[V2]<=2) q.push(V2);
        }
    }
    cout<<ans;
    return 0;
}

第三周（2025/03/31-2025/04/06）

T1

P6603 「EZEC-2」甜梦

这道题真的是好题啊。

题面

有一张连通有向图，点的编号在 \([1,n]\) 之间且互不相同。
现在有两个点，初始均在 \(1\) 号点。任意时刻，这两个点所在的点的编号之差的绝对值不能大于 \(l\)。
每次可以移动一个点到其可以到达的另一个点，特别的，如果两个点都可以到 \(v\) 点，则可以同时移动到 \(v\) 点。
每个点有一个权值 \(a_{i}\)，第一次经过 \(i\) 点的时候将获得 \(a_{i}\)。
两个点同时到达 \(n\) 点的时候结束，问能获得权值的最大值是多少？

【数据范围与约定】

测试点编号	\(n\le\)	\(m\le\)	\(l\le\)	\(a_i\le\)	时间	特殊性质
\(1,2\)	\(10\)	\(15\)	\(5\)	\(50\)	\(1\text s\)	无
\(3\sim 4\)	\(16\)	\(40\)	\(8\)	\(5 \times 10^3\)	\(1\text s\)	无
\(5\sim 6\)	\(16\)	\(120\)	\(8\)	\(5 \times 10^3\)	\(1\text s\)	无
\(7 \sim 10\)	\(100\)	\(10^3\)	\(10\)	\(10^4\)	\(1 \text s\)	无
\(11\)	\(100\)	\(10^3\)	\(10\)	\(10^4\)	\(1\text s\)	场景是一棵树
\(12 \sim 14\)	\(10^3\)	\(10^4\)	\(10\)	\(10^4\)	\(1\text s\)	无
\(15,16\)	\(5\times10^3\)	\(3\times10^4\)	\(10\)	\(10^4\)	\(1\text s\)	无
\(17,18\)	\(5\times10^3\)	\(3\times10^4\)	\(11\)	\(10^4\)	\(2\text s\)	无
\(19,20\)	\(5\times10^3\)	\(3\times10^4\)	\(12\)	\(10^4\)	\(3\text s\)	无

对于 \(100\%\) 的数据，\(1\le u<v \le n\), \(1 \le n \le 5\times 10^3\), \(1 \le m \le 3\times 10^4\), \(1 \le a_i \le 10^4\), \(1 \le l \le 12\)。

输入保证每个场景都能从起点到达，并且都能连到终点。
输入不保证没有重边。
输入不对 \(u,v\) 的编号差做任何保证。

Hint1

可以先思考一个最暴力的状压 DP。并计算一下你能通过哪些数据点。尝试一下优化？

Hint2

显然对于 \(n\) 很小的时候，我们可以设计状态 \(dp_{S,i,j}\) 表示当前已经走了 \(S\) 集合，当前两个点是 \(i,j\) 的最大权值和。转移在这里就不给出了。
这样的状态复杂度是 \(O(2^nn^2)\)，可以拿 \(20pts\)。
对于这张图的性质你有没有找全？

Hint3

发现图其实是一张 DAG，并且总是从编号小的点到编号大的点。
因此我们是没有必要将整张图的状态都记录下来的。
如果 \(S\) 中最小的点是 \(k\)，那么编号小于 \(k\) 的点都没用了。我们可以将它们丢掉。
不妨设 \(dp_{S,i,j}\) 表示从 \([k,k+l]\) 这些点的状态，\(i,j\) 依然表示这两个点的位置。
此时的状态复杂度是 \(O(2^ln^2)\)，可以获得 \(55pts\)。
能优化一下状态吗？

Hint4

如果我们记录的 \(i\) 并不是当前 \(S\) 中表示的最小的点，那么显然 \(S\) 中前面的点依然可以丢掉。因此我们强制 \(i\) 是 \(S\) 中最小编号的点。
我们令新的状态 \(dp_{S,i,j}\) 表示 \([k,k+l]\) 点的状态，其中最小的点的编号为 \(i\)，另一个点的编号是 \(i+j\)。
此时状态复杂度变为 \(O(n2^ll)\)，可以获得 \(80pts\) 左右。
还能继续优化吗？

Hint5

记录最小的点与最大的点的编号的差有意义吗？

Solution

因为不能走回头路，假如 \(i+j\) 并不是当前 \(S\) 中最大的，那说明后面有点走过了，这显然是不合法的，因此另一个点此时必然为 \(S\) 中最高的为 \(1\) 的二进制位表示的编号。
于是此时只需要记录 \(dp_{S,i}\) 即可，时间复杂度 \(O(n2^l)\)，可以通过。
转移方程呢？分类讨论一下即可：
我们不妨令较小的点为 \(A\)，较大的点为 \(B\)，要转移到的点为 \(v\)。

从 \(B\) 转移到 \(v\)：
肯定需要满足 \(v-B\le l\)。
\(dp_{S,A}+a_{v}\to dp_{S|(1<<v-B),A}\)。
（ps：这样写 \(\LaTeX\) 其实是不太好的，但我这里就将就一下吧。）
从 \(A\) 和 \(B\) 同时转移到 \(v\)：首先肯定需要 \(A\) 和 \(B\) 均可到达 \(v\)。
\(dp_{S,A}+a_{v}\to dp_{1,v}\)。
从 \(A\) 转移到 \(v\)：这里又要分两种情况了。
1. \(v\le B\)：
  此时最小的点从 \(A\) 变成了 \(v\)。
  \(dp_{S,A}+a_{v}\to dp_{(S>>v-A)|1},v\)。
  注意要判断一下 \(v\) 在曾经的状态中又没有出现过，出现过就不要多加一次 \(a_{v}\) 了。
2. \(v-B\le l\)：此时最小的点从 \(A\) 变成了 \(B\)。
  \(dp_{S,A}+a_{v}\to dp_{(S>>B-A)|1|(1<<v-B)},B\)。
  此时并不需要判断 \(v\) 出现过没有，因为如果出现过，要么 \(v-A>l\) 不合法，要么原先最大的点不是 \(B\) 而是 \(v\)。

那么就结束了，注意下因为距离范围是 \([0,l]\)，所以数组应该开 \(2^{l+1}\) 而不是 \(2^{l}\)。

代码

// Problem: P6603 「EZEC-2」甜梦
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P6603
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e3+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

bool awa;
int n,m,l,k,old=0,now=1,head[MAXN],a[MAXN],dp[MAXN][(1<<13)],maxval[(1<<13)];
struct node{
    int to,next;
}edge[MAXN*20];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}
bool qwq;

signed main(){
    // cout<<(&awa-&qwq)/1024.0/1024.0<<endl;
    read(n,m,l);
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=m;i++){
        int u,v;
        read(u,v);
        build(u,v);
    }
    memset(dp,-1,sizeof(dp));
    dp[1][1]=a[1];
    for(int i=0;i<(1<<l+1);i++){
        for(int j=0;j<=l;j++){
            if(i&(1<<j)) maxval[i]=j;
        }
    }
    for(int A=1;A<=n;A++){
        for(int i=1;i<(1<<l+1);i++){
            int B=A+maxval[i];
            if(dp[A][i]==-1||B>n) continue;
            set<int> s1,s2,g;
            for(int j=head[A];j;j=edge[j].next) s1.insert(edge[j].to);
            for(int j=head[B];j;j=edge[j].next) s2.insert(edge[j].to);
            for(int j:s2) if(s1.find(j)!=s1.end()) g.insert(j);
            for(int j:s2) if(j-A<=l) dp[A][i|(1<<j-A)]=max(dp[A][i|(1<<j-A)],dp[A][i]+a[j]);
            for(int j:s1){
                if(j<=B){
                    int state=(i>>j-A)|1;
                    dp[j][state]=max(dp[j][state],dp[A][i]+((i&(1<<j-A))?0:a[j]));
                }
                else{
                    if(j-B<=l){
                        int state=(i>>B-A)|1|(1<<j-B);
                        dp[B][state]=max(dp[B][state],dp[A][i]+a[j]);
                    }
                }
            }
            for(int j:g) dp[j][1]=max(dp[j][1],dp[A][i]+a[j]);
        }
    }
    cout<<dp[n][1];
    return 0;
}

T2

P2481 [SDOI2010] 代码拍卖会

这题也真的是好题啊。

Solution

首先看见 \(N\) 这么大，容易想到矩阵快速幂或者是数位 DP。
发现如果写成矩阵快速幂必然和 \(p\) 相关，而 \(p\le 500,p^3\le 1.25\times 10^8\) 还要加只 \(\log\)，肯定过不了，所以尝试往数位 DP 上去想。

不妨设每只小猪给出 \(a_{i}\) 颗猪币，发现 \(a_{i}\) 不降。联系到数位 DP 的特点是优化重复计算的内容，于是思考什么地方有多次重复计算。

发现可以将 \(a_{i}\) 拆成 \(a_{i}\) 个 \(1\)，由于取模具有结合律，所以可以重新组合成若干个后缀均为 \(1\) 的数之和。我们不妨称这种数为 \(1\) 串。（也就是由若干个 \(1\) 组成的数）比如 \(1124\) 可以拆成 \(1111+11+1+1\)。

而后缀为 \(1\) 的数对 \(p\) 取模可以简单得由下边这个递推式得出：
\[ dp_{i}=(dp_{i-1}\times10+1)\bmod p \] 这个东西在至多 \(2\times p\) 的范围内会出现重复。于是我们便可以简单的计算取模后结果为 \(i\) 的由若干个 \(1\) 的数的数量。我们记这个东西为 \(f_{i}\)。
具体的，我们分三部分计算：

没进入循环节的部分
完整循环节的部分
非完整循环节的部分

于是我们便可以设计一个简单的背包 DP 来计算答案。
设 \(dp_{i,j,k}\) 表示，当前考虑到取模后结果为 \(i\) 的 \(1\) 串对答案的贡献，\(j\) 表示当前的和对 \(p\) 取模是多少，\(k\) 表示我们已经用了多少个 \(1\) 串。
转移是平凡的。大家可以自己推一下。

因为一只小猪最多出 \(9\) 个币，所以 \(1\) 串的数量最多也只有 \(9\)，总的时间复杂度可以说是 \(O(81\times p^2)\)，准确点说就是 \(O(p^2)\) 的。

细节有点小多，具体可以看我代码。

代码

// Problem: P2481 [SDOI2010] 代码拍卖会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2481
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e2+10;
const int mod=999911659;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,ans,p,len,pos,dp[MAXN][MAXN][11],f[MAXN],last[MAXN],inv[MAXN];

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

int C(int x,int y){
    if(x<0) return 1;
    if(x<y) return 0;
    int res=1;
    for(int i=1;i<=y;i++) res=res*(x-i+1)%mod*inv[i]%mod;
    return res;
}

signed main(){
    read(n,p);
    int val=1%p;
    memset(last,-1,sizeof(last));
    for(int i=1;i<=10;i++) inv[i]=qpow(i,mod-2);
    for(int i=1;i<=min(n,2*p);i++){
        if(last[val]!=-1){
            len=i-1-last[val];
            pos=i-1;
            break;
        }
        if(i==n) dp[0][val][1]=1;
        f[val]++;
        last[val]=i-1;
        val=(val*10+1)%p;
    }
    if(len!=0){
        int cycle=(n-pos)/len+1;
        for(int i=1;i<=len;i++){
            f[val]=f[val]*cycle%mod;
            val=(val*10+1)%p;
        }
        if(pos+(n-pos)/len*len+1==n+1){
            for(int i=1;i<len;i++) val=(val*10+1)%p;
            dp[0][val][1]=1;
        }
        for(int i=pos+(n-pos)/len*len+1;i<=n;i++){
            f[val]++;
            if(i==n) dp[0][val][1]=1;
            val=(val*10+1)%p;
        }
    }
    for(int i=0;i<p;i++) f[i]%=mod;
    for(int i=1;i<=p;i++){
        for(int k=1;k<=9;k++){
            for(int q=0;q+k<=9;q++){
                for(int j=0;j<p;j++){
                    (dp[i][(j+(i-1)*q)%p][q+k]+=dp[i-1][j][k]*C(f[i-1]+q-1,q)%mod)%=mod;
                }
            }
        }
    }
    for(int i=1;i<=9;i++) ans=(ans+dp[p][0][i])%mod;
    cout<<ans;
    return 0;
}

第四周（2025/04/07-2025/04/13）

T1

CF468C Hack it!
CF 传送门：CF468C Hack it!

思维题，码量极短。

Solution

我们假设 \(f(x)=y\)，则有 \(f(x+10^{18})=y+1,1\le x < 10^{18}\)。
我们令 \(\sum_{i=0}^{10^{18}-1}f(i)\equiv z \pmod a\)，可以推得：

\[ \sum_{i=1}^{10^{18}}f(i)\equiv z+1 \pmod a \]

于是可得：

\[ \sum_{i=a-z}^{10^{18}-1+a-z}f(i)\equiv 0 \pmod a \]

那么 \(z\) 怎么求呢？
我们令 \(g(x)\) 表示 \(\sum_{i=0}^{10^x-1}f(i)\bmod a\) 的值，那么 \(z\) 就等于 \(g(18)\)。我们又有 \(g(i)=45\times 10^{i-1}+g(i-1)\times 10\)。化简一下得到：

\[ \begin{aligned} g(i)&=45\times 10^{i-1}+g(i-1)\times 10\\ &=45\times 10^{i-1}+(45\times 10^{i-2}+g(i-2)\times 10)\times 10\\ &=45\times 10^{i-1}+45\times 10^{i-1}+g(i-2)\times 10^2\\ &=45\times (i-1) \times 10^{i-1}+g(1)\times 10^{i-1}\\ &=45\times i \times 10^{i-1}\\ \end{aligned} \]

于是，\(g(18)\) 也可以在 \(O(1)\) 的时间内求出来。
这道题便做完了。

代码

// Problem: CF468C Hack it!
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF468C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

//(0) 1 2 3 4 5 6 7 8  9
// 1  2 3 4 5 6 7 8 9  10
// 2  3 4 5 6 7 8 9 10 11

//0~9:45
//0~99:45*10+45*10
//0~999:45*100+10*(10~99)
//0~1e18-1:18*45*1e17

int n,f_1e18_1,_1e18_1=1000000000000000000ll-1ll;

signed main(){
    read(n);
    f_1e18_1=100000000000000000ull*45ull%n*18ull%n;
    if(f_1e18_1==0) cout<<1<<" "<<(int)(_1e18_1);
    else cout<<n-f_1e18_1<<" "<<(int)(_1e18_1+(n-f_1e18_1));
    return 0;
}

T2

CF512E Fox And Polygon
CF 传送门：CF512E Fox And Polygon

思维题，个人感觉远没有 \(2900\)。
我的代码写的比较丑陋，实际可以更短。

Solution

首先，题面已经告诉我们了，从任意状态可以变成任意状态。
我们不妨设一个中间状态 \(M\)，变化过程就是 \(S\to M\to T\)。
从 \(M\) 到 \(T\) 可以变成从 \(T\) 到 \(M\)，再把方案倒过来。

我们不妨令一种特殊情况为 \(M\)，比如所有对角线均从 \(1\) 号点出发。
我们发现一条从 \(1\) 号点出发的对角线将多边形分成了两半，可以继续递归处理。
实际上进行的次数是 \(n-3\) 次。

不妨设当前我们的区间为 \([l,r]\)，假设其中有一条从 \(1\) 号点出发的对角线，直接分成两半。否则我们需要一次翻转。

那么我们怎么去找原来的对角线呢？
我们发现原先的对角线一定是 \(l\) 连接 \(r\)。画个图就知道了。

那么新的对角线的另一端点呢？
我们将一个点连接的边的另一端点丢进一个 set 里面。
我们发现我们要找的，刚好就是 \(r\) 的 set 里面，\(l\) 的后继。这个画下图也就知道了。
然后修改了对角线后，会造成影响，一样用 set 维护一下就好了。

时间复杂度 \(O(n\log n)\)

代码

// Problem: CF512E Fox And Polygon
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF512E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,cnt1,cnt2,x[MAXN],y[MAXN];
set<int> s1[MAXN],s2[MAXN];

void work1(int l,int r){
    if(l+1==r) return;
    auto pos=s1[1].find(l);
    pos++;
    if(*pos==r){
        x[++cnt1]=l,y[cnt1]=r;
        pos=s1[r].find(l);pos++;
        int awa=*pos;
        s1[1].insert(awa);
        s1[l].erase(r);s1[r].erase(l);
        work1(l,awa);work1(awa,r);
    }
    else{
        int awa=*pos;
        work1(l,awa);work1(awa,r);
    }
}

void work2(int l,int r){
    if(l+1==r) return;
    auto pos=s2[1].find(l);
    pos++;
    if(*pos==r){
        pos=s2[r].find(l);pos++;
        int awa=*pos;
        x[++cnt2]=1,y[cnt2]=awa;
        s2[1].insert(awa);
        s2[l].erase(r);s2[r].erase(l);
        work2(l,awa);work2(awa,r);
    }
    else{
        int awa=*pos;
        work2(l,awa);work2(awa,r);
    }
}

signed main(){
    read(n);
    for(int i=1;i<=n-3;i++){
        int a,b;read(a,b);
        s1[a].insert(b);s1[b].insert(a);
    }
    for(int i=1;i<=n-3;i++){
        int a,b;read(a,b);
        s2[a].insert(b);s2[b].insert(a);
    }
    for(int i=1;i<=n;i++){
        s1[i].insert(i+1==n+1?1:i+1),s1[i].insert(i-1==0?n:i-1);
        s2[i].insert(i+1==n+1?1:i+1),s2[i].insert(i-1==0?n:i-1);
    }
    work1(2,n);
    cnt2=cnt1;
    work2(2,n);
    cout<<cnt2<<'\n';
    for(int i=1;i<=cnt1;i++) cout<<x[i]<<" "<<y[i]<<'\n';
    for(int i=cnt2;i>=1+cnt1;i--) cout<<x[i]<<" "<<y[i]<<'\n';
    return 0;
}

第五周（2025/04/14-2025/04/20）

T1

P4948 数列求和

数学题，推推式子就可以了。

Solution

题目让求：

\[ \sum_{i=1}^{n}i^ka^i \]

我们从特殊性质入手。
\(k=0\) 时也就是 \(\sum_{i=1}^{n}a^i\)。这是一个标准的等比数列求和。

\[ \begin{aligned} f(n)=\sum_{i=1}^{n}a^i\\ af(n)=\sum_{i=2}^{n+1}a^i\\ (a-1)f(n)=a^{n+1}-a\\ f(n)=\dfrac{a^{n+1}-a}{a-1} \end{aligned} \]

直接照着式子做就行了。

接下来考虑 \(k=1\) 的情况。
此时要求的变成 \(\sum_{i=1}^{n}ia^i\)。
我们沿用一下 \(k=0\) 时的思路。

令：

\[ A=\sum_{i=1}^{n}ia^i\\ B=\sum_{i=2}^{n+1}ia^i\\ C=aA=\sum_{i=1}^{n}ia^{i+1} \]

可以得到：

\[ B-A=(n+1)a^{n+1}-a\\ C-B=-\sum_{i=2}^{n+1}a^i\\ C-A=(n+1)a^{n+1}-a-\sum_{i=2}^{n+1}a^i\\ (a-1)A=(n+1)a^{n+1}-a-a\sum_{i=1}^{n}a^i\\ A=\dfrac{(n+1)a^{n+1}-a-a\sum_{i=1}^{n}a^i}{a-1} \]

最后面又是一个 \(k=0\) 的式子，直接算就行了。

有了 \(k=1\) 的思路，我们不妨考虑更一般的情况。

令：

\[ f(k)=\sum_{i=1}^{n}i^ka^i\\ g(k)=\sum_{i=2}^{n+1}i^ka^i\\ af(k)=\sum_{i=2}^{n+1}(i-1)^ka^{i}\\ \]

可以得到：

\[ af(k)-g(k)=-\sum_{i=2}^{n+1}a^{i}\left(i^k-(i-1)^k\right)\\ g(k)-f(k)=(n+1)^ka^{n+1}-a\\ (a-1)f(k)=(n+1)^ka^{n+1}-a-\sum_{i=2}^{n+1}a^{i}\left(i^k-(i-1)^k\right)\\ \]

\(i^k-(i-1)^k\) 这个东西直接考虑展开，发现也就是 \(\sum_{j=0}^{k-1}\begin{pmatrix}k\\j\\\end{pmatrix}(i-1)^j\)。

我们每次要求的 \(i\) 都是从 \(2\) 到 \(n+1\)，于是原式可以转化为：

\[ (a-1)f(k)=(n+1)^ka^{n+1}-a- \sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix}\sum_{i=2}^{n+1}a^i(i-1)^j\\ \]

后面提出一个 \(a\)，得到：

\[ (a-1)f(k)=(n+1)^ka^{n+1}-a- a\sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix}\sum_{i=1}^{n}i^ja^i\\ \]

我们发现 \(\sum_{i=1}^{n}i^ja^i\) 其实就是 \(f(j)\)。
因此就有：

\[ f(k)=\dfrac{(n+1)^ka^{n+1}-a- a\sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix}f(j)}{a-1}\\ \]

照着式子 \(O(k^2)\) 去做就好了。

但是我们发现，当 \(a=1\) 的时候，这个式子出现了除以 \(0\) 的情况，这显然是不行的。
此时我们要求的式子，变成了 \(\sum_{i=1}^{n}i^k\)。
这个又怎么去做呢？

我们这次换一种方法，上面的也可以使用下面这种方法来推。但我不知道下面这个能不能用上面那个来推。

我们令：

\[ f(k)=\sum_{i=1}^{n}i^k\\ g(k)=\sum_{i=2}^{n+1}i^k=\sum_{i=1}^n(i+1)^k\\ \]

有：

\[ g(k)-f(k)=(n+1)^k-1\\ \]

我们又根据上面的 \(a^k-(a-1)^k=\sum_{i=0}^{k-1}\begin{pmatrix}k\\i\\\end{pmatrix}(a-1)^i\) 可以得到：

\[ \begin{aligned} g(k)-f(k)&= \sum_{i=1}^n\sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix}i^j\\ &=\sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix} \sum_{i=1}^ni^j\\ &=\sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix} f(j)\\ \end{aligned} \\ \]

根据上下两个式子，我们可以得到：

\[ \sum_{j=0}^{k-1} \begin{pmatrix} k\\ j\\ \end{pmatrix} f(j)-(n+1)^k+1=0\\ \]

从左边拿出一个 \(\begin{pmatrix}k\\k-1\\\end{pmatrix}f(k-1)=kf(k-1)\) 得到：

\[ \sum_{j=0}^{k-2} \begin{pmatrix} k\\ j\\ \end{pmatrix} f(j)-(n+1)^k+1=-kf(k-1) \]

将 \(k\) 增加 \(1\) 得到：

\[ \sum_{j=0}^{k-1} \begin{pmatrix} k+1\\ j\\ \end{pmatrix} f(j)-(n+1)^{k+1}+1=-(k+1)f(k) \]

两边同时乘以 \(-1\) 得到：

\[ (k+1)f(k)= (n+1)^{k+1}- \sum_{j=0}^{k-1} \begin{pmatrix} k+1\\ j\\ \end{pmatrix} f(j)-1\\ f(k)=\dfrac{ (n+1)^{k+1}-1- \sum_{j=0}^{k-1} \begin{pmatrix} k+1\\ j\\ \end{pmatrix}f(j)}{k+1} \]

同样 \(O(k^2)\) 照着式子做就可以了。

那么就结束了。

代码

// Problem: P4948 数列求和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4948
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod=1e9+7;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,a,k,f[MAXN],fac[MAXN],inv[MAXN];

int qpow(int x,int y){
    x%=mod;
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

int C(int x,int y){
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}

signed main(){
    read(n,a,k);
    fac[0]=1;
    for(int i=1;i<=k+1;i++) fac[i]=fac[i-1]*i%mod;
    inv[k+1]=qpow(fac[k+1],mod-2);
    for(int i=k;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    if(a==1){
        f[0]=n;
        for(int i=1;i<=k;i++){
            int sum=0;
            for(int j=0;j<i;j++) (sum+=C(i+1,j)*f[j]%mod)%=mod;
            f[i]=((qpow(n+1,i+1)-1-sum)%mod+mod)%mod*qpow(i+1,mod-2)%mod;
        }
    }
    else{
        f[0]=(qpow(a,n+1)-a+mod)%mod*qpow(a-1,mod-2)%mod;
        for(int i=1;i<=k;i++){
            int sum=0;
            for(int j=0;j<i;j++) (sum+=C(i,j)*f[j]%mod)%=mod;
            f[i]=((qpow(n+1,i)*qpow(a,n+1)%mod-a-a*sum%mod)%mod+mod)%mod*qpow(a-1,mod-2)%mod;
        }
    }
    cout<<f[k];
    return 0;
}

T2

P3209 [HNOI2010] 平面图判定

突然发现我不会 2-SAT，于是学了一下。

Solution

首先，我们先得知道一个定理：

若一张图是平面图，那么有 \(m\leq 3n-6\)。其中 \(m\) 是边数， \(n\) 是点数。

于是我们就可以判一下，此时 \(m\) 变得与 \(n\) 同阶，想一想怎么建立 2-SAT 就行了。

图一定存在一条哈密顿回路，我们把这条回路提出来，发现一条边要么从环里面连，要么从环外面连。
什么情况下会造成冲突呢？
当两条线段从同一种面填会相交的时候，那么此时就出现冲突（废话）此时也就构成了 2-SAT。

那么问题就是怎么找冲突的，令两条线段的四个端点依次为 \(x_1,y_1,x_2,y_2\)，画一下图，发现当 \(x_1<x_2<y_1<y_2\) 时则出现冲突，直接根据 2-SAT 连边就可以了。

那么就做完了。

代码

// Problem: P3209 [HNOI2010] 平面图判定
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3209
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int T,n,m,k,tot,cnt,id[MAXN],head[MAXN],scc[MAXN],dfn[MAXN],low[MAXN];
bool vis[MAXN],instack[MAXN];
stack<int> s;
struct node{
    int u,v;
}e[MAXN];
struct node2{
    int to,next;
}edge[MAXN];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void tarjan(int u){
    vis[u]=instack[u]=true;
    dfn[u]=low[u]=++cnt;
    s.push(u);
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(instack[v]) low[u]=min(low[u],dfn[v]);
        if(vis[v]) continue;
        tarjan(v);
        low[u]=min(low[u],low[v]);
    }
    if(dfn[u]==low[u]){
        tot++;
        while(s.top()!=u){
            instack[s.top()]=false;
            scc[s.top()]=tot;
            s.pop();
        }
        instack[s.top()]=false;
        scc[s.top()]=tot;
        s.pop();
    }
}

signed main(){
    read(T);
    while(T--){
        read(n,m);
        k=tot=cnt=0;
        for(int i=1;i<=m;i++) read(e[i].u,e[i].v);
        for(int i=1;i<=n;i++){
            int val;
            read(val);
            id[val]=i;
        }
        if(m>3*n-6){
            cout<<"NO\n";
            continue;
        }
        for(int i=1;i<=m;i++){
            if(abs(id[e[i].u]-id[e[i].v])==1||abs(id[e[i].u]-id[e[i].v])==n-1) continue;
            for(int j=i+1;j<=m;j++){
                if(abs(id[e[j].u]-id[e[j].v])==1||abs(id[e[j].u]-id[e[j].v])==n-1) continue;
                int x1=id[e[i].u],y1=id[e[i].v],x2=id[e[j].u],y2=id[e[j].v];
                if(x1>y1) swap(x1,y1);
                if(x2>y2) swap(x2,y2);
                if(x1>x2) swap(x1,x2),swap(y1,y2);
                if(x1<x2&&x2<y1&&y1<y2){
                    build(i,j+m);
                    build(j,i+m);
                    build(j+m,i);
                    build(i+m,j);
                }
            }
        }
        for(int i=1;i<=2*m;i++) if(!dfn[i]) tarjan(i);
        bool flag=true;
        for(int i=1;i<=m;i++){
            if(scc[i]==scc[i+m]){
                flag=false;
                break;
            }
        }
        cout<<(flag?"YES\n":"NO\n");
        for(int i=1;i<=2*m;i++) head[i]=scc[i]=dfn[i]=low[i]=vis[i]=instack[i]=0;
    }
    return 0;
}

第六周（2025/04/21-2025/04/27）

每周好题分享永久停办一周。

第七周（2025/06/02-2025/06/08）

打赢复活赛了。

T1

P4173 残缺的字符串

Solution

见：使用 FFT/NTT 进行字符串匹配

T2

P7044 「MCOI-03」括号

突然发现我不会组合数学，于是恶补了一下。

Solution

\(n\) 有 \(10^6\)，非常的大，这启发我们这道题大概率是 \(O(n)\) 做法。
不妨先考虑 \(K=1\) 的情况。

读题，分析一下，发现所谓的 \(0\) 级偏值，也就是对括号串进行括号匹配后，剩下的左括号的数量加上右括号的数量。
于是我们便可以轻松得到一个 \(O(n^2)\) 的做法。

发现我们在计算的时候，对某一个括号进行了多次重复的计算，我们不妨考虑一个括号会产生什么样的贡献。
我们使用栈进行括号匹配的时候，找到的是从中间开始的匹配，我们对于左括号记一下其右侧第一个能与其匹配的左括号的位置，记作 \(nxt_{i}\)，对于右括号记一下其左侧第一个能与其匹配的左括号的位置，记作 \(pre_{i}\)。
那么对于左括号 \(s_{i}\)，当子串 \([L,R]\) 满足 \(1\le L \le i,i\le R<nxt_{i}\) 时，该左括号会产生 \(1\) 的贡献。
同理，对于右括号 \(s_{i}\)，当子串 \([L,R]\) 满足 \(pre_{i}< L \le i,i\le R\le n\) 时，该右括号会产生 \(1\) 的贡献。
根据 \(\sum\limits_{L=1}^{i}\sum\limits_{R=i}^{nxt_{i}-1}1=i(nxt_{i}-i)\)，这个是可以 \(O(1)\) 计算的。于是对于 \(k=1\) 的情况，我们预处理出需要的 \(pre_{i}\) 和 \(nxt_{i}\)。再扫一遍即可。

那么现在考虑 \(k>1\) 的情况。
不难发现，对于子串 \([l,r]\)，对于其上一级偏值，能产生该子串贡献的区间 \([L,R]\)，满足 \(1\le L\le l,r\le R\le n\)。也就是说明，我们将计算 \(k\) 级偏值的顺序倒过来，对于子串 \([l,r]\)，每次就是在扩大这个区间。
我们现在只考虑 \(l\)，\(r\) 是同理的，发现其本质是一个长度为 \(k-1\) 的不升序列，并且序列中所有元素的值均小于等于 \(l\)，大于等于 \(1\)。
这个是很经典的 trick，不升序列倒过来就成了不降序列，对于一个长度为 \(a\)，值域为 \([1,b]\) 的不降序列，其可行方案数为 \(\begin{pmatrix}a+b-1\\b-1\end{pmatrix}\)。

那么对于这道题而言，子串 \([l,r]\) 会被计算的次数也就是

\[ \begin{pmatrix} k-1+l-1\\ l-1 \end{pmatrix} \begin{pmatrix} k-1+(n-r+1)-1\\ (n-r+1)-1 \end{pmatrix} \]

化简一下，再根据 \(\begin{pmatrix}a\\b\end{pmatrix}=\begin{pmatrix}a\\a-b\end{pmatrix}\)。可以得到：

\[ \begin{pmatrix} k+l-2\\ k-1 \end{pmatrix} \begin{pmatrix} k+n-r-1\\ k-1 \end{pmatrix} \]

和 \(k=1\) 类似，我们同样考虑一个位置会产生什么贡献，可以得到，对于一个左括号 \(s_{i}\)，我们要求的答案，是：

\[ \sum_{l=1}^{i} \sum_{r=i}^{nxt_{i}-1} \begin{pmatrix} k+l-2\\ k-1 \end{pmatrix} \begin{pmatrix} k+n-r-1\\ k-1 \end{pmatrix} \]

这个东西可以变成

\[ \sum_{l=1}^{i} \begin{pmatrix} k+l-2\\ k-1 \end{pmatrix} \sum_{r=i}^{nxt_{i}-1} \begin{pmatrix} k+n-r-1\\ k-1 \end{pmatrix} \]

前面这个东西是显然可以化简的，后面也是。
最后得到答案：

\[ \begin{pmatrix} k+i-1\\ k \end{pmatrix} \left( \begin{pmatrix} k+n-i\\ k \end{pmatrix}- \begin{pmatrix} k+n-nxt_{i}\\ k \end{pmatrix} \right) \]

对于右括号是同理的，我就不推了。

最后照着式子做就好了，时间复杂度 \(O(n)\)。

代码

// Problem: P7044 「MCOI-03」括号
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7044
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e6+10;
const int mod=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,k,ans,fac[MAXN],inv[MAXN],pre[MAXN],nxt[MAXN];
string s;

int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=res*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return res;
}

int C(int x,int y){
    return fac[x]*inv[y]%mod*inv[x-y]%mod;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>s;s=' '+s;
    for(int i=1;i<=n;i++) if(s[i]=='(') nxt[i]=n+1;
    for(int i=1;i<=n;i++) if(s[i]==')') pre[i]=0;
    stack<int> sta;
    for(int i=1;i<=n;i++){
        if(s[i]=='(') sta.push(i);
        else{
            if(!sta.empty()&&s[sta.top()]=='(') pre[i]=sta.top(),nxt[sta.top()]=i,sta.pop();
            else sta.push(i);
        }
    }
    fac[0]=1;
    for(int i=1;i<=2e6;i++) fac[i]=fac[i-1]*i%mod;
    inv[2000000]=qpow(fac[2000000],mod-2);
    for(int i=2e6-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
    for(int i=1;i<=n;i++){
        if(s[i]=='(') (ans+=C(k+i-1,k)*((C(k+n-i,k)-C(k+n-nxt[i],k)+mod)%mod)%mod)%=mod;
        else (ans+=((C(k+i-1,k)-C(k+pre[i]-1,k)+mod)%mod)*C(k+n-i,k)%mod)%=mod;
    }
    cout<<ans;
    return 0;
}

第八周（2025/06/09-2025/06/29）

（因一些原因，上周和上上周没有讲）

T1

CF930C Teodor is not a liar!

有意思的 DP 题。

Solution

先手玩一下样例，帮助理解一下题意。
后文感觉有点跳跃，但其实我也不知道我怎么想到的。

我们记 \(cnt_i\) 表示对于第 \(i\) 个点，其在所有区间中被包含的次数。我们发现，只要我们对于所有当前询问的点，存在一种方案，使得存在某个点被某些区间包含，并且所有点被包含次数均符合，那么就是不确定的。

不难想到，假如所有询问的 \(i\) 的 \(cnt_{i}\) 构成一个不降序列，则可以轻松构造出一种合法方案。同理，构成不升序列也是可行的。

考虑什么时候能确定，能确定，也就是确定存在某个点，没有被所有区间包含。说明这个点的左侧存在一些完整的区间，右边也存在一些完整的区间。并且同时也不能是不降序列，不升序列或者这两个拼起来。那么只能是存在 \(n_1,n_2,n_3\) 满足 \(cnt_1>cnt_2,cnt_3>cnt_2\)。

那思路就很清晰了，既然不能存在上述情况，那我们对于一个点 \(1\)，我们去找 \([1,i]\) 的最长不降子序列，找 \([i+1,n]\) 的最长不升子序列，此时 \(cnt_{i}\) 是不定的，左右也都能构造出方案使其不确定。那么我们对于所有的 \(i\) 去求一次答案，取 \(\max\) 就行了。
求这个东西是容易的，我们在做最长不降子序列的时候，实际上求的就是所有前缀的最长不降子序列，所以做一次就好了。后者同理，倒着做一次即可。~~不会有人现在还不会O(nlogn)的最长不降子序列吧，不会吧，不会吧。~~

代码

// Problem: CF930C Teodor is not a liar!
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF930C
// Memory Limit: 250 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,t[MAXN],z[MAXN],maxlen,len[MAXN],dp1[MAXN],dp2[MAXN];

int lowbit(int u){return u&(-u);}

void update(int pos,int val){
    while(pos<=m){
        t[pos]+=val;
        pos+=lowbit(pos);
    }
}

int query(int pos){
    int res=1;
    while(pos){
        res+=t[pos];
        pos-=lowbit(pos);
    }
    return res;
}

signed main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        int l,r;
        read(l,r);
        update(l,1);
        if(r+1<=m) update(r+1,-1);
    }
    for(int i=1;i<=m;i++) z[i]=query(i);
    len[0]=0;maxlen=0;
    for(int i=1;i<=m;i++){
        int pos=upper_bound(len,len+maxlen+1,z[i])-len-1;
        dp1[i]=pos+1;
        if(pos+1>maxlen) maxlen=pos+1,len[pos+1]=z[i];
        else len[pos+1]=min(len[pos+1],z[i]);
    }
    memset(len,0,sizeof(len));
    len[0]=0;maxlen=0;
    for(int i=m;i>=1;i--){
        int pos=upper_bound(len,len+maxlen+1,z[i])-len-1;
        dp2[i]=pos+1;
        if(pos+1>maxlen) maxlen=pos+1,len[pos+1]=z[i];
        else len[pos+1]=min(len[pos+1],z[i]);
    }
    int ans=0;
    for(int i=1;i<=m;i++) ans=max(ans,dp1[i]+dp2[i+1]);
    cout<<ans;
    return 0;
}

T2

P11113 [ROI 2024] 2026 (Day 1)

比较显然的一道紫题。

Solution

首先不难发现，对于连续的相同操作或是相反操作，我们可以简化为一次操作，比如 LRRRLLLR 可以简化为 R。
然后手玩一下，发现，至多两次操作后，所有的方块都堆到了角落，并且接下来的操作中，只要转到这个角落，形态是不变的。
有一些操作仍是无效的，比如此时方块均在左上角，那么 L 和 U 操作均是无效的。我们将这些无效操作删除后，可能又会出现相反或是相同的操作，我们也同样去掉这些操作，发现这类似于括号匹配，用一个栈即可维护。
发现剩下来的操作，要么是顺时针旋转，要么是逆时针旋转。
于是我们先暴力跑两次操作，到达墙角后，我们按操作来顺时针或是逆时针旋转，并且得到原本位置和旋转后的位置的一一对应关系，再使用诸如倍增或是其他办法来快速进行操作，最后对于剩下直接暴力即可。
暴力显然是 \(O(N^2)\) 的（\(N=n\times m\)），暴力操作至多进行 \(9\) 次，剩下的时间复杂度是 \(O(N^2\log q)\) 的。轻松通过。
难点主要在模拟，有一些细节。

代码

// Problem: P11113 [ROI 2024] 2026 (Day 1)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11113
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,t,m,q,cnt=-1,pos,to[MAXN][21],mp[MAXN];
string op,newop;
vector<int> ch[MAXN],num[MAXN];

void work(char op){
    if(op=='U'){
        for(int j=1;j<=m;j++){
            int cnt=1;
            for(int i=1;i<=n;i++){
                if(ch[i][j]==-1) continue;
                swap(ch[cnt][j],ch[i][j]);
                cnt++;
            }
        }
    }
    if(op=='D'){
        for(int j=1;j<=m;j++){
            int cnt=n;
            for(int i=n;i>=1;i--){
                if(ch[i][j]==-1) continue;
                swap(ch[cnt][j],ch[i][j]);
                cnt--;
            }
        }
    }
    if(op=='L'){
        for(int i=1;i<=n;i++){
            int cnt=1;
            for(int j=1;j<=m;j++){
                if(ch[i][j]==-1) continue;
                swap(ch[i][cnt],ch[i][j]);
                cnt++;
            }
        }
    }
    if(op=='R'){
        for(int i=1;i<=n;i++){
            int cnt=m;
            for(int j=m;j>=1;j--){
                if(ch[i][j]==-1) continue;
                swap(ch[i][cnt],ch[i][j]);
                cnt--;
            }
        }
    }
}

void print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ch[i][j]==-1) cout<<'.';
            else cout<<(char)(ch[i][j]);
        }
        cout<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>t;
    while(t--){
        cin>>n>>m;
        newop="";
        for(int i=1;i<=cnt;i++) for(int j=0;j<=20;j++) to[i][j]=0;
        cnt=-1;
        for(int i=1;i<=n;i++){
            ch[i].clear();
            ch[i].push_back(0);
            for(int j=1;j<=m;j++){
                char OP;
                cin>>OP;
                if(OP=='.') ch[i].push_back(-1);
                else ch[i].push_back(OP);
            }
        }
        cin>>op;
        // for(int i=0;i<q;i++) work(op[i]);
        // for(int i=1;i<=n;i++){
            // for(int j=1;j<=m;j++) cout<<(char)(ch[i][j]);
            // cout<<endl;
        // }
        // return 0;
        newop+=op[0];cnt++;
        for(int i=1;i<op.length();i++){
            if((op[i-1]=='U'||op[i-1]=='D')&&(op[i]=='U'||op[i]=='D')) newop[cnt]=op[i];
            else if((op[i-1]=='L'||op[i-1]=='R')&&(op[i]=='L'||op[i]=='R')) newop[cnt]=op[i];
            else newop+=op[i],cnt++;
        }
        // cout<<newop<<endl;
        work(newop[0]);
        if(cnt==0){
            print();
            continue;
        }
        work(newop[1]);
        if(cnt==1){
            print();
            continue;
        }
        if(newop[0]=='U'&&newop[1]=='L') pos=1;
        if(newop[0]=='U'&&newop[1]=='R') pos=2;
        if(newop[0]=='D'&&newop[1]=='L') pos=4;
        if(newop[0]=='D'&&newop[1]=='R') pos=3;
        if(newop[0]=='L'&&newop[1]=='U') pos=1;
        if(newop[0]=='R'&&newop[1]=='U') pos=2;
        if(newop[0]=='L'&&newop[1]=='D') pos=4;
        if(newop[0]=='R'&&newop[1]=='D') pos=3;
        op=newop;q=cnt;
        newop="";cnt=-1;
        deque<char> s;
        for(int i=2;i<=q;i++){
            int lastpos=pos;
            if(pos==1&&op[i]=='D') pos=4;
            if(pos==1&&op[i]=='R') pos=2;
            if(pos==2&&op[i]=='D') pos=3;
            if(pos==2&&op[i]=='L') pos=1;
            if(pos==3&&op[i]=='U') pos=2;
            if(pos==3&&op[i]=='L') pos=4;
            if(pos==4&&op[i]=='U') pos=1;
            if(pos==4&&op[i]=='R') pos=3;
            if(!s.empty()){
                if(s.back()=='U'&&op[i]=='D'){s.pop_back();continue;}
                if(s.back()=='D'&&op[i]=='U'){s.pop_back();continue;}
                if(s.back()=='L'&&op[i]=='R'){s.pop_back();continue;}
                if(s.back()=='R'&&op[i]=='L'){s.pop_back();continue;}
            }
            s.push_back(op[i]);
            if(lastpos==1&&(s.back()=='U'||s.back()=='L')){s.pop_back();continue;}
            if(lastpos==2&&(s.back()=='U'||s.back()=='R')){s.pop_back();continue;}
            if(lastpos==3&&(s.back()=='D'||s.back()=='R')){s.pop_back();continue;}
            if(lastpos==4&&(s.back()=='D'||s.back()=='L')){s.pop_back();continue;}
        }
        while(!s.empty()){
            newop+=s.front();
            s.pop_front();
        }
        // cout<<newop<<endl;
        if(newop.length()<=4){
            for(int i=0;i<newop.length();i++) work(newop[i]);
            print();
            continue;
        }
        cnt=0;
        mp[0]=0;
        for(int i=1;i<=n;i++){
            num[i].clear();
            num[i].push_back(0);
            for(int j=1;j<=m;j++){
                if(ch[i][j]!=-1){
                    mp[++cnt]=ch[i][j];
                    ch[i][j]=cnt;
                    num[i].push_back(cnt);
                }
                else ch[i][j]=-1,num[i].push_back(-1);
            }
        }
        // for(int i=1;i<=n;i++){
            // for(int j=1;j<=m;j++) cout<<ch[i][j]<<" ";
            // cout<<endl;
        // }
        for(int i=0;i<4;i++) work(newop[i]);
        for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(num[i][j]!=-1) to[num[i][j]][0]=ch[i][j];
        for(int i=1;i<=20;i++) for(int j=1;j<=cnt;j++) to[j][i]=to[to[j][i-1]][i-1];
        int len=newop.length()/4;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(num[i][j]==-1){
                    ch[i][j]=num[i][j];
                    continue;
                }
                for(int p=0;(1<<p)<=len;p++){
                    if(len&(1<<p)){
                        num[i][j]=to[num[i][j]][p];
                    }
                }
                ch[i][j]=mp[num[i][j]];
            }
        }
        for(int i=len*4;i<newop.length();i++) work(newop[i]);
        print();
    }
    return 0;
}

LOADING

每周好题分享

第一周（2025/03/17~2025/03/23）

T1

T2

第二周（2025/03/24~2025/03/30）

T1

T2

第三周（2025/03/31-2025/04/06）

T1

T2

第四周（2025/04/07-2025/04/13）

T1

T2

第五周（2025/04/14-2025/04/20）

T1

T2

第六周（2025/04/21-2025/04/27）

第七周（2025/06/02-2025/06/08）

T1

T2

第八周（2025/06/09-2025/06/29）

T1

T2