2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics [2020/05/19 21:06] wzx27 |
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics [2020/05/21 17:43] (当前版本) wzx27 |
||
|---|---|---|---|
| 行 78: | 行 78: | ||
| 2、[[http://poj.org/problem?id=2888|poj2888 Magic Bracelet]] | 2、[[http://poj.org/problem?id=2888|poj2888 Magic Bracelet]] | ||
| - | $m$种颜色染正$n$边形，但有限制条件颜色$u$和$v$不能同时出现 | + | $m$种颜色染正$n$边形，但有限制条件颜色$u$和$v$不能相邻出现 |
| - | 注意：$m$很小 | + | 注意：$m<10$ |
| 对于颜色是否能同时出现的问题，考虑用一个关于颜色的邻接矩阵$G$来表示两个颜色之间的关系: | 对于颜色是否能同时出现的问题，考虑用一个关于颜色的邻接矩阵$G$来表示两个颜色之间的关系: | ||
| 行 90: | 行 90: | ||
| 对于有上述限制的，可以这么做，构造出邻接矩阵后，有 | 对于有上述限制的，可以这么做，构造出邻接矩阵后，有 | ||
| - | $$\mathcal{C}(\rho^i)=\sum_i\sum_j G^{gcd(n,i)-1}[i][j]$$ | + | $$\mathcal{C}(\rho^i)=\sum_i\sum_j G^{gcd(n,i)-1}[i][j]\times [G[i][j]==1]$$ |
| - | 在离散数学的图论中曾提到$G^k[i][j]\; :=\; i出发，经过k条边到达j的路径数$ | + | 在离散数学的图论中曾提到$$G^k[i][j]\; :=\; i出发，经过k条边到达j的路径数$$ |
| - | 在这里就是$G^k[i][j]\; :=\; 第一个循环节的颜色是i，最后一个循环节的颜色是j的染色数$ | + | 在这里就是$$G^k[i][j]\; :=\; 第1个循环节的颜色是i，第k+1个循环节节的颜色是j的染色数$$ |
| + | |||
| + | 因为最后一个循环节会和第一个循环节的下一个元素再次相邻，所以只对$G[i][j]==1$的$G^{gcd(n,i)-1}[i][j]$算贡献 | ||
| + | |||
| + | 然后我们会发现这实际上就是 | ||
| + | $$\mathcal{C}(\rho^i)=\sum_i\sum_j G^{gcd(n,i)-1}[i][j]\times [G[i][j]==1]=\sum_iG^{gcd(n,i)}[i][i]$$ | ||
| + | |||
| + | 即第一个循环节颜色是$i$经过$gcd(n,i)+1$条合法路径又回到自身的数量 | ||
| + | |||
| + | 所以只要用矩阵快速幂优化一下就可以了 | ||
2020-2021/teams/wangzai_milk/wzx27/combinatorial_mathematics.1589893599.txt.gz · 最后更改: 2020/05/19 21:06 由 wzx27
