Mixing Chemicals 题解

思路

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

What is Basal ring tree?

题目大意

给你一棵基环树，让你进行

k

分图染色。

求染色方案数。

思路

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

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

即环形

DP

和树形

DP

。

树形DP

很明显，每一个点都会连向一个点，那么每个点的染色方案数都为

(k-1)

种，则答案为

\color {blue}不在环上的点 \times(k-1)

。

环形DP

分两种情况来讨论。

我们设一个函数

f(x)

。

f(x)

代表环上有

x

个点已染色的方案数。

则

f(x) = f(i-1) \times(k-2) + f(i-2) \times (k - 1)

。

可以理解为：

在两个颜色相同的点中间插入一个颜色不同的，有 $(k-1)$ 种方案数。
在两个颜色不同的点中间插入一个，有 $(k-2)$ 种方案数。

需要注意的是：

前三个的函数值很特殊。

f(1) = k

，

f(2) = k \times (k - 1)

，

f(3) = k \times (k - 1) \times (k - 2)

。

预处理时注意一下即可。

但是有一个很重要的问题，该怎么找到环呢？

由于这里是内向基环树（每个点只有一条出边，即给人的感觉是内向的）。

所以只需要一直找他的父亲，然后直到重复为止。

\color {red}(注意，这里还需要返回重复点的位置，以此才能判断是否在环内)

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

CPP

/*
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;
}

题解：SP8064 AMR10J - Mixing Chemicals

文章操作