首页 > 其他分享 >环上给n个区域用m种颜色染色,相邻不同

环上给n个区域用m种颜色染色,相邻不同

时间:2023-03-04 21:36:47浏览次数:45  
标签:种颜色 环上 染色 相邻 区域 不同

问题

在一个环上给n个区域用m种颜色染色,要求相邻区域颜色不同。

方法

1、公式

可以推出来一个公式为:\(res = (m-1)^n+(-1)^n(m-1),(m≥2)\)

直接用就行了

2、dp递推

详细过程看这位大佬的博客,我觉得讲的很清楚了:浅析一类要求相邻不同的环上染色问题 - sun123zxy - 博客园 (cnblogs.com)

标签:种颜色,环上,染色,相邻,区域,不同
From: https://www.cnblogs.com/blockche/p/17179195.html

相关文章

  • 分考场 【 DFS + 染色问题 】
    试题历届试题分考场资源限制时间限制:1.0s 内存限制:256.0MB问题描述n个人参加某项特殊考试。为了公平,要求任何两个认识的人不能分在同一个考场。求是少需......
  • [HAOI2018]染色
    \(\text{Solution}\)第二道二项式反演题挺套路的设\(g(i)\)为恰好出现\(S\)次的颜色至少有\(i\)种那么\[g(i)=\binom{m}{i}\binom{n}{is}\frac{(is)!}{(s!)^i}(......
  • 染色问题
    发现没学相关知识所以学学笔者写这篇文章时没应用过所以全是理论知识\(1.\)基础知识\(\textbf{定义1.1}\text{(置换)}\)一个\(S\)上的置换\(f:S\toS\)是一个......
  • 【NOIP2010】【codevs1069】关押罪犯(二分答案+二分图染色)
    problem将n个罪犯分别关押进2座监狱每2个罪犯之间有一个冲突值,当他们在同一监狱时就会爆发让爆发的冲突值(最大的那个)最小,求那个最小值solution考虑判定:是否存在一种分配方案......
  • 【YBT2023寒假Day6 C】子串染色(SAM)(线段树)(启发式合并)
    子串染色题目链接:YBT2023寒假Day6C题目大意对于一个s的子串t,把它在s中所有出现的位置包含的所有下标染黑,黑色连续段的数目是子串t的价值。然后给你一个k和一......
  • POJ 1436 Horizontally VisibleSegments(线段树成段更新+区间覆盖染色)
    DescriptionThereisanumberofdisjointverticallinesegmentsintheplane.Wesaythattwosegmentsarehorizontallyvisibleiftheycanbeconnectedbyaho......
  • 【YBT2023寒假Day4 A】网格染色(DP)(矩阵乘法)(DFT)
    网格染色题目链接:YBT2023寒假Day4A题目大意有一个n*3的网格,你可以选恰好m个格子染成黑色。然后对于一个黑点,我们对它周围的\(8\)个点中的一些有限制不能是黑点,......
  • 【题解】P4491 [HAOI2018]染色
    思路NTT优化二项式反演。首先考虑到求“正好有\(k\)种颜色出现\(S\)次”的方案数,所以可以考虑转化成求“至少有\(k\)种颜色出现\(S\)次”的方案数。形式化......
  • 通关搜索和图论 day_17 -- 染色法 & 匈牙利算法
    染色法一个图是二分图当且仅当她可以被2染色(不含有奇数环)流程如下,先找到一个不在集合中的点把他放在左边然后遍历这个点有连接的点,把这些点放到右边,再依次遍历放到右......
  • 二分图与染色算法
    二分图的概念二分图就是顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。    染色法概......