题解 P3240 【[HNOI2015]实验比较】

· · 题解

Editorial

这是一个 O(n^2) 的做法。

题意各位大佬都讲得很清楚了，现在可以转化成一个问题是：给定一个内向森林，祖先结点的颜色必须严格大于后代结点。颜色必须为连续正整数，求方案。

先考虑一棵树的答案：

设 g(n) 表示所有节点有 n 种颜色且满足题意的方案数。

然后我们可以设 f(n)= \sum\limits_{i=0}^{n}\binom{n}{i}g(i)。

21.1.13upd：这样看着可能不太明确其含义，补一下：我们可以设 f[i][j] 表示在 i 子树内的所有节点，颜色小于 j，i 的颜色恰好是 j 的方案数。即，不要求选出的颜色的值域是 1\sim k 连续的。这样就可以树形 dp 了。

不难发现 f(i)\ (1 \le i \le n) 可以通过一个 O(n^2) 的前缀和优化树形 dp 求出。

根据二项式反演 g(n)=\sum\limits_{i=0}^{n} \binom{n}{i}(-1)^{n-i}f(i) 我们就可以得到答案了。

总复杂度仅为 O(n^2)。

Code

而在本题中，是内向树森林，我们建立一个虚结点 n+1，与所有树的根连边。

运行上述算法时，我们对虚结点的转移进行单独判断即可。

int ind[MX];
int head[MX] ,tot;
struct edge{
    int node ,next;
}h[MX << 1];
void addedge(int u ,int v){
    h[++tot] = (edge){v ,head[u]} ,head[u] = tot;
    ind[v]++;
}

LL dp[MX][MX] ,S[MX][MX] ,C[MX][MX];

int fa[MX] ,n ,m;
void init(){
    for(int i = 1 ; i < MX ; ++i) fa[i] = i;
    for(int i = 0 ; i < MX ; ++i) C[i][0] = 1;
    for(int i = 1 ; i < MX ; ++i)
        for(int j = 1 ; j < MX ; ++j)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void link(int u ,int v){u = find(u) ,v = find(v) ,fa[u] = v;}

int cnt ,ins[MX];
void dapai(int x){
    if(ins[x]) puts("0") ,exit(0);
    ins[x] = 1;
    for(int i = 1 ; i <= cnt ; ++i) dp[x][i] = 1;
    for(int i = head[x] ,d ; i ; i = h[i].next){
        dapai(d = h[i].node);
        for(int j = 1 ; j <= cnt ; ++j){
            if(x == n + 1) dp[x][j] = dp[x][j] * S[d][j] % MOD;
            else dp[x][j] = dp[x][j] * S[d][j - 1] % MOD;
        }
    }
    ins[x] = 0;
    for(int i = 1 ; i <= cnt ; ++i) S[x][i] = (S[x][i - 1] + dp[x][i]) % MOD;
}

int ecnt;
struct EDGE{int u ,v;}E[MX];

int main(){
    init();
    n = read() ,m = read();
    for(int i = 1 ,u ,v ; i <= m ; ++i){
        char type[233];
        scanf("%d%s%d" ,&u ,type ,&v);
        if(type[0] == '=') link(u ,v);
        else E[++ecnt] = (EDGE){u ,v};
    }
    for(int i = 1 ; i <= ecnt ; ++i){
        addedge(find(E[i].u) ,find(E[i].v));
    }

    int in = 0;
    for(int i = 1 ; i <= n ; ++i){
        if(find(i) == i) ++cnt;
        if(find(i) == i && !ind[i]){
            addedge(n + 1 ,find(i));
            ++in;
        }
    }
    if(!in){
        puts("0");
        return 0;
    }
    dapai(n + 1);
    LL ans = 0;
    for(int j = 1 ; j <= cnt ; ++j){
        LL tmp = 0;
        for(int i = 0 ; i <= j ; ++i){
            LL add = dp[n + 1][i] * ((j - i) & 1 ? -1 : 1) * C[j][i] % MOD;
            add = (add + MOD) % MOD;
            tmp = (tmp + add) % MOD;
        }
        debug("stained %d color %lld\n" ,j ,tmp);
        ans = (ans + tmp) % MOD;
    }
    printf("%lld\n" ,ans);
    return 0;
}