Travel Notes

Day 0

报到，领了纪念品，买了一顶帽子（衣服一件要150，好贵啊）。

在学校逛了一下午，环境不错。不过为什么三面环山台风来了会非常安全（？

吃完晚饭先串寝划水，之后背了一会儿笔试，然后去洗澡，但我没用过这个插卡取热水的装置，洗的是冷水。。。

Day 1

本来说今天没有安排，结果中午在食堂听到通知说下午笔试。

进笔试场随便找了个位置坐下，开始还以为是和 uoj 类似的提交答案的方式，旁边开了个 gedit 敲答案，做了一会儿才发现竟然可以直接点击选项选择（

有一道题大概是问在工作人员宣布 NOI 机试开始前，是否可以动键盘和鼠标，我想起来在某年 NOIP，工作人员一直在说”进入以后不要动电脑“，再结合笔试题库不能提前登录系统，就猜不能动，然后最后成绩 100 分。

Day 2

早上安排看奥运会开幕式，下午自行安排。

我没有去看奥运会开幕式（我不知道在哪里看），不过问题也不大，之后可以自己看。

复习了一下各种模板，主要是我写的不太熟练的一些ds。

Day 3

要求 8:30 到赛场门口，进场之后才知道 9:00 开始。

T1：做的操作就是 LCT 的 Access，但是暴力询问复杂度好像没有保证；

T2：路径计数？奇数减偶数？我先蒙在鼓里。

T3：这个题的询问方式和【NOIP2018】保卫王国有点像，不会又是什么奇怪 dp 优化吧。

先做 T1，因为没有修改，而没有修改的 LCT 大多可以用树链剖分代替，于是我就想重链剖分。

重儿子的轻重记真实的轻重，轻儿子的轻重要和父亲将所有儿子都设为轻儿子的时间另行比较。

有一些细节，就是重儿子的轻重是真实的，对于一条重链，要把最后节点的重儿子也变轻。

写完包括对拍等一共花了 2h 多。

再做 T2，刚开始考虑 $k=2$，发现相邻的正负系数就是对于排列 $p$，若所有 $(i,p_i)$ 有边则贡献为 $(-1)^{\sigma(p)}$，否则为 $0$，$\sigma(p)$ 表示排列 $p$ 的逆序对数，然后当时感觉这个只能 $2^n$，就没有写。

再看 T3，先缩点，然后拓扑排序，就是一个外向树的形式，然后分类讨论了很长时间 $k=0/1$ 才通过大样例。

然后时间就已经不多了，就赶紧写了 T2 的 40pts，检查一下时间就结束了。100+40+64=204

出场听到虚树两个字，突然想到 T3 可以直接虚树就不用分类讨论直接 $AC$。

回到寝室看群里有人说啥 CF，LGV 引理，Cauchy-Binet 公式啥的。听说有 20~30 个 AK。

Day4

下午有嘉年华活动，像我这样的菜鸡连 U 盘都没拿到。

结束之后发现隔壁的厅在放奥运会女子双人跳水，中国夺冠了。

晚上又复习了一遍模板。

Day5

今天是正常 8:00 开始考试。

T1：刚开始还以为真的是个通信题，看到后面发现就是套了一个通信题的壳。

T2：感觉这个式子非常有趣（考完才知道这个是连分数）。

T3：第二个样例解释很长，还用了容斥原理，题目的数据范围有部分分 $n\leq 16$。

感觉这个 $T1$ 没什么头绪，又发现这个字典相当于是随机的，于是认为这个建 trie 树然后在上面暴力 dfs 应该比较快？写了一下，但是 $k$ 有 $15$，光 $2^k$ 就很大了，而且空间还开不下。又想了想随机，正确性不高，就先把数组开小一点。

再看 $T2$，开始完全没有思路，因为不知道怎么保证分子分母互质。

先看特殊性质 $A$，发现答案是斐波那契数列相邻两项的比值，显然是互质的，就写了这档部分分。

然后看原问题，发现好像一定是互质的，然后又写了 $O(nq)$。

做 $T3$，将容斥扩展到一般情况，得到了一个 $O(2^n n^2m)$ 的做法。

然后想了想，性质 $A$ 只和状态中的 $1$ 的个数有关，就写了 $O(n^3m)$。

之后没有想出其它的。40+35+32=107。

中午吃饭和一位以前认识的同学吹水，他告诉我 T1 通过鸽巢原理可以发现把每个串 16 个位分成一块，显然至少有一块和原串是相同的（这么简单我竟然没做出来），T2 是连分数，LibreOJ NOI Round 有关于这个的题目（后来发现他进队了 Orz）。

下午听讲评，好像并没有规定听讲评是不是要坐在闭幕式的位置，T2 并没有讲，到了 gxxj 时因为二楼实在太热了跑路了。

Day6

我的分数只上了 Ag 线，而且由于不是正式选手也没有牌。

中午吃完饭就跑路了。

Solution

D1T1

没啥好说的。就是树剖后重儿子的轻重是真的，轻儿子的轻重需要讨论。

线段树维护每个点成为重儿子的时刻和每个点将所有儿子都变成轻儿子的时刻。

询问时往上跳，轻重链切换时讨论一下即可。时间复杂度 $O(n\log^2 n)$.

D1T2

先考虑 $k=2$ 怎么做，记 $A$ 为邻接矩阵，问题相当于： $$ \sum_{p \text{是} {1,2,\cdots,n} \text{的排列}} (-1)^{\sigma(p)}\prod_{i=1}^n A_{i,p_i} $$ 其中 $\sigma(p)$ 表示排列 $p$ 的逆序对数，而这个式子就是 $det(A)$ 的定义式。

