Skip to content

2025 年 1 月杂题

新年快乐。

本来想写个去年的年终总结，但是细想感觉又无从落笔。

这一年经历了很多，收获了很多。有成长，也有遗憾。

还是没有退役，继续向着省队努力吧。

今年就要成年了，希望我能不辜负过去自己的希望吧。

P3715 [BJOI2017] 魔法咒语

传送门

题意

  • 给定 $n$ 个字符串 $s_i$ 和 $m$ 个字符串 $t_i$。
  • 求由若干个 $s_i$ 顺次相连，长度恰好为 $l$ 且不包含任何恰好等于 $t_i$ 的子串的字符串数量。
  • 有两个子任务：
    • $\sum |s_i|,|t_i|\le 100,l\le 100,1\le n,m\le 50$
    • $\sum |s_i|,|t_i|\le 100,|s_i|\le 2,l\le 10^8,1\le n,m\le 50$

题解

AC 自动机 $+$ DP。

不难想到建出 $t$ 的 AC 自动机，设 $f_{i,j}$ 表示长度为 $i$ 的字符串恰好在 AC 自动机上走到结点 $j$ 的方案数，转移在 AC 自动机上走路即可。

sub1 直接暴力，sub2 用矩阵保存相邻两个 $i$ 的状态，然后预处理转移即可。

sub1 复杂度 $O(\left(\sum |t_i|\right)+l\sum s_i)$，sub2 复杂度 $O(\left(\sum |s_i|\right)\times\left(\sum |t_i|\right)+\log l\times \left(\sum |t_i|\right)^3)$。

/// details | 参考代码 open: False typeL success

#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=105,mod=1e9+7;
int n,m,l;
string s[N],t[N];
struct Trie{
    int tr[N][26],fail[N],vis[N],cntn;
    void Insert(const string &s){
        int len=s.length(),p=0;
        forup(i,0,len-1){
            int c=s[i]-'a';
            if(!tr[p][c]) tr[p][c]=++cntn;
            p=tr[p][c];
        }
        vis[p]=1;
    }
    vector<int> e[N];
    void dfs(int x){
        for(auto i:e[x]){
            vis[i]|=vis[x];
            dfs(i);
        }
    }
    void Build(){
        queue<int> q;
        forup(i,0,25){
            if(tr[0][i]){
                q.push(tr[0][i]);
            }
        }
        while(q.size()){
            int u=q.front();q.pop();
            e[fail[u]].push_back(u);
            forup(i,0,25){
                if(tr[u][i]){
                    fail[tr[u][i]]=tr[fail[u]][i];
                    q.push(tr[u][i]);
                }else{
                    tr[u][i]=tr[fail[u]][i];
                }
            }
        }
        dfs(0);
    }
    int work(int p,const string &s){
        forup(i,0,s.size()-1){
            int c=s[i]-'a';
            p=tr[p][c];
            if(vis[p]) return -1;
        }
        return p;
    }
}mt;
namespace sub1{
    int dp[N][N];
    void solve(){
        dp[0][0]=1;
        forup(i,1,l){
            forup(p,1,n){
                if(i<s[p].size()) continue;
                int j=i-s[p].size();
                forup(st,0,mt.cntn){
                    if(dp[j][st]==0) continue;
                    int tmp=mt.work(st,s[p]);
                    if(~tmp){
                        (dp[i][tmp]+=dp[j][st])%=mod;
                    }
                }
            }
            forup(j,0,mt.cntn){
                msg("%d ",dp[i][j]);
            }
            msg("|\n");
        }
        int ans=0;
        forup(i,0,mt.cntn){
            (ans+=dp[l][i])%=mod;
        }
        printf("%d\n",ans);
    }
}
namespace sub2{
    int t;
    struct Matrix{
        int c[N*2][N*2];
        Matrix(){
            mem(c,0);
        }
        void init(){
            forup(i,0,t-1){
                c[i][i]=1;
            }
        }
        Matrix operator *(const Matrix &r){
            Matrix res;
            forup(i,0,t-1){
                forup(j,0,t-1){
                    forup(k,0,t-1){
                        (res.c[i][j]+=1ll*c[i][k]*r.c[k][j]%mod)%=mod;
                    }
                }
            }
            return res;
        }
    }tr;
    Matrix ksm(Matrix a,int b){
        Matrix c;c.init();
        while(b){
            if(b&1) c=c*a;
            a=a*a;
            b>>=1;
        }
        return c;
    }
    void solve(){
        int nn=mt.cntn+1;
        t=nn*2;
        forup(i,0,nn-1){
            tr.c[i][i+nn]=1;
        }
        forup(i,1,n){
            forup(j,0,nn-1){
                int p=mt.work(j,s[i]);
                if(~p) ++tr.c[j+(s[i].size()-1)*nn][p];
            }
        }
        Matrix res=ksm(tr,l);
        int ans=0;
        forup(i,0,nn-1){
            (ans+=res.c[0][i])%=mod;
        }
        printf("%d\n",ans);
    }
}
signed main(){
    n=read();m=read();l=read();
    forup(i,1,n){
        cin>>s[i];
    }
    forup(i,1,m){
        cin>>t[i];
        mt.Insert(t[i]);
    }
    mt.Build();
    if(l<=100){
        sub1::solve();
    }else{
        sub2::solve();
    }
}

