UOJ Logo 150137的博客

博客

UNR#2 T1 的一些其他做法

2017-07-13 17:12:25 By 150137

这题大家貌似都见过原题qwq,我比较菜所以没见过。我们机房一共有四个人打UNR,然后一共有三个做法,有基友问都是什么我就简单说说qwq

我的做法和题解是一样的,详情还是看乐滋滋的题解

我左边的同学做法是这样的

他考虑对于一个图进行二分图染色,然后考虑进行染色的第一个点其实是有 $k$ 种方案的,然后对于同在一个联通块内的一个点每个点的贡献都是 $k-1$

一个简单的证明是这样的,首先我们造一棵树出来,显然这个东西是完全合法的,然后考虑加上一些非树边,由于是二分图,所以加上非树边之后显然环是偶环,那么显然第一个点和最后一个点总是不能同色的,所以他的方案数和不连边的方案数是同样的,所以就是 $k-1$

如果是非二分图,对于一种合法染色,我们循环一下就行啦,显然必然包括 $3!$ (因为两种颜色没法给他染色辣)

我对面的同学好像更diao一些大概是导出了一个类似环的多项式然后推出了一个非常简单的式子,具体意思看看代码大概还是可以接受的 CQzhangyu's Ac solution

我们现在来看看他们为啥相等……

我们考虑欧拉定理的拓展定理

$$ a^b \equiv \begin{cases} a^{b \bmod \varphi(p) } & { \gcd(a,p) = 1} \\ a^{b \bmod \varphi(p) + \varphi(p)} & \gcd(a,p) \neq 1, b \geq \varphi(p) \\ \end{cases} \pmod p $$

$\varphi(6) = \varphi(2)\times \varphi(3) = 1 \times 2 = 2$

然后……

233333333333333333333333333333333333333333333333333

评论

150137
前排……qwq
samzhang
楼主不要只写定理内容不写前提条件啊喂!
150137
@mike
WrongAnswer
我的想法可能比较奇怪…… 首先每个连通块独立,可以分别计算每个连通块乘起来。现在假设图连通。 考虑暴搜,如果有三元环(a,b,c),那么显然可以把a,b,c分别染色1,2,3,求剩下点的染色方案,然后答案乘上k(k-1)(k-2)。 因为6|k(k-1)(k-2),所以有三元环答案就是0。 否则,如果一个点a与两个点b,c相邻,那么可以把b,c缩成一个点(染色方案分b,c同色和b,c不同色两类,后者相当于连一条(b,c)边,出现三元环,答案为0,故只统计b,c同色的方案) 因此选一个点v为起点对这个图BFS一遍,到v距离相等的点都可以缩成一个点。如果缩完出现自环答案是0,否则图等价于链。 即:如果存在边(a,b),a,b到v距离相等,答案为0,否则答案为k(k-1)^(n-1)。 这个做法和判二分图应该是等价的。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。