再考虑 $n_1=n_2=\cdots=n_k$，任意两列的选择方案式独立的，那么答案就是 $(k-1)$ 个行列式的乘积。

又因为 $det(A)\times det(B)=det(A\times B)$，所以答案即为所有矩阵乘积的行列式。

最后考虑原问题，其实上面的结论依然成立，具体证明可以使用 Cauchy-Binet 公式进行数学归纳。

#include<bits/stdc++.h>
using namespace std;
const int Mod=998244353;
typedef long long ll;
int T,k,n[110],m[110];
struct Matrix{
    int v[210][210];
} A,B;
ll qpow(ll x,int a){
    ll res=1;
    while (a){
        if (a&1) res=res*x%Mod;
        x=x*x%Mod; a>>=1;
    }
    return res;
}
Matrix mul(const Matrix &A,const Matrix &B,int n,int m,int s){
    Matrix res;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=s;j++)
            res.v[i][j]=0;
    for (int i=1;i<=n;i++)
        for (int k=1;k<=m;k++)
            if (A.v[i][k])
                for (int j=1;j<=s;j++)
                    res.v[i][j]=(res.v[i][j]+1ll*A.v[i][k]*B.v[k][j])%Mod;
    return res;
}
int det(Matrix &A,int n){
    int res=1;
    for (int i=1;i<=n;i++){
        if (!A.v[i][i]){
            res=Mod-res;
            for (int j=i+1;j<=n;j++)
                if (A.v[j][i]){
                    for (int k=i;k<=n;k++) swap(A.v[i][k],A.v[j][k]);
                    break;
                }
            if (!A.v[i][i]) return 0;
        }
        ll inv=qpow(A.v[i][i],Mod-2);
        for (int j=i+1;j<=n;j++){
            ll tmp=Mod-inv*A.v[j][i]%Mod;
            for (int k=i;k<=n;k++) A.v[j][k]=(A.v[j][k]+tmp*A.v[i][k])%Mod;
        }
    }
    for (int i=1;i<=n;i++) res=1ll*res*A.v[i][i]%Mod;
    return res;
}
int main(){
    freopen("xpath.in","r",stdin);
    freopen("xpath.out","w",stdout);
    scanf("%d",&T);
    while (T--){
        scanf("%d",&k);
        for (int i=1;i<=k;i++) scanf("%d",&n[i]);
        for (int i=1;i<k;i++) scanf("%d",&m[i]);
        int u,v;
        for (int i=1;i<k;i++){
            for (int x=1;x<=n[i];x++)
                for (int y=1;y<=n[i+1];y++)
                    B.v[x][y]=0;
            for (int j=1;j<=m[i];j++){
                scanf("%d%d",&u,&v);
                B.v[u][v]=1;
            }
            if (i==1) A=B;
            else A=mul(A,B,n[i-1],n[i],n[i+1]);
        }
        printf("%d\n",det(A,n[1]));
    }
    return 0;
}

D1T3

先缩点，然后原图变成了一张 $DAG$。设 $x\rightarrow y$ 表示有一条 $x$ 到 $y$ 的边，$x\Rightarrow y$ 从 $x$ 出发能到达 $y$。

观察 $x\Rightarrow z,y\Rightarrow z$ 则有 $x\Rightarrow y/y\Rightarrow x$ 这个条件。

将其弱化为 $x\rightarrow z,y\rightarrow z$ 则有 $x\Rightarrow y/y\Rightarrow x$，若 $x\Rightarrow y$ 则删除 $x\rightarrow z$ 的边，否则删除 $y\rightarrow z$ 的边。

那么原图等价于一张没有点入度 $\geq 2$ 的图，而根据原图弱连通可以发现这张图一定为一棵外向树。

可以使用拓扑排序，每个点的父亲为连向它的点中拓扑序最大的点。

询问的话将读入的节点建立虚树，然后看树上的每个点和每条边是否能再 $s,t$ 的路径上即可。

树剖求LCA