///

P7736 [NOI2021] 路径交点

传送门

题意

  • 有一个 $k$ 层的图，第 $i$ 层有 $n_i$ 个点，每一层只会向下一层连边，$n_1=n_k$。
  • 假设每一层的点按编号依次排列在一条直线上，不难发现假如把边画在纸上它们之间可能有交，具体来说，对于第 $p$ 层向 $p+1$ 层的连边 $u_1\to v_1,u_2\to v_2$，有交当且仅当 $u_1 > u_2$ 且 $v_1 < v_2$
  • 设 $S$ 为一个路径集合大小等于 $n_1$，满足第一层所有点均为某一条路径的起点，最后一层均为终点，并且点不重复。设 $f(S)$ 为路径集合 $S$ 中的交点总数，求 $f(S)$ 为偶数的方案数减去 $f(S)$ 为奇数的方案数。
  • $1\le n_1,k\le 100,n_1\le n_i\le 2n_1,n_k=n_1$，无重边自环。

题解

LGV 引理版题。

不难发现交点数量和 $n_1\to n_k$ 对应关系中的逆序对数量奇偶性相同。

于是变成 LGV 引理模板了，参考这篇博客。

中间的 $e(u,v)$ 可以 bfs 预处理，复杂度大概是 $O(n_1^3k)$。

参考代码 
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=2e4+5,inf=0x3f3f3f3f,mod=998244353;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int k,n[N],pre[N],m[N];
vector<int> e[N];
int f[N],a[105][105];
void bfs(int x){
    mem(f,0);
    queue<int> q;
    q.push(x);
    f[x]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(auto i:e[u]){
            if(!f[i]) q.push(i);
            (f[i]+=f[u])%=mod;
        }
    }
    forup(i,1,n[k]){
        a[x][i]=f[i+pre[k-1]];
    }
}
int det(int n){
    int val=1;
    forup(i,1,n){
        int j=i;
        while(j<=n&&!a[j][i]) ++j;
        if(j>n) return 0;
        if(j!=i){
            val=mod-val;
            forup(k,1,n) swap(a[i][k],a[j][k]);
        }
        int inv=ksm(a[i][i],mod-2);
        val=1ll*val*a[i][i]%mod;
        forup(k,i,n) a[i][k]=1ll*a[i][k]*inv%mod;
        forup(j,i+1,n){
            fordown(k,n,i){
                a[j][k]=(a[j][k]+mod-1ll*a[j][i]*a[i][k]%mod)%mod;
            }
        }
    }
    return val;
}
void solve(){
    k=read();
    forup(i,1,k){
        n[i]=read();
        pre[i]=pre[i-1]+n[i];
    }
    forup(i,1,k-1){
        m[i]=read();
    }
    forup(i,1,k-1){
        forup(j,1,m[i]){
            int u=read()+pre[i-1],v=read()+pre[i];
            e[u].push_back(v);
        }
    }
    forup(i,1,n[1]){
        bfs(i);
    }
    printf("%d\n",det(n[1]));
    forup(i,1,pre[k]){
        e[i].clear();
    }
}
signed main(){
    int t=read();
    while(t--){
        solve();
    }
}

黑暗爆炸-3238 差异

传送门

题意

  • 给定一个字符串 $S$，设 $T_i$ 表示从点 $i$ 开始的后缀，求：

    $$ \sum_{1\le i < j\le n}|T_i|+|T_j|-2\mathrm{lcp}(T_i,T_j) $$

  • $1\le |S|\le 5\times 10^5$，字符集为小写字母集。

题解

不难发现 $\sum_{1\le i < j\le n}|T_i|+|T_j|$ 是可以直接算的，于是只需要算 $\sum_{1\le i < j\le n}\mathrm{lcp}(T_i,T_j)$。

首先我们不喜欢后缀的最长公共前缀，于是将整个字符串 reverse 一下就变成求前缀的最长公共后缀了。

于是建出 SAM，那么 $\mathrm{lcp}$ 就转化成了 $\mathrm{lnk}$ 树上的 $\mathrm{lca}$。于是我们将每个点挂在自己的所有祖先，然后再从上往下传即可，注意不要算重。复杂度 $O(n|\Sigma|)$。

