洛谷3240 [HNOI2015]实验比较

Luogu

BZOJ

分析

语文题

显然相等的点可以缩成一个点。

发现题目中有一句话:

小D都最多只记住了某一张质量不比 $i$ 差的另一张图片 $K_i$

那么缩点后这个图就变成了一棵树,考虑树形$\texttt{DP}$。

设 $f[i][j]$ 表示以 $i$ 为根的子树,用 $j$ 个<连接的方案数。

状态转移方程为:$f[i][c]=f[v1][a]*f[v2][b]*C_{c}^{a}*C_{a}^{b-(c-a)}$。

整个式子是将两个长度分别为 $a$ 和 $b$ 的序列合并。

解释一下后面的两个组合数:先在 $c$ 个位置中选 $a$ 个,则剩下的 $c−a$ 个只能放第二个序列中的数,于是从 $b$ 个数中选出一些数与之前的 $a$ 个数中的一些合并,一共有 $b−(c−a)$ 个这样的需要合并的数。

原图可能有多个连通块,于是建一个虚点 $root$ ,答案为 $\sum\limits_{i=1}^n f[root][i]$ 。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;
const int mod=1e9+7;

struct UFS {
    int f[N];
    inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
    inline void merge(int x,int y) {
        x=find(x),y=find(y);
        if (x!=y) f[y]=x;
    }
} S;

struct Edge { int v,nxt; } e[N<<1];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,m,tot=0;
int C[N][N];
int x[N],y[N],deg[N];
int f[N][N],g[N],sz[N];

inline void dfs(int u,int fa) {
    f[u][0]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u); sz[u]+=sz[v];
        for (re int j=0;j<=sz[u];++j)
            for (re int k=1;k<=sz[v];++k)
                for (re int l=max(j,k);l<=min(n,j+k);++l) {
                    int now=1ll*C[l][j]*C[j][k-(l-j)]%mod*f[u][j]%mod*f[v][k-1]%mod;
                    g[l]=(g[l]+now)%mod;
                }
        for (re int j=0;j<=sz[u];++j) f[u][j]=g[j],g[j]=0;
    }
    ++sz[u];
}

int main() {
    n=read(),m=read();
    /*预处理*/
    for (re int i=1;i<=n;++i) S.f[i]=i;
    for (re int i=0;i<=n;++i) C[i][0]=1;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    /*读入*/
    for (re int i=1;i<=m;++i) {
        int u=read();
        char c; do c=getchar(); while (c!='='&&c!='<');
        int v=read();
        if (c=='=') S.merge(u,v);
        else x[++tot]=u,y[tot]=v;
    }
    for (re int i=1;i<=tot;++i) {
        int u=S.find(x[i]),v=S.find(y[i]);
        addEdge(u,v),++deg[v];
    }
    for (re int i=1;i<=n;++i)
        if (i==S.find(i)&&!deg[i]) addEdge(0,i);
    /*求解*/
    dfs(0,0);
    int ans=0;
    for (re int i=1;i<=n;++i) ans=(ans+f[0][i])%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 09 PM

发表评论