#include<bits/stdc++.h>
using namespace std;
int n,m,q,k,cnt,rt,tot,len,bel[310000],ind[310000],p[310000];
int top,sz[310000],fa[310000],dep[310000],son[310000],sum[310000];
int uu[310000],vv[310000],cc[310000],num[310000],tp[310000],s[310000];
int dtime,dfn[310000],low[310000],head,tail,que[310000];
bool ins[310000],vis[2][310000];
vector<int> old[310000],edge[310000];
int edgenum,vet[610000],Next[610000],Head[310000];
void addedge(int u,int v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
char Getchar(){
    static char now[1<<20],*S,*T;
    if (T==S){
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
int read(){
    int x=0,f=1;
    char ch=Getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=Getchar();
    }
    while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
    return x*f;
}
void tarjan(int u){
    dtime++; dfn[u]=dtime; low[u]=dtime;
    s[++top]=u; ins[u]=true;
    for (int v:old[u])
        if (!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else
            if (ins[v]) low[u]=min(low[u],dfn[v]);
    if (low[u]==dfn[u]){
        cnt++;
        while (s[top]!=u){
            bel[s[top]]=cnt; ins[s[top]]=false;
            num[cnt]++; top--;
        }
        bel[s[top]]=cnt; ins[s[top]]=false;
        num[cnt]++; top--;
    }
}
void dfs1(int u,int f){
    sz[u]=1; fa[u]=f; dep[u]=dep[f]+1; sum[u]=sum[f]+num[u];
    for (int v:edge[u])
        if (v!=f){
            dfs1(v,u); sz[u]+=sz[v];
            if (sz[son[u]]<sz[v]) son[u]=v;
        }
}
void dfs2(int u,int t){
    tp[u]=t; dfn[u]=++dtime;
    if (!son[u]) return;
    dfs2(son[u],t);
    for (int v:edge[u])
        if (v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
int LCA(int u,int v){
    while (tp[u]!=tp[v]){
        if (dep[tp[u]]>dep[tp[v]]) u=fa[tp[u]];
        else v=fa[tp[v]];
    }
    if (dep[u]<dep[v]) return u;
    else return v;
}
bool cmp(int x,int y){ return dfn[x]<dfn[y];}
void addpush(int u,int v,int c){
    len++; uu[len]=u; vv[len]=v; cc[len]=c;
}
void addpush(int u,int v){
    len++; uu[len]=u; vv[len]=v; cc[len]=sum[fa[v]]-sum[u];
}
void build(){
    p[++tot]=rt; sort(p+1,p+tot+1,cmp); tot=unique(p+1,p+tot+1)-p-1;

    int top=1,tmp=tot,u; s[1]=rt;
    for (int i=2;i<=tmp;i++){
        u=p[i];
        if (top==1){ s[++top]=u; continue;}
        int l=LCA(s[top],u);

        while (top>1&&dep[s[top-1]]>=dep[l]) addpush(s[top-1],s[top]),top--;
        if (s[top]!=l) addpush(l,s[top]),s[top]=l,p[++tot]=l;
        s[++top]=u;
    }
    while (top>1) addpush(s[top-1],s[top]),top--;
}
void get_DAG(){
    dtime=0;
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;i++)
        for (int v:old[i])
            if (bel[i]!=bel[v]){
                addedge(bel[i],bel[v]);
                ind[bel[v]]++;
            }
}
void topo_sort(){
    head=1; tail=0;
    for (int i=1;i<=cnt;i++)
        if (!ind[i]) que[++tail]=i,rt=i;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e]){
            ind[vet[e]]--;
            if (!ind[vet[e]]){
                fa[vet[e]]=u;
                que[++tail]=vet[e];
            }
        }
    }
}
int solve(int u,int v){
    edgenum=0;
    for (int i=1;i<=tot;i++) Head[p[i]]=0;
    for (int i=1;i<=len;i++) addedge(uu[i],vv[i]);
    head=1; tail=1; que[1]=u; vis[0][u]=true;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e])
            if (!vis[0][vet[e]]){
                vis[0][vet[e]]=true;
                que[++tail]=vet[e];
            }
    }

    edgenum=0;
    for (int i=1;i<=tot;i++) Head[p[i]]=0;
    for (int i=1;i<=len;i++) addedge(vv[i],uu[i]);
    head=1; tail=1; que[1]=v; vis[1][v]=true;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e])
            if (!vis[1][vet[e]]){
                vis[1][vet[e]]=true;
                que[++tail]=vet[e];
            }
    }
    for (int i=1;i<=tot;i++) Head[p[i]]=0;

    int ans=0;
    for (int i=1;i<=len;i++)
        if (vis[0][uu[i]]&&vis[1][vv[i]]) ans+=cc[i];
    for (int i=1;i<=tot;i++){
        if (vis[0][p[i]]&&vis[1][p[i]]) ans+=num[p[i]];
        vis[0][p[i]]=false; vis[1][p[i]]=false;
    }
    return ans;
}
int main(){
    freopen("celebration.in","r",stdin);
    freopen("celebration.out","w",stdout);
    n=read(); m=read(); q=read(); k=read();
    int u,v;
    for (int i=1;i<=m;i++){
        u=read(); v=read();
        old[u].push_back(v);
    }
    get_DAG(); topo_sort();
    for (int i=1;i<=cnt;i++)
        if (i!=rt) edge[fa[i]].push_back(i);
    dtime=0; dfs1(rt,0); dfs2(rt,rt);
    while (q--){
        tot=2; len=0;
        p[1]=read(); p[2]=read();
        for (int i=1;i<=k;i++){
            tot++; p[tot]=read();
            tot++; p[tot]=read();
        }
        for (int i=1;i<=tot;i++) p[i]=bel[p[i]];
        for (int i=3;i<=tot;i+=2) addpush(p[i],p[i+1],0);
        u=p[1]; v=p[2]; build();
        printf("%d\n",solve(u,v));
    }
    return 0;
}

欧拉序RMQ求LCA

#include<bits/stdc++.h>
using namespace std;
int n,m,q,k,cnt,rt,tot,len,bel[310000],ind[310000],p[310000],f[21][610000];
int top,Q[610000],fa[310000],dep[310000],Log2[610000],sum[310000];
int uu[310000],vv[310000],cc[310000],num[310000],s[310000];
int dtime,dfn[310000],low[310000],head,tail,que[310000];
bool ins[310000],vis[2][310000];
vector<int> old[310000],edge[310000];
int edgenum,vet[610000],Next[610000],Head[310000];
void addedge(int u,int v){
    vet[++edgenum]=v;
    Next[edgenum]=Head[u];
    Head[u]=edgenum;
}
char Getchar(){
    static char now[1<<20],*S,*T;
    if (T==S){
        T=(S=now)+fread(now,1,1<<20,stdin);
        if (T==S) return EOF;
    }
    return *S++;
}
int read(){
    int x=0,f=1;
    char ch=Getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=Getchar();
    }
    while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=Getchar();
    return x*f;
}
void tarjan(int u){
    dtime++; dfn[u]=dtime; low[u]=dtime;
    s[++top]=u; ins[u]=true;
    for (int v:old[u])
        if (!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        } else
            if (ins[v]) low[u]=min(low[u],dfn[v]);
    if (low[u]==dfn[u]){
        cnt++;
        while (s[top]!=u){
            bel[s[top]]=cnt; ins[s[top]]=false;
            num[cnt]++; top--;
        }
        bel[s[top]]=cnt; ins[s[top]]=false;
        num[cnt]++; top--;
    }
}

