题解：CF1574F Occurrences

Tokisaki__kurumi · 2025-11-13 16:51:06 · 题解

CF1574F

思路：我们发现对于一个 A_i 来说我们如果出现了其中的一个数字，我们就要将他全部选上，正确性显然。但有一些情况是不能选他们的，当 A_i 中出现重复数字时，我们一定不会选，当同一个数字有两个不同的后继时我们不能选，因此如果把所有 A_i 抽象成一张图的话，有环不能选，一个节点有多个儿子不能选，一个节点有多个父亲不能选。这些操作可以用链表加并查集实现。最后合法可选的是几条互不干扰的链，相当于转化成一个背包问题，每个物品的重量是链的长度，求可以组成重量为 m 的方案数。直接做是 O(nm) 的，虽然物品很多，但物品的重量种类不多只有 O(\sqrt m) 种，于是把重量相同的物品合起来，跑一遍完全背包即可。时间复杂度 \mathcal{O}(n\sqrt m)。

code

int n,m,k;
int pre[N],to[N];
int f[N],g[N],w[N];
int fa[N],sz[N];
int tag[N];
int a[N];
inline int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}    
inline void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y){tag[x]=1;return;} 
    fa[x]=y;
    tag[y]|=tag[x];
    sz[y]+=sz[x];
}
inline void solve(){
    read(n,m,k);
    for(int i=1;i<=k;++i) fa[i]=i,sz[i]=1;
    for(int i=1;i<=n;++i){
        int c;
        read(c);
        for(int j=1;j<=c;++j){
            read(a[j]);
            if(j==1) continue;
            if((pre[a[j]]&&pre[a[j]]!=a[j-1])||(to[a[j-1]]&&to[a[j-1]]!=a[j])) merge(a[j-1],a[j]),tag[find(a[j])]|=1;
            else if(!to[a[j-1]]){
                to[a[j-1]]=a[j];
                pre[a[j]]=a[j-1];
                merge(a[j-1],a[j]);
            }
        }
    }
    for(int i=1;i<=k;++i){
        if(find(i)!=i||tag[i]) continue;
        g[sz[i]]++;
    }
    int cnt=0;
    for(int i=1;i<=m;++i){
        if(g[i]) w[++cnt]=i;
    }
    f[0]=1;
    for(int i=0;i<=m;++i){
        for(int j=1;j<=cnt&&w[j]+i<=m;++j){
            f[i+w[j]]=(f[i+w[j]]+1ll*f[i]*g[w[j]]%mod)%mod;
        }
    }
    write(f[m]);
}