思维题泛刷记录

简介

此文为本人泛刷思维题的简要题解，用以记录一些思维精彩的题。

折叠的代码中有原题链接方便跳转。（实现过于简单的题直接提供链接）

正文

Luogu_P6075

link

题目中 个元素可以看作 种颜色。关键在于注意到每种颜色是独立的，可以分开考虑。

对于一种颜色，在图上染色的轮廓应为左上部分染而右下不染，而每种方案正好对应一条从左下角点出发到达对角线的右上顶点的路径。

如图所示：

由于每条路径都是等长的，而且每次都有向上或者向右两种分支，所以单一颜色的贡献为 ，故答案为 。