void dfs(int u,int f){
    dep[u]=dep[f]+1; sum[u]=sum[f]+num[u]; Q[++dtime]=u; dfn[u]=dtime;
    for (int v:edge[u]){
        if (v==f) continue;
        dfs(v,u); Q[++dtime]=u;
    }
}
void buildst(){
    Log2[0]=-1;
    for (int i=1;i<=dtime;i++){
        f[0][i]=Q[i];
        Log2[i]=Log2[i>>1]+1;
    }
    int x,y;
    for (int j=1;j<=20;j++)
        for (int i=1;i+(1<<j)-1<=dtime;i++){
            x=f[j-1][i]; y=f[j-1][i+(1<<(j-1))];
            f[j][i]=(dep[x]<dep[y]?x:y);
        }
}
int LCA(int u,int v){
    u=dfn[u]; v=dfn[v];
    if (u>v) swap(u,v);
    int k=Log2[v-u+1];
    int x=f[k][u],y=f[k][v-(1<<k)+1];
    return (dep[x]<dep[y]?x:y);
}
bool cmp(int x,int y){ return dfn[x]<dfn[y];}
void addpush(int u,int v,int c){
    len++; uu[len]=u; vv[len]=v; cc[len]=c;
}
void addpush(int u,int v){
    len++; uu[len]=u; vv[len]=v; cc[len]=sum[fa[v]]-sum[u];
}
void build(){
    p[++tot]=rt; sort(p+1,p+tot+1,cmp); tot=unique(p+1,p+tot+1)-p-1;

    int top=1,tmp=tot,u; s[1]=rt;
    for (int i=2;i<=tmp;i++){
        u=p[i];
        if (top==1){ s[++top]=u; continue;}
        int l=LCA(s[top],u);

        while (top>1&&dep[s[top-1]]>=dep[l]) addpush(s[top-1],s[top]),top--;
        if (s[top]!=l) addpush(l,s[top]),s[top]=l,p[++tot]=l;
        s[++top]=u;
    }
    while (top>1) addpush(s[top-1],s[top]),top--;
}
void get_DAG(){
    dtime=0;
    for (int i=1;i<=n;i++)
        if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;i++)
        for (int v:old[i])
            if (bel[i]!=bel[v]){
                addedge(bel[i],bel[v]);
                ind[bel[v]]++;
            }
}
void topo_sort(){
    head=1; tail=0;
    for (int i=1;i<=cnt;i++)
        if (!ind[i]) que[++tail]=i,rt=i;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e]){
            ind[vet[e]]--;
            if (!ind[vet[e]]){
                fa[vet[e]]=u;
                que[++tail]=vet[e];
            }
        }
    }
}
int solve(int u,int v){
    edgenum=0;
    for (int i=1;i<=tot;i++) Head[p[i]]=0;
    for (int i=1;i<=len;i++) addedge(uu[i],vv[i]);
    head=1; tail=1; que[1]=u; vis[0][u]=true;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e])
            if (!vis[0][vet[e]]){
                vis[0][vet[e]]=true;
                que[++tail]=vet[e];
            }
    }

    edgenum=0;
    for (int i=1;i<=tot;i++) Head[p[i]]=0;
    for (int i=1;i<=len;i++) addedge(vv[i],uu[i]);
    head=1; tail=1; que[1]=v; vis[1][v]=true;
    while (head<=tail){
        int u=que[head++];
        for (int e=Head[u];e;e=Next[e])
            if (!vis[1][vet[e]]){
                vis[1][vet[e]]=true;
                que[++tail]=vet[e];
            }
    }
    for (int i=1;i<=tot;i++) Head[p[i]]=0;

    int ans=0;
    for (int i=1;i<=len;i++)
        if (vis[0][uu[i]]&&vis[1][vv[i]]) ans+=cc[i];
    for (int i=1;i<=tot;i++){
        if (vis[0][p[i]]&&vis[1][p[i]]) ans+=num[p[i]];
        vis[0][p[i]]=false; vis[1][p[i]]=false;
    }
    return ans;
}
int main(){
    freopen("celebration.in","r",stdin);
    freopen("celebration.out","w",stdout);
    n=read(); m=read(); q=read(); k=read();
    int u,v;
    for (int i=1;i<=m;i++){
        u=read(); v=read();
        old[u].push_back(v);
    }
    get_DAG(); topo_sort();
    for (int i=1;i<=cnt;i++)
        if (i!=rt) edge[fa[i]].push_back(i);
    dtime=0; dfs(rt,0); buildst();
    while (q--){
        tot=2; len=0;
        p[1]=read(); p[2]=read();
        for (int i=1;i<=k;i++){
            tot++; p[tot]=read();
            tot++; p[tot]=read();
        }
        for (int i=1;i<=tot;i++) p[i]=bel[p[i]];
        for (int i=3;i<=tot;i+=2) addpush(p[i],p[i+1],0);
        u=p[1]; v=p[2]; build();
        printf("%d\n",solve(u,v));
    }
    return 0;
}

D2T1

通过鸽巢原理可以发现把每个字典中的串 16 个位分成一块，显然至少有一块和询问串是相同的。

