2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:wangzai_milk:wzx27:combinatorial_mathematics [2020/05/19 16:51] 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$来表示两个颜色之间的关系: | ||
| $$G[u][v]=G[v][u]=0\; \leftrightarrow \; u和v不能同时出现$$ | $$G[u][v]=G[v][u]=0\; \leftrightarrow \; u和v不能同时出现$$ | ||
| + | 接着更泛化地表示每个旋转置换$\rho^i$的对非等价着色数的贡献$\mathcal{C}(\rho^i)$ | ||
| + | |||
| + | 首先$\rho^i$会产生$gcd(n,i)$个长度为$\frac n{gcd(n,i)}$循环节，然后枚举每个循环节的颜色就得到了$\mathcal{C}(\rho^i)$，例如没有任何限制时每个循环节都可以取$m$种颜色，所以$\mathcal{C}(\rho^i)=m^{gcd(n,i)}$ | ||
| + | |||
| + | 对于有上述限制的，可以这么做，构造出邻接矩阵后，有 | ||
| + | |||
| + | $$\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]\; :=\; 第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.1589878269.txt.gz · 最后更改: 2020/05/19 16:51 由 wzx27