参考代码 
#include<bits/stdc++.h>
#define forup(i,s,e) for(i64 i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(i64 i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=1e6+5,inf=0x3f3f3f3f;
i64 n,pos[N];
char str[N];
i64 tr[N][26],lnk[N],len[N],cnt[N],res[N];
i64 lst=0,cntn=0;;
i64 insert(i64 c){
    i64 x=++cntn,p=lst;lst=x;
    cnt[x]=1;
    len[x]=len[p]+1;
    while(~p&&!tr[p][c]){
        tr[p][c]=x;
        p=lnk[p];
    }
    if(p==-1){
        lnk[x]=0;
        return x;
    }
    i64 q=tr[p][c];
    if(len[q]==len[p]+1){
        lnk[x]=q;
    }else{
        i64 _q=++cntn;
        len[_q]=len[p]+1;
        lnk[_q]=lnk[q];lnk[q]=lnk[x]=_q;
        forup(i,0,25){
            tr[_q][i]=tr[q][i];
        }
        while(~p&&tr[p][c]==q){
            tr[p][c]=_q;
            p=lnk[p];
        }
    }
    return x;
}
vector<i64> e[N];
void dfs1(i64 x){
    for(auto i:e[x]){
        dfs1(i);
        cnt[x]+=cnt[i];
    }
    res[x]=-2*cnt[x]*len[x];
}
void dfs2(i64 x){
    for(auto i:e[x]){
        res[i]+=res[x]+2*cnt[i]*len[x];
        dfs2(i);
    }
}
signed main(){
    scanf(" %s",str+1);
    n=strlen(str+1);
    reverse(str+1,str+n+1);
    lnk[0]=-1;
    forup(i,1,n){
        pos[i]=insert(str[i]-'a');
    }
    forup(i,1,cntn){
        e[lnk[i]].push_back(i);
    }
    dfs1(0);
    dfs2(0);
    i64 ans=0;
    forup(i,1,n){
        ans+=res[pos[i]]+i*n+n*(n+1)/2;
    }
    printf("%lld\n",ans/2);
}

P2490 [SDOI2011] 黑白棋

传送门

题意

  • 有一张 $1\times n$ 的棋盘，上面有 $k$ 个棋子（$k$ 是偶数），这些棋子是白色/黑色交替排列的，并且第一个是白色（那么显然最后一个是黑色）。
  • 有两个人在这张棋盘上进行游戏，其中先手操作白棋，后手操作黑棋。每一步可以选择不超过 $d$ 个自己操作的棋子移动一步。白棋只能向右移动，黑棋只能向左移动，不能操作者负。
  • 问有多少种摆放方式是先手必胜的。
  • $1\le d\le k\le n\le 10^4$ 其中 $2\le k\le 100$。

题解

不难发现这就是一个经典的 k-Nim 问题，结论是将每一堆石子的数量按二进制表示出来后，进行模 $k+1$ 的不进位加法，若为 $0$ 则后手必胜，否则先手必胜。

这道题的限制就是总石子个数不能超过 $n-k$。

这种因为每一位是独立的，所以考虑按位 DP。具体来说，设 $f_{i,j}$ 表示考虑低 $i$ 位，用了 $j$ 个石子的方案数，转移就枚举这一位应该有 $d+1$ 的倍数个 $1$，用组合数分发到 $\frac{k}{2}$ 堆石子其中若干个就行了。

然后统计答案还需要计算没用到的格子的位置，也是组合数即可。

复杂度 $O(n\log n+n^2)$，这个 $n^2$ 不会乘 $\log$ 是因为枚举 $d+1$ 的倍数这一部分不会超过 $\frac{n}{2^i}$，常数很小还是很能通过的。