暴力枚举是哪一块相同，对应字典中的串的数量期望是 8 个。然后比对是否为答案可以一块一块算 popcount。

常数大概是 $16\times 8\times 8=1024$。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef pair<int,int> pii;
int n,m,ans,k,p[256],a[400005][16],b[16],popc[110000]; ull a1,a2;
bool s[256]; string t;
vector<pii> vec[25];
ull myRand(ull &k1,ull &k2){
    ull k3=k1,k4=k2;
    k1=k4;
    k3^=(k3<<23);
    k2=k3^k4^(k3>>17)^(k4>>26);
    return k2+k4;
}
void gen(int n,ull a1,ull a2){
    for (int i=1;i<=n;i++){
        for (int j=0;j<256;j++)
            s[j]=(myRand(a1,a2)&(1ull<<32))?1:0;
        int now=0;
        for (int j=0;j<256;j+=16){
            for (int k=0;k<16;k++)
                a[i][now]=(a[i][now]<<1)|s[p[j+k]];
            vec[now].push_back(pii(a[i][now],i));
            now++;
        }
    }
    for (int k=0;k<16;k++) sort(vec[k].begin(),vec[k].end());
}
inline void check(int x){
    if (popc[a[x][0]^b[0]]+popc[a[x][1]^b[1]]+popc[a[x][2]^b[2]]+popc[a[x][3]^b[3]]+
        popc[a[x][4]^b[4]]+popc[a[x][5]^b[5]]+popc[a[x][6]^b[6]]+popc[a[x][7]^b[7]]+
        popc[a[x][8]^b[8]]+popc[a[x][9]^b[9]]+popc[a[x][10]^b[10]]+popc[a[x][11]^b[11]]+
        popc[a[x][12]^b[12]]+popc[a[x][13]^b[13]]+popc[a[x][14]^b[14]]+popc[a[x][15]^b[15]]<=k) ans=true;
}
int main(){
    freopen("qi.in","r",stdin);
    freopen("qi.out","w",stdout);
    srand(19260817);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for (int i=0;i<65536;i++) popc[i]=popc[i>>1]+(i&1);
    for (int i=0;i<256;i++) p[i]=i;
    random_shuffle(p,p+256);
    cin>>n>>m>>a1>>a2;
    gen(n,a1,a2); ans=0;
    for (int i=1;i<=m;i++){
        cin>>t>>k; int loc=0;
        for (int j=0;j<256;j+=4){
            for (int k=0;k<4;k++)
                s[j+k]=((t[loc]>='A'?t[loc]-'A'+10:t[loc]-'0')>>(3-k))&1;
            loc++;
        }
        if (ans)
            for (int j=0;j<256;j++) s[j]^=1;
        ans=0;
        int now=0;
        for (int j=0;j<256;j+=16){
            b[now]=0;
            for (int k=0;k<16;k++)
                b[now]=(b[now]<<1)|s[p[j+k]];
            now++;
        }
        for (int i=0;i<16&&!ans;i++){
            int pos=lower_bound(vec[i].begin(),vec[i].end(),pii(b[i],0))-vec[i].begin();
            while (pos<(int)vec[i].size()&&vec[i][pos].first==b[i]&&!ans) check(vec[i][pos].second),pos++;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

D2T2

可以证明，$W$ 操作等价于在序列后加入 $0,1$，$E$ 操作等价于在序列后加入 $0,-1,1,1$。

每个数等价于一个矩阵，$0$ 等价于 $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$，$1$ 等价于 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$，$-1$ 等价于$\begin{bmatrix} -1 & 1 \\ 1 & 0 \end{bmatrix}$。

而矩阵有结合律，$W$ 为 $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}=\begin{bmatrix} 1 & 0 \\ 1 & 1 \end{bmatrix}$，$E$ 为 $\begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}\times\begin{bmatrix} -1 & 1 \\ 1 & 0 \end{bmatrix}\times\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\times\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}=\begin{bmatrix} 2 & 1 \\ -1 & 0 \end{bmatrix}$。

也可以采取其它的方法推出 $W,E$ 对应的矩阵，比如解矩阵方程（这个方法可能更容易想到）。

