题解：SP8064 AMR10J - Mixing Chemicals

· · 题解

Mixing Chemicals 题解

题目链接

思路

\color {red} 基环树好题！！！🎉

What is Basal ring tree?

题目大意

给你一棵基环树，让你进行 k 分图染色。

求染色方案数。

思路

既然是一颗基环树，那么我们肯定要先找环。

那么题目就分成了两部分，一部分是不在环上的点，另一种是在环上的点。

即环形 DP 和树形 DP 。

树形DP

很明显，每一个点都会连向一个点，那么每个点的染色方案数都为 (k-1) 种，则答案为

---- ### 环形DP **分两种情况来讨论。** 我们设一个函数 $f(x)$ 。 $f(x)$ 代表环上有 $x$ 个点已染色的方案数。 则 $f(x) = f(i-1) \times(k-2) + f(i-2) \times (k - 1)$。 可以理解为 ： 1. 在两个颜色相同的点中间插入一个颜色不同的，有 $(k-1)$ 种方案数。 2. 在两个颜色不同的点中间插入一个，有 $(k-2)$ 种方案数。 需要注意的是 ： 前三个的函数值很特殊。 $f(1) = k$ ， $f(2) = k \times (k - 1)$，$f(3) = k \times (k - 1) \times (k - 2)$。 预处理时注意一下即可。 **但是有一个很重要的问题，该怎么找到环呢？** 由于这里是内向基环树（每个点只有一条出边，即给人的感觉是内向的）。 所以只需要一直找他的父亲，然后直到重复为止。 $\color {red}(注意，这里还需要返回重复点的位置，以此才能判断是否在环内)

代码（请勿抄袭，码风不好勿喷）

/*
username :
Cenxi

time :
2024.11.24

problem name :
Mixing Chemicals
*/

#include <bits/stdc++.h>//头文件

using namespace std;//命名空间

const long long MOD (1e9 + 7);//模数
const long long MAX_VECTOR_SIZE (107);//最大空间

//father代表每个节点的父亲，f是预处理DP值。
//bz_ring用于深搜时标记节点用，bz_bz_ring来排除在同一个环里的节点，避免重复计算。
long long father[MAX_VECTOR_SIZE], f[MAX_VECTOR_SIZE], bz_ring[MAX_VECTOR_SIZE], bz_bz_ring[MAX_VECTOR_SIZE];

//t是数据组数，n是节点数，k是颜色数量。
long long t, n, k;

//cnt用于统计环里的节点数，ans计算答案，sum统计非环节点数
long long cnt, ans, sum;

//深搜，用来判断是否在环内。
inline long long deep_first_search (register const long long x)
{

    //已经标记过了
    if (bz_bz_ring[x] == 1)
    {

            //返回当前节点
        return x;
    }

    //标记节点 
    bz_bz_ring[x] = 1;

    //环长度加一
    ++ cnt;

    //返回重复的节点
    return deep_first_search (father[x]);
}

//标记环内节点
inline void bz_the_ring (register const long long x)
{

    if (bz_bz_ring[x] == 1)
    {

        return;
    }

        bz_bz_ring[x] = bz_ring[x] = 1;

        bz_the_ring (father[x]);
}

//主函数
int main (void)
{

    //关同步流，加速流输入输出
    ios :: sync_with_stdio (false);
    cin.tie (nullptr);
    cout.tie (nullptr);

    cin >> t;

        for (register long long x (1); x <= t; ++ x)
        {

            memset (bz_ring, 0, sizeof bz_ring);

            cin >> n >> k;

            ans = 1;
            sum = n;

            for (register long long i (0); i < n; ++ i)
            {   

                cin >> father[i];
        }

            //初始化DP数组方案数
        f[1] = k;
        f[2] = k * (k - 1);
        f[3] = k * (k - 1) * (k - 2) % MOD;

        for (register long long i (4); i <= n; ++ i)
        {

            f[i] = (f[i - 1] * (k - 2) % MOD + (f[i - 2] * (k - 1)) % MOD) % MOD;
        }

            //处理环上DP

        for (register long long i (0); i < n; ++ i)
        {

                //没有被标记过
            if (bz_ring[i] == 0)
            {

                    //初始化环长度为0
                cnt = 0;

                        //清空标记数组
                memset (bz_bz_ring, 0, sizeof bz_bz_ring);

                        //在环内
                if (deep_first_search (i) == i)
                {

                    memset (bz_bz_ring, 0, sizeof bz_bz_ring);

                            //表记所有环内的点
                    bz_the_ring (i);

                            //剩下的节点减去环内节点数
                    sum = sum - cnt;

                            //答案累乘
                    ans *= f[cnt];

                            //取模
                    ans %= MOD;
                }
            }
        }

            //乘上非环节点方案数
        for (register long long i (1); i <= sum; ++ i)
        {

            ans *= (k - 1);
            ans %= MOD;
        }

            //输出答案
        cout << ans << '\n';
    }

    //返回
    return 0;
}

完结撒花🎉🎉