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);
}

Comments