那么翻转和反转都可以通过维护 $fhq-treap$ 解决。设 $n,q$ 同阶，时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod=998244353;
int n,q,rt,B,C,D; char s[110000],op[11];
int tot,ls[210000],rs[210000],sz[210000],val[210000];
mt19937 rand_num(19260817);
struct node{
    int v[2][2];
    node operator*(const node &a) const{
        node res;
        res.v[0][0]=(1ll*v[0][0]*a.v[0][0]+1ll*v[0][1]*a.v[1][0])%Mod;
        res.v[0][1]=(1ll*v[0][0]*a.v[0][1]+1ll*v[0][1]*a.v[1][1])%Mod;
        res.v[1][0]=(1ll*v[1][0]*a.v[0][0]+1ll*v[1][1]*a.v[1][0])%Mod;
        res.v[1][1]=(1ll*v[1][0]*a.v[0][1]+1ll*v[1][1]*a.v[1][1])%Mod;
        return res;
    }
} num[4][210000],tmp[2];
bool rev[210000],flip[210000];
void pushrev(int u){
    if (!u) return;
    rev[u]^=1; swap(ls[u],rs[u]); node tmp;
    tmp=num[0][u]; num[0][u]=num[1][u]; num[1][u]=tmp;
    tmp=num[2][u]; num[2][u]=num[3][u]; num[3][u]=tmp;
}
void pushflip(int u){
    if (!u) return;
    val[u]^=1; flip[u]^=1; node tmp;
    tmp=num[0][u]; num[0][u]=num[2][u]; num[2][u]=tmp;
    tmp=num[1][u]; num[1][u]=num[3][u]; num[3][u]=tmp;
}
void pushup(int u){
    sz[u]=sz[ls[u]]+1+sz[rs[u]];
    num[0][u]=num[0][ls[u]]*tmp[val[u]]*num[0][rs[u]];
    num[1][u]=num[1][rs[u]]*tmp[val[u]]*num[1][ls[u]];
    num[2][u]=num[2][ls[u]]*tmp[val[u]^1]*num[2][rs[u]];
    num[3][u]=num[3][rs[u]]*tmp[val[u]^1]*num[3][ls[u]];
}
void pushdown(int u){
    if (rev[u]){
        pushrev(ls[u]); pushrev(rs[u]);
        rev[u]=0;
    }
    if (flip[u]){
        pushflip(ls[u]); pushflip(rs[u]);
        flip[u]=0;
    }
}
int Merge(int x,int y){
    if (!x||!y) return x|y;
    if (rand_num()%(sz[x]+sz[y])<sz[x]){
        pushdown(x);
        rs[x]=Merge(rs[x],y); pushup(x);
        return x;
    } else{
        pushdown(y);
        ls[y]=Merge(x,ls[y]); pushup(y);
        return y;
    }
}
void Split(int now,int k,int &x,int &y){
    if (!now){
        x=0; y=0;
        return;
    }
    pushdown(now);
    if (k<=sz[ls[now]]){
        y=now;
        Split(ls[now],k,x,ls[now]);
    } else{
        x=now;
        Split(rs[now],k-sz[ls[now]]-1,rs[now],y);
    }
    pushup(now);
}
int Newnode(int v){
    tot++;
    sz[tot]=1; val[tot]=v;
    num[0][tot]=tmp[v]; num[1][tot]=tmp[v];
    num[2][tot]=tmp[v^1]; num[3][tot]=tmp[v^1];
    return tot;
}
void print(){
//    printf("#%d %d\n",num[0][rt].v[0][0],num[0][rt].v[0][1]);
//    printf("#%d %d\n",num[0][rt].v[1][0],num[0][rt].v[1][1]);
    printf("%d %d\n",num[0][rt].v[0][0],(num[0][rt].v[0][0]+num[0][rt].v[1][0])%Mod);
}
void Append(int v){
    rt=Merge(rt,Newnode(v));
}
int x,y,z;
void Flip(int l,int r){
    Split(rt,r,y,z); Split(y,l-1,x,y);
    pushflip(y);
    rt=Merge(Merge(x,y),z);
}
void Reverse(int l,int r){
    Split(rt,r,y,z); Split(y,l-1,x,y);
    pushrev(y);
    rt=Merge(Merge(x,y),z);
}
int main(){
    freopen("code.in","r",stdin);
    freopen("code.out","w",stdout);
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    tmp[0].v[0][0]=2; tmp[0].v[0][1]=1;
    tmp[0].v[1][0]=Mod-1; tmp[0].v[1][1]=0;
    tmp[1].v[0][0]=1; tmp[1].v[0][1]=0;
    tmp[1].v[1][0]=1; tmp[1].v[1][1]=1;
    for (int i=0;i<4;i++){
        num[i][0].v[0][0]=1; num[i][0].v[0][1]=0;
        num[i][0].v[1][0]=0; num[i][0].v[1][1]=1;
    }
    //0 原，1 翻，2 反，3 翻反
    //0 E，1 W
    for (int i=1;i<=n;i++) Append(s[i]=='W');
    print();
    int l,r;
    while (q--){
        scanf("%s",op);
        if (op[0]=='A'){
            scanf("%s",s); n++;
            Append(s[0]=='W');
        } else{
            scanf("%d%d",&l,&r);
            if (op[0]=='F') Flip(l,r);
            else Reverse(l,r);
        }
        print();
    }
    return 0;
}

D2T3

先讲讲 $O(2^nn^2m)$ 的暴力容斥，就 $2^n$ 枚举 $p$ 的合法下标集合，钦定这些合法。

先考虑机器人是否爆炸，否则考虑每个位置的限制 $0/1/x/1-x$。

• 如果有 $0,1$ 或 $x,1-x$ 同时存在，方案数为 $1$（即必须为空）。
• 如果有 $0\ or\ 1$ 且 $x\ or\ 1-x$ 同时存在，方案数为 $2$（即必须为空或某个数）。
• 否则方案数为 $3$。

然后优化，枚举 $p$ 中下标最大的位置，设为 $r$。

先考虑机器人是否爆炸，否则可以对前 $r$ 个位置 $dp$。

设 $dp[0/1][i][s]$ 表示$

因为机器人没有爆炸，所以不可能从 $

而状态的数量显然最多 $2^{\min(n-r,r)}$ ，所以复杂度为 $O(n^2m2^{n/2})$。

考虑继续优化，用 $bitset$ 记录 $bs[j][4]$ 若当前列 $-j$ 为合法起点，那么当前列哪些行必须为 $0/1/x/-x$。之后的方案数就可以用 $bitset$ 解决。

时间复杂度 $O(n^2\frac{m}{\omega}2^{n/2})$。

STL的bitset