参考代码 
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=20005,M=55,mod=1e9+7;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int n,k,d;
int dp[25][N];
int fact[N],finv[N];
int binom(int n,int m){
    if(n<m) return 0;
    return 1ll*fact[n]*finv[m]%mod*finv[n-m]%mod;
}
signed main(){
    n=read();k=read();d=read()+1;
    fact[0]=1;
    forup(i,1,n) fact[i]=1ll*fact[i-1]*i%mod;
    finv[n]=ksm(fact[n],mod-2);
    fordown(i,n-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
    n-=k;
    k>>=1;
    dp[0][0]=1;
    int mx=0;
    for(int i=0,p=1;p<=n;++i,p<<=1){
        mx=i+1;
        forup(j,0,n){
            if(!dp[i][j]) continue;
            forup(t,0,min(k,(n-j)/(d*p))){
                (dp[i+1][j+d*p*t]+=1ll*dp[i][j]*binom(k,d*t)%mod)%=mod;
            }
        }
    }
    int ans=0;
    forup(i,0,n){
        (ans+=1ll*dp[mx][i]*binom(n-i+k,k)%mod)%=mod;
    }
    ans=(binom(n+k*2,k*2)+mod-ans)%mod;
    printf("%d\n",ans);
}

P5417 [CTSC2016] 萨菲克斯·阿瑞

传送门

题意

  • 问满足以下所有条件的字符串 $s$ 可能有多少种不同的后缀数组：
    • 长度为 $n$，字符集大小为 $m$。
    • 第 $i$ 种（从小往大排列）字符出现次数不超过 $c_i$。
  • $1\le n,m\le 200,0\le c_i\le n,\sum c_i\ge n$

题解

很厉害的一道题。

首先后缀数组显然不能直接做，考虑经典转化：将后缀数组转化为字符的大小关系。

具体来说，设后缀数组为 $sa$（$sa_i$ 表示字典序第 $i$ 小的后缀），逆排列为 $rk$，那么 $s_{sa_i}\le s_{sa_{i+1}}$，并且若 $rk_{sa_i+1} > rk_{sa_{i+1}+1}$ 则这个 $\le$ 必须替换为 $ < $。即一个后缀数组能映射到一个由 $ < $ 或 $\le$ 连接的大小关系序列。

但是这个关系序列显然无法映射到后缀数组。一个观察是若钦定不同字符的数量恰好等于 $ < $ 的个数加一，那么这个关系序列就能映射到唯一的字符串，进而映射到唯一的后缀数组。而不难发现我们只要确定由 $<$ 连接的每一段长度（不妨设为 $a_i$）后，不同的后缀数组数量就是 $\frac{(\sum a_i)!}{\prod a_i!}$，但是显然会算重，这启发我们进行容斥。

具体来说，我们对关系序列进行计数，每两个 $<$ 之间的 $s_{sa_i}$ 尽量用同种字符填满，然后钦定 $k$ 个 $<$ 替换为 $\le$，并且容斥系数为 $(-1)^k$。

不难想到设 $f_{i,j,k}$ 表示考虑前 $i$ 种字符，已经填了前 $j$ 位，并且上一段的末尾为 $k$ 的方案数，因为方案数带 $n!$ 的系数，根据套路把它拆出来，那么转移有三种：

  1. $f_{i,j,k}\gets f_{i-1,j-c_i,k}$：将 $c_i$ 个字符全部填进这一段，并且不新建下一段。
  2. $f_{i,j,k}\gets -\sum_{t=1}^{c_i}f_{i-1,j-t,k}$：填 $t$ 个字符进这一段，但是钦定这个 $<$ 变成 $\le$，即不新建一段，那么有 $-1$ 的系数。
  3. $f_{i,j,j}\gets \frac{1}{(j-k)!}\sum_{t=1}^{c_i}f_{i-1,j-t,k}$：填 $t$ 个字符进这一段，并且新建一段。

为什么后面两种转移从 $1$ 开始枚举 $t$ 呢？虽然实际选的字符并不一定是一个前缀，但是由于我们只关注每一段的长度所以并不会算漏情况。反而如果从 $0$ 开始枚举就可能需要加一堆特判。

复杂度 $O(n^2m)$，需要前缀和优化。

参考代码 
#include<bits/stdc++.h>
#define forup(i,s,e) for(int i=(s),E123123123=(e);i<=E123123123;++i)
#define fordown(i,s,e) for(int i=(s),E123123123=(e);i>=E123123123;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using namespace std;
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=505,mod=1e9+7;
int ksm(int a,int b){
    int c=1;
    while(b){
        if(b&1) c=1ll*a*c%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return c;
}
int n,m,c[N];
int f[2][N][N],sum[N][N];
int fact[N],finv[N];
signed main(){
    n=read();m=read();
    forup(i,1,m){
        c[i]=read();
    }
    int cntn=0;
    forup(i,1,m) if(c[i]) c[++cntn]=c[i];
    m=cntn;
    fact[0]=1;
    forup(i,1,n) fact[i]=1ll*fact[i-1]*i%mod;
    finv[n]=ksm(fact[n],mod-2);
    fordown(i,n-1,0) finv[i]=1ll*finv[i+1]*(i+1)%mod;
    f[0][0][0]=1;
    forup(i,0,n){
        sum[i][0]=1;
    }
    int ans=0;
    forup(i,1,m){
        int p=i&1,q=p^1;
        mem(f[p],0);
        forup(j,0,n){
            forup(k,0,j){
                if(j>=c[i]+k) (f[p][j][k]+=f[q][j-c[i]][k])%=mod;
                int vv;
                if(j>c[i]){
                    vv=(sum[j-1][k]+mod-sum[j-c[i]-1][k])%mod;
                }else{
                    vv=sum[j-1][k];
                }
                f[p][j][k]=(f[p][j][k]+mod-vv)%mod;
                (f[p][j][j]+=1ll*vv*finv[j-k]%mod)%=mod;
            }
        }
        (ans+=f[p][n][n])%=mod;
        mem(sum,0);
        forup(j,0,n){
            forup(k,0,j){
                sum[j][k]=f[p][j][k];
                if(j) (sum[j][k]+=sum[j-1][k])%=mod;
            }
        }
    }
    printf("%lld\n",1ll*ans*fact[n]%mod);
}

CF1746F Kazaee

传送门

题意

  • 有一个长度为 $n$ 的序列 $a$，维护两个操作共 $m$ 次：
    • 单点修改。
    • 区间查询是否每个数出现次数都是 $k$ 的倍数，每次询问的 $k$ 不一定相同。
  • $1\le n,q\le 3\times 10^5,1\le a_i\le 10^9$。

题解

典题，但是 zky 提供了一个拓展性更强的做法。

一个想法是给每个值映射一个随机权值，查询区间和是否为 $k$ 的倍数。多映射几组错误概率就很低了。

但是我们发现随机权值的范围缩小到 $0$ 或者 $1$ 仍然可以，此时出错当且仅当若干个不为 $k$ 倍数的数区间总个数是 $k$ 的倍数，然后全选或者全不选，发现只要存在这样的错误方案就必定会存在若干个正确方案（修改出错部分的一个子集），那么错误概率不超过 $\frac{1}{2}$（恰好两个数加起来出错，错误比例为 $\frac{2}{4}$），于是随机 $40$ 组映射差不多就能对了，错误概率 $2^{-40}$。

参考代码 
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=3e5+5,inf=0x3f3f3f3f;
int n,q,a[N];
struct BIT{
    int c[N];
    void upd(int x,int k){for(;x<=n;x+=x&-x)c[x]+=k;}
    int sum(int x){int res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}mt[41];
map<int,vector<int> > mp;
mt19937 mr(20071221);
int Rd(int l,int r){return (unsigned int)mr()%(r-l+1)+l;}
signed main(){
    n=read();q=read();
    forup(i,1,n){
        a[i]=read();
        if(!mp.count(a[i])){
            vector<int> vec;
            forup(i,0,40){
                vec.push_back(Rd(0,1));
            }
            mp[a[i]]=vec;
        }
        vector<int> p=mp[a[i]];
        forup(j,0,40){
            mt[j].upd(i,p[j]);
        }
    }
    forup(i,1,q){
        int op=read();
        if(op==1){
            int x=read(),v=read();
            vector<int> p=mp[a[x]];
            forup(j,0,40){
                mt[j].upd(x,-p[j]);
            }
            a[x]=v;
            if(!mp.count(a[x])){
                vector<int> vec;
                forup(i,0,40){
                    vec.push_back(Rd(0,1));
                }
                mp[a[x]]=vec;
            }
            p=mp[a[x]];
            forup(j,0,40){
                mt[j].upd(x,p[j]);
            }
        }else{
            int l=read(),r=read(),k=read();
            bool flag=true;
            forup(j,0,40){
                if((mt[j].sum(r)-mt[j].sum(l-1))%k!=0){
                    flag=false;
                    break;
                }
            }
            puts(flag?"YES":"NO");
        }
    }
}

P1224 [NOI2013] 向量内积

传送门

题意

  • 给定 $n$ 个 $d$ 维向量，求是否存在两个向量 $v_i,v_j(i\ne j)$ 点积为 $k$ 的倍数，输出这两个向量的下标。
  • 两个 subtask：
    • $1\le n\le 10^4,1\le d\le 100,2\le k\le 3$。
    • $1\le n\le 10^5,1\le d\le 30,2\le k\le 3$。

题解

zky 的神秘随机化做法。

首先不妨直接在模意义下进行计算。

考虑 $k=2$，那么点积只有可能是 $0$ 或者 $1$。显然不存在这样的一对 $(i,j)$ 当且仅当对于任意 $i,j$ 有 $v_i\cdot v_j = 1$。注意到点积对于向量加法有分配律，那么我们随机取出一个向量的集合 $S$，将其线性加起来得到 $V$。然后用所有不在 $S$ 中的向量和 $V$ 相乘，显然某 $i\in S$ 和 $j\notin S$ 满足 $v_i\cdot v_j=0$ 仅当 $j$ 和 $V$ 的点积奇偶性和 $|S|$ 的奇偶性不同。

考虑这个判定条件的正确率，首先不难发现判定错误当且仅当有偶数对 $(i,j)$ 被分开了，发现无论有几对这样的数对，偶数对的情况都不会多于奇数对的情况，即正确率不低于 $\frac{1}{2}$。那么进行 $T$ 次错误概率就是 $2^{-T}$，复杂度 $O(\frac{Tnd}{\omega})$。

然后考虑 $k=3$，发现在模 $3$ 意义下非 $0$ 数的平方都是 $1$，那么取点积的平方，则 $\left(\sum_{p=1}^dv_{i,p}v_{j,p}\right)=\sum_{1\le x,y\le d}v_{i,x}v_{i,y}v_{j,x}v_{j,y}$，于是转化为长度为 $d^2$ 的向量点积就又可以用奇偶性判断了。这个复杂度是 $O(\frac{Tnd^2}{\omega})$，错误概率还是 $2^{-T}$。

因为要可变长度 bitset，代码里用了模板技巧。

参考代码 
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(int i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(int i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using uchar=unsigned char;
using pii=pair<int,int>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline int read(){
    int x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const int N=1e5+5,M=105,inf=0x3f3f3f3f;
const int T=50;
int n,m,p;
template<int D>
struct Vec{
    bitset<D> v[2];
    int operator *(const Vec<D> &r){
        if(p==2){
            return (v[0]&r.v[0]).count()&1;
        }else{
            return ((v[0]&r.v[0]).count()+(v[1]&r.v[1]).count()
                    +2*(v[0]&r.v[1]).count()+2*(v[1]&r.v[0]).count())%3;
        }
    }
    Vec operator +(const Vec<D> &r){
        Vec res;
        if(p==2){
            res.v[0]=v[0]^r.v[0];
        }else{
            bitset<D> v0,rv0;v0.set();rv0.set();
            v0=v0^v[0]^v[1];
            rv0=rv0^r.v[0]^r.v[1];
            res.v[0]=((v[1]&r.v[1])|(v0&r.v[0])|(v[0]&rv0));
            res.v[1]=((v[0]&r.v[0])|(v0&r.v[1])|(v[1]&rv0));
        }
        return res;
    }
};
vector<vector<uchar>> s;
mt19937 mr(20071221);
int Rd(int l,int r){return (unsigned int)mr()%(r-l+1)+l;}
bool vis[N];
template<int M=1>
void work(int n,int m){
    if(M<=m) work<min(M*2,10001)>(n,m);
    vector<Vec<M>> a(n+1);
    forup(i,1,n){
        forup(j,1,m){
            if(s[i][j]!=0){
                a[i].v[s[i][j]-1].set(j,1);
            }
        }
    }
    forup(i,1,T){
        Vec<M> vec;
        int cnt=0;
        forup(j,1,n){
            vis[j]=Rd(0,1);
            if(vis[j]){
                cnt=(cnt+1)%p;
                vec=vec+a[j];
            }
        }
        forup(i,1,n){
            forup(j,i+1,n){
                msg("%d ",a[i]*a[j]);
            }
            msg("|\n");
        }
        forup(i,1,n){
            msg("%d ",vis[i]);
        }msg("|\n");
        forup(j,1,n){
            if(!vis[j]){
                int sum=0;
                forup(k,1,n){
                    if(vis[k]){
                        (sum+=a[j]*a[k])%=p;
                    }
                }
                if(a[j]*vec!=cnt){
                    msg("(%d)\n",j);
                    forup(k,1,n){
                        if(!vis[k]) continue;
                        if(a[j]*a[k]==0){
                            if(j>k) swap(j,k);
                            printf("%d %d\n",j,k);
                            exit(0);
                        }
                    }
                    assert(0); 
                }
            }
        }
    }
};
void solve3(){
    vector<vector<uchar>> b;
    b.resize(n+1,vector<uchar>(m*m+1,0));
    forup(i,1,n){
        forup(j,1,m){
            forup(k,1,m){
                b[i][(j-1)*m+k]=s[i][j]*s[i][k]%p;
            }
        }
    }
    s=b;
    work(n,m*m);
};
signed main(){
    n=read();m=read();p=read();
    s.resize(n+1,vector<uchar>(m+1));
    forup(i,1,n){
        forup(j,1,m){
            s[i][j]=read()%p;
        }
    }
    if(p==2){
        work(n,m);
    }else{
        solve3();
    }
    puts("-1 -1");
}

zky 原创题

暂时无法提交。

题意

  • 给定一个长度为 $n$ 的整数序列 $a$，支持以下两种操作共 $m$ 次：
    • 区间翻转。
    • 查询从区间中选出一个子集能获得的最大异或和。
  • $1\le n,q\le 5\times 10^4,0\le a < 2^{60}$

题解

神秘啊神秘。

考虑这样做：随机一个 $0/1$ 序列 $b$，再维护一个 $c_i=a_ib_i$，然后我们将区间 $c_i$ 的异或和拎出来。

不难发现当我们随机 $b_i$ 的组数足够多时，把每个 $c_i$ 的区间异或和当成一个向量得到的张成空间（下称“新空间”）显然是区间张成空间（下称“原空间”）的子空间，并且很有可能就是原空间的张成空间。

那么具体多有可能呢。首先不妨把原空间看作一个 $[0,2^l)$ 的集合，那么若新空间是原空间的真子空间，则新空间的正交补空间维数必定不小于 $1$，即存在一个向量 $v$ 和新空间内所有向量全部垂直。显然对于一个向量，在全集中恰有 $\frac{1}{2}$ 的向量和它垂直，那么存在一个向量和这些东西全部垂直的概率就是 $2^{-T}$（其中 $T$ 是取的组数）。

那么平衡树维护 $T$ 个区间异或和即可，复杂度 $O(nT+qT(\log n+\log V))$。据 zky 说 $T$ 取 $100$ 是不难过的。

代码懒得写了。

一般图最大匹配

题意

  • 给定一张无向图，求最大匹配（找到最大的边集使得任意一个点至多出现一次）。
  • $1\le n\le 500$

题解

这道题正解 $n\le 1000$ 是带花树算法（我不会），但是 zky 讲了一个很精妙的线性代数做法。

考虑设计矩阵 $G$：

对于 $i\le j$，若 $i,j$ 之间有边，则 $G_{i,j}=x_{i,j},G_{j,i}=-x_{i,j}$（这里的 $x_{i,j}$ 是一个代数对象，对于不同的 $(i,j)$ 两两不同）。

结论：$\det G\ne 0$ 等价于原图存在完美匹配。

为什么呢？考虑行列式的定义，$\sum_p\pi(p)G_{i,p_i}$（这里 $\pi$ 表示若 $p$ 逆序对数量为奇数则为 $-1$，否则为 $+1$），不难发现 $i\to p_i$ 构成了一个置换环，注意到若存在环为奇数则必定能反过来走一遍抵消，所以计算到 $\det$ 里面的都是环长全为偶数的方案了。显然环长全为偶数有平凡解。

那么怎么求最大匹配呢？我们猜测答案是 $\frac{\mathrm{rank}\;G}{2}$。

首先不难发现取出最大匹配对应的行，这些行线性无关（否则行列式就是 $0$ 了），则矩阵的值大于等于二倍最大匹配。

并且我们显然可以取出一个 $\mathrm{rank}\;G\times \mathrm{rank}\;G$ 的矩阵行列式不等于 $0$，于是二倍最大匹配大于等于矩阵的秩。

显然我们不能直接算多项式，于是我们随机 $x$ 求出 $\mathrm{rank}$ 即可，复杂度 $O(n^3)$。

代码就不贴了。

LOJ#178 多项式求根

传送门

题意

  • 给定一个多项式方程 $f(x)=\sum_{i=0}^na_ix^i=0$，求在模质数 $p$ 意义下的所有根。
  • $1\le n\le 100,3\le p\le 10^9$

题解

很妙的一个东西。

首先要求根的话我们肯定希望写成 $\prod(x-b_i)$ 的形式。

不难发现 $\prod_{i=0}^{p-1}(x-i)=x^p-x$，因为带任何值进去都是 $0$。那么我们求出 $\gcd(f,x^p-x)$ 就能得到一个只有根的东西了。并且我们又找到了一个分理出一部分根的方法。

具体来说，我们构造一个多项式 $g$ 包含 $[0,p-1]$ 中的一部分根，取 $h=\gcd(f,g)$ 即可把 $f$ 的根分为 $h$ 中的和 $\frac{f}{h}$ 中的两部分了，一直递归到只有一个根就对了。

那么如何构造多项式 $g$ 呢？注意到在模 $p$ 意义下，任何数的 $\frac{p-1}{2}$ 不是 $1$ 就是 $-1$（取决于这个数是不是二次剩余），而根据经典结论，二次剩余大约占 $\frac{1}{2}$，那么我们取 $g=h^{\frac{p-1}{2}}-1$ 即可（此处 $h$ 是一个随机的多项式）。

但是我不会写多项式全家桶，所以留坑待补。

P5811 [IOI2019] 景点划分

传送门

题意

  • 给定一张 $n$ 个点 $m$ 条边的无向图，将其划分为大小分别为 $a,b,c(a+b+c=n)$ 的三个点集，使得其中至少两个点集是连通的。构造方案或者判断无解。
  • $3\le n\le 10^5,2\le m\le 2\times 10^5$，无重边自环，图连通。

题解

貌似有很巧妙的做法，但是可以直接利用双极定向知识比较板地做。

首先不妨设 $a\le b\le c$，显然集合 $A,B$ 更容易是连通的，下文称 $A$ 中为红点，$B$ 中为蓝点。

注意到任意一个点双都能双极定向，那么我们先建立原图的广义圆方树（下文简称圆方树），考虑寻找一个点双同时包含红蓝两色的点。不难想到点双有且仅有一个，首先必定存在至少一个解包含一个这样的点双，并且如果有两个同时包含红蓝两色的点双，那么中间那个割点不管取什么颜色都不对了。

那么我们枚举每一个方点，找到它最大的子树大小（只算子树内圆点）记为 $sz$。

  1. 若 $sz > n-a$，那么显然这个方点不可能有解。
  2. 否则，若 $sz\ge b$，那么必定能在这个子树内找到一个大小 $\ge b$ 的连通块同时，在子树外找到大小 $\ge a$ 的，直接构造即可。
  3. 否则，我们对这个点双进行双极定向（随便找 $s\ne t$ 即可），由于每个子树大小都 $< b$，那么前缀和不可能从小于 $a$ 突变到大于等于 $a+b$。由于 $a\le b\le c$，那么在第一个前缀大于等于 $a$ 的位置，后面的后缀必定大于等于 $c$ 于是也大于等于 $b$，那么就能构造出来的。

显然代码不好写，现在正好已经很晚了于是留坑待补。

CF1073G Yet Another LCP Problem

传送门

题意

  • 给定一个长度为 $n$ 的字符串，有 $m$ 次询问。
  • 每次询问给定两个下标的集合 $A,B$，求出 $\sum_{i\in A}\sum_{j\in B}\mathrm{lcp}(i,j)$。
  • 此处 $\mathrm{lcp}(i,j)$ 表示后缀 $[i,n]$ 和后缀 $[j,n]$ 的最长公共前缀。
  • $1\le n\le 2\times 10^5$

题解

一个完全不动脑子的 SAM 做法。

首先把字符串 std::reverse 一下，不难想到两两在 parent tree 上求 $\mathrm{lca}$。

然后发现可以将每个点点权置为为 $\mathrm{len_{\mathit{i}}}-\mathrm{len_{link_{\mathit{i}}}}$（除去根节点权值为 $0$），这样 $\mathrm{lca}$ 就转化为了两条延伸到 $1$ 的垂直树链交的点权和。

然后直接树剖维护即可，注意链底的等价类不一定被全部包含，可以单独维护。总复杂度 $O(n\log^2 n)$。

参考代码 
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s),E123123=(e);i<=E123123;i++)
#define fordown(i,s,e) for(i64 i=(s),E123123=(e);i>=E123123;i--)
using namespace std;
#ifdef DEBUG
#define msg(args...) fprintf(stderr,args)
#else
#define msg(...) void()
#endif
using i64=long long;
using pii=pair<i64,i64>;
#define fi first
#define se second
#define mkp make_pair
#define gc getchar()
inline i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc)) if(c=='-') f=-1;
    while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=gc;}
    return x*f;
}
#undef gc
const i64 N=4e5+5,inf=0x3f3f3f3f;
i64 n,m;
char str[N];
i64 pos[N];
i64 tr[N][26],lnk[N],len[N];
i64 cntn,lst;
vector<i64> e[N];
void Insert(i64 c){
    i64 x=++cntn,p=lst;lst=x;
    len[x]=len[p]+1;
    while((~p)&&!tr[p][c]){
        tr[p][c]=x;
        p=lnk[p];
    }
    if(p==-1){
        lnk[x]=0;
        return;
    }
    i64 q=tr[p][c];
    if(len[q]==len[p]+1){
        lnk[x]=q;
    }else{
        i64 _q=++cntn;
        len[_q]=len[p]+1;
        lnk[_q]=lnk[q];
        lnk[x]=lnk[q]=_q;
        forup(i,0,25) tr[_q][i]=tr[q][i];
        while((~p)&&tr[p][c]==q){
            tr[p][c]=_q;p=lnk[p];
        }
    }
    return;
}
i64 dfn[N],Tm,sz[N],mp[N];
i64 son[N];
void dfs(i64 x){
    sz[x]=1;son[x]=0;
    for(auto i:e[x]){
        dfs(i);
        sz[x]+=sz[i];
        if(!son[x]||sz[i]>sz[son[x]]) son[x]=i;
    }
}
i64 hig[N];
void dfs2(i64 x,i64 hh){
    dfn[x]=++Tm;
    mp[dfn[x]]=x;
    hig[x]=hh;
    if(son[x]){
        dfs2(son[x],hh);
    }
    for(auto i:e[x]){
        if(i==son[x]) continue;
        dfs2(i,i);
    }
}
struct SegTree{
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 val[N<<2],sum[N<<2],mark[N<<2];
    void Build(i64 l=1,i64 r=Tm,i64 id=1){
        mark[id]=sum[id]=0;
        if(l==r){
            if(mp[l]==0){
                val[id]=len[mp[l]];
            }else{
                val[id]=len[mp[l]]-len[lnk[mp[l]]];
            }
            // msg("%lld(%lld %lld)%lld|\n",id,l,r,val[id]);
            return;
        }
        Build(lson);Build(rson);
        val[id]=val[id<<1]+val[id<<1|1];
        msg("%lld(%lld %lld)%lld|\n",id,l,r,val[id]);
    }
    void PushUp(i64 id){
        sum[id]=sum[id<<1]+sum[id<<1|1];
    }
    void modi(i64 id,i64 V){
        sum[id]+=V*val[id];
        mark[id]+=V;
    }
    void PushDown(i64 id){
        modi(id<<1,mark[id]);
        modi(id<<1|1,mark[id]);
        mark[id]=0;
    }
    void Update(i64 L,i64 R,i64 X,i64 l=1,i64 r=Tm,i64 id=1){
        if(L<=l&&r<=R){
            modi(id,X);
            // msg("%lld %lld|%lld %lld|\n",l,r,val[id],sum[id]);
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id);
    }
    i64 Query(i64 L,i64 R,i64 l=1,i64 r=Tm,i64 id=1){
        if(L<=l&&r<=R){
            return sum[id];
        }
        i64 res=0;
        if(mark[id]) PushDown(id);
        if(L<=mid) res+=Query(L,R,lson);
        if(mid< R) res+=Query(L,R,rson);
        return res;
    }
}mt;
struct BIT{
    i64 c[N];
    void upd(i64 x,i64 k){for(;x<=Tm;x+=x&-x)c[x]+=k;}
    i64 sum(i64 x){i64 res=0;for(;x>0;x-=x&-x)res+=c[x];return res;}
}t2;
void Update(i64 x,i64 v){
    while(~x){
        mt.Update(dfn[hig[x]],dfn[x],v);
        x=lnk[hig[x]];
    }
}
i64 Query(i64 x){
    i64 res=0;
    while(~x){
        res+=mt.Query(dfn[hig[x]],dfn[x]);
        x=lnk[hig[x]];
    }
    return res;
}
signed main(){
    n=read();m=read();
    scanf(" %s",str+1);
    reverse(str+1,str+n+1);
    lnk[0]=-1;
    lst=cntn=0;
    forup(i,1,n){
        Insert(str[i]-'a');
    }
    i64 p=0;
    forup(i,1,n){
        p=tr[p][str[i]-'a'];
        pos[i]=p;
    }
    // forup(i,0,cntn){
    //     forup(j,0,2){
    //         msg("%lld ",tr[i][j]);
    //     }
    //     msg("|%lld %lld|\n",len[i],lnk[i]);
    // }
    forup(i,1,cntn){
        e[lnk[i]].push_back(i);
    }
    dfs(0);
    dfs2(0,0);
    forup(i,1,cntn){
        msg("%lld ",dfn[i]);
    }
    msg("|\n");
    mt.Build();
    forup(i,1,m){
        i64 cl=read(),cr=read(),res=0;
        vector<i64> vec;
        forup(i,1,cl){
            i64 p=read();
            p=n-p+1;
            vec.push_back(p);
            Update(lnk[pos[p]],1);
            t2.upd(dfn[pos[p]],len[pos[p]]-len[lnk[pos[p]]]);
            t2.upd(dfn[pos[p]]+sz[pos[p]],-(len[pos[p]]-len[lnk[pos[p]]]));
        }
        forup(i,1,cr){
            i64 p=read();
            p=n-p+1;
            res+=Query(pos[p])+t2.sum(dfn[pos[p]]);
        }
        printf("%lld\n",res);
        for(auto p:vec){
            Update(lnk[pos[p]],-1);
            t2.upd(dfn[pos[p]],-(len[pos[p]]-len[lnk[pos[p]]]));
            t2.upd(dfn[pos[p]]+sz[pos[p]],len[pos[p]]-len[lnk[pos[p]]]);
        }
    }
}

Comments