#include<bits/stdc++.h>
#define cerr cout
using namespace std;
const int Mod=1e9+7;
int n,m,dp[2][2][71000],pw2[71000],pw3[71000]; char s[110];
vector<int> vec[1100],num[1100]; bool flag[4];
bitset<1005> bs[4][35],f[71000][4],all,v1,v2;
inline int add(int x,int y){ return x+y>=Mod?x+y-Mod:x+y;}
inline int dec(int x,int y){ return x-y<0?x-y+Mod:x-y;}
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%s",s); int len=strlen(s);
        vec[i].push_back(2);
        for (int j=0;j<len;j++)
            if (s[j]=='R') vec[i].push_back(2);
            else if (s[j]=='*') vec[i].back()^=1;
            else vec[i].back()=s[j]-'0';
        num[vec[i].size()].push_back(i);
    }
    pw2[0]=1; pw3[0]=1;
    for (int i=1;i<=n*m;i++){
        pw2[i]=add(pw2[i-1],pw2[i-1]);
        pw3[i]=add(add(pw3[i-1],pw3[i-1]),pw3[i-1]);
    }
    int ans=pw3[n*m],tot=0;
    for (int i=1;i<=m;i++) all.set(i);
    for (int r=n;r>=0;r--){
        for (int u:num[n-r+1]){
            //钦定当前列-j为合法起点，那么当前列必须为0/1/2/3的是哪些行
            for (int j=0;j<vec[u].size();j++) bs[vec[u][j]][j].set(u);
            for (int j=vec[u].size();j<=n+2;j++) bs[2][j].set(u);
            tot++;
        }
        dp[0][0][0]=1; dp[0][1][0]=0;//dp[0/1][0/1][s] <i-(n-r)的列有没有选，当前在第i列，i-(n-r)..i列选的状态为s
        int limx,limy;
        int now=0,lst=1;
        for (int i=1;i<=r;i++){
            now^=1; lst^=1;
            limx=(1<<(min(n-r+1,i-1)))-1; limy=(1<<(min(n-r+1,i)))-1;
            for (int y=0;y<=1;y++)
                for (int s=0;s<=limy;s++)
                    dp[now][y][s]=0;
            for (int x=0;x<=1;x++)
                for (int s=0;s<=limx;s++){
                    int y=x|((s<<1)>limy);
                    if (i!=r) dp[now][y][(s<<1)&limy]=add(dp[now][y][(s<<1)&limy],dp[lst][x][s]);
                    dp[now][y][(s<<1|1)&limy]=dec(dp[now][y][(s<<1|1)&limy],dp[lst][x][s]);
                }
            for (int y=0;y<=1;y++){
                for (int j=0;j<min(n-r+1,i);j++)
                    for (int t=0;t<4;t++) f[1<<j][t]=bs[t][j];
                f[0][0]=0; f[0][1]=0; f[0][2]=((y||i<r)?all:0); f[0][3]=0;
                for (int s=0;s<=limy;s++){
                    for (int t=0;t<4;t++) f[s][t]=f[s^(s&-s)][t]|f[s&-s][t];
                    v1=(f[s][0]&f[s][1])|(f[s][2]&f[s][3]);
                    v2=(f[s][0]|f[s][1])&(f[s][2]|f[s][3])&(all^v1);
                    dp[now][y][s]=1ll*dp[now][y][s]*pw2[v2.count()]%Mod*pw3[tot-v1.count()-v2.count()]%Mod;
                }
            }

        }

        limy=(1<<(min(n-r+1,r)))-1;
        for (int i=1;i<=n-r;i++){
            for (int y=0;y<=1;y++){
                for (int j=0;j<min(n-r+1,r);j++)
                    for (int t=0;t<4;t++) f[1<<j][t]=bs[t][i+j];
                f[0][0]=0; f[0][1]=0; f[0][2]=(y?all:0); f[0][3]=0;
                for (int s=0;s<=limy;s++){
                    for (int t=0;t<4;t++) f[s][t]=f[s^(s&-s)][t]|f[s&-s][t];
                    v1=(f[s][0]&f[s][1])|(f[s][2]&f[s][3]);
                    v2=(f[s][0]|f[s][1])&(f[s][2]|f[s][3])&(all^v1);
                    dp[now][y][s]=1ll*dp[now][y][s]*pw2[v2.count()]%Mod*pw3[tot-v1.count()-v2.count()]%Mod;
                }
            }
        }
        for (int y=0;y<=1;y++){
            for (int s=0;s<=limy;s++){
                ans=dec(ans,dp[now][y][s]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

手写bitset

#include<bits/stdc++.h>
using namespace std;
const int Mod=1e9+7;
int n,m,dp[2][2][71000],pw2[71000],pw3[71000],ctz[71000]; char s[110];
vector<int> vec[1100],num[1100]; bool flag[4];
inline int add(int x,int y){ return x+y>=Mod?x+y-Mod:x+y;}
inline int dec(int x,int y){ return x-y<0?x-y+Mod:x-y;}
struct Bitset{
    unsigned v[32];
    int count(){
        int res=0;
        for (int i=0;i<32;i++) res+=ctz[v[i]>>16]+ctz[v[i]&65535];
        return res;
    }
    void set(int x){ v[x>>5]|=(1u<<(x&31));}
} bs[4][35],f[71000][4],all,v1,v2,o;
Bitset operator&(const Bitset &a,const Bitset &b){
    Bitset res;
    for (int i=0;i<32;i++) res.v[i]=a.v[i]&b.v[i];
    return res;
}
Bitset operator|(const Bitset &a,const Bitset &b){
    Bitset res;
    for (int i=0;i<32;i++) res.v[i]=a.v[i]|b.v[i];
    return res;
}
Bitset operator^(const Bitset &a,const Bitset &b){
    Bitset res;
    for (int i=0;i<32;i++) res.v[i]=a.v[i]^b.v[i];
    return res;
}
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    for (int i=0;i<65536;i++) ctz[i]=ctz[i>>1]+(i&1);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
        scanf("%s",s); int len=strlen(s);
        vec[i].push_back(2);
        for (int j=0;j<len;j++)
            if (s[j]=='R') vec[i].push_back(2);
            else if (s[j]=='*') vec[i].back()^=1;
            else vec[i].back()=s[j]-'0';
        num[vec[i].size()].push_back(i);
    }
    pw2[0]=1; pw3[0]=1;
    for (int i=1;i<=n*m;i++){
        pw2[i]=add(pw2[i-1],pw2[i-1]);
        pw3[i]=add(add(pw3[i-1],pw3[i-1]),pw3[i-1]);
    }
    int ans=pw3[n*m],tot=0;
    for (int i=1;i<=m;i++) all.set(i);
    for (int r=n;r>=0;r--){
        for (int u:num[n-r+1]){
            //钦定当前列-j为合法起点，那么当前列必须为0/1/2/3的是哪些行
            for (int j=0;j<vec[u].size();j++) bs[vec[u][j]][j].set(u);
            for (int j=vec[u].size();j<=n+2;j++) bs[2][j].set(u);
            tot++;
        }
        dp[0][0][0]=1; dp[0][1][0]=0;//dp[0/1][0/1][s] <i-(n-r)的列有没有选，当前在第i列，i-(n-r)..i列选的状态为s
        int limx,limy;
        int now=0,lst=1;
        for (int i=1;i<=r;i++){
            now^=1; lst^=1;
            limx=(1<<(min(n-r+1,i-1)))-1; limy=(1<<(min(n-r+1,i)))-1;
            for (int y=0;y<=1;y++)
                for (int s=0;s<=limy;s++)
                    dp[now][y][s]=0;
            for (int x=0;x<=1;x++)
                for (int s=0;s<=limx;s++){
                    int y=x|((s<<1)>limy);
                    if (i!=r) dp[now][y][(s<<1)&limy]=add(dp[now][y][(s<<1)&limy],dp[lst][x][s]);
                    dp[now][y][(s<<1|1)&limy]=dec(dp[now][y][(s<<1|1)&limy],dp[lst][x][s]);
                }
            for (int y=0;y<=1;y++){
                for (int j=0;j<min(n-r+1,i);j++)
                    for (int t=0;t<4;t++) f[1<<j][t]=bs[t][j];
                f[0][0]=o; f[0][1]=o; f[0][2]=((y||i<r)?all:o); f[0][3]=o;
                for (int s=0;s<=limy;s++){
                    for (int t=0;t<4;t++) f[s][t]=f[s^(s&-s)][t]|f[s&-s][t];
                    v1=(f[s][0]&f[s][1])|(f[s][2]&f[s][3]);
                    v2=(f[s][0]|f[s][1])&(f[s][2]|f[s][3])&(all^v1);
                    dp[now][y][s]=1ll*dp[now][y][s]*pw2[v2.count()]%Mod*pw3[tot-v1.count()-v2.count()]%Mod;
                }
            }

        }

        limy=(1<<(min(n-r+1,r)))-1;
        for (int i=1;i<=n-r;i++){
            for (int y=0;y<=1;y++){
                for (int j=0;j<min(n-r+1,r);j++)
                    for (int t=0;t<4;t++) f[1<<j][t]=bs[t][i+j];
                f[0][0]=o; f[0][1]=o; f[0][2]=(y?all:o); f[0][3]=o;
                for (int s=0;s<=limy;s++){
                    for (int t=0;t<4;t++) f[s][t]=f[s^(s&-s)][t]|f[s&-s][t];
                    v1=(f[s][0]&f[s][1])|(f[s][2]&f[s][3]);
                    v2=(f[s][0]|f[s][1])&(f[s][2]|f[s][3])&(all^v1);
                    dp[now][y][s]=1ll*dp[now][y][s]*pw2[v2.count()]%Mod*pw3[tot-v1.count()-v2.count()]%Mod;
                }
            }
        }
        for (int y=0;y<=1;y++){
            for (int s=0;s<=limy;s++){
                ans=dec(ans,dp[now][y][s]);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

总结

D1T1 这题完成的还算可以，考察了树链剖分以及线段树。

D1T2 是一个 Cauchy-Binet 公式，我没有学过，但是理应做出 $n_1=n_2=\cdots=n_k$，这个没做出的原因是对行列式等线性代数知识不够熟悉。

D1T3 关键的将图缩点然后缩成一棵树等操作都是考场上想到的。不过我并没有想到虚树，与正解失之交臂。

D2T1 思维难度并不高，想到鸽巢原理拆分成 16 个二进制数就完了。然而我被 $k$ 如此小限制了，以为复杂度和 $k$ 呈指数级关系，没有往数学方向想。

D2T2 在考场上想这道题时认为 $E$ 操作要分情况讨论非常麻烦，没有想到变为解矩阵方程后两种情况其实是一样的。

D2T3 没有想到怎么对 dp 的状态进行优化，没有发现机器人爆炸会减少大量状态数。

性质分析能力还是重中之重，其实 D2T2/D2T3 两种情况等价/机器人爆炸都属于题目的特殊性质，更改了这题可能会复杂很多甚至就做不了了。

NOI 级别的题目，一般有一些特殊的数字和奇怪的条件，那么很有可能需要用到。

需要做更多的题，做题更多可以发现更多题目中条件的特殊性，题目也有可能和做过的题类似，如 D1T2 和 CF167E，D2T2 和 loj573。要多做些 CF 题和比赛。

这次发现对线性代数方面不够熟悉，其实同样不够熟悉的还有数论。这个方面还要多学多练。