T1 同色三角形

考察容斥定理和计算贡献的思想

本题在计算同色三角形数量，难以计算，可以用总数减去异色三角形的数量——任选三个点的方案数为 ，减去异色三角形，就是同色三角形数量。

对于某一个点而言，假设有 条红色边， 条绿色边，那么它对异色三角形数量的贡献——任选一红边 P 一绿边 Q，都可以确定一个三角形（因为这是完全图，所以 P Q 之间也一定有一条边，又因为 P Q 这两条边是异色的，说明这个三角形肯定是异色的）

计算贡献：那么也就是说这个顶点就会参与 个异色三角形的组成。

统计所有点的贡献 ，请注意：一个异色三角形上有两个点会被统计贡献，所以 才是异色三角形的数量。题目保证这样的图一定存在，所以无需担心 不是整数。

综上：同色三角形的数量就是 。

T2 任务

我们考虑如何求出包含 这个子序列的长为 的字符串 有多少个。令 表示目前枚举到了 的第 位，匹配到了 的第 位的方案数。那么

（要么第 位匹配上了，那么 的取值就只有一种，要么第 位没有匹配上，那么取值就有 25 个）

所以我们发现答案只与 有关，与 内容无关。如果处理好这些 的话，将可以获得 50~70 的暴力分。

100pt

通过大眼观察法，我们发现

因为 ，所以 至多有 种。那么我们就可以维护一个单点修改，区间查询乘积的线段树了。

T3 加法方案

发现若 可以为空，则 可以和 构成双射，则最终答案即为 。

考虑求 ，可以考虑每一位的贡献，则有从高到低第 位的贡献为

考虑这个 式子的组合意义，记 ，即为给出标号分别为 的 个小球，选出 个小球放入 个盒子中。

考虑钦定剩下的 个小球放入第 个盒子，则该式即为将 个小球放入 个盒子中的方案数，即 。

预处理出 和 的幂次即可做到 。

感谢拔钉党贡献的题解。

T4 打标签

首先考虑 时怎么做。设存在感序列为 ，友好度序列为 。

手动模拟一下，可以发现当 时才可能有多解或无解，其余情况均有唯一解。

当 时，有

这样我们就可以求出所有 的 了。

然后反着来一遍，就容易求出所有地方的值。

更具体一点，先按照顺序求出红色位置的值，然后按照顺序求出蓝色位置的值，最后求出绿色位置的值。

当 时，也可以用类似的方法解决。

当 时，蓝色位置与红色位置恰好重合，所以不能使用上述方法。

手动模拟样例，可以得到结论，当 时，无解，或 为任何值都有解。

以 举例，若存在一组解为 ，则存在解 ++ 。

我们只需要让所有余数为 的位置加上 ，余数为 的位置减去 ，就可以构造出一组新的解。

所以我们可以强制规定 ，然后对序列的后 个位置做 的情况即可。

这样 就做完了，那么 更大的时候怎么做呢？

首先考虑一个别的问题，题目中给出了 ，让我们求出 ，这样并不好做。

但是我们如果知道了 ，能否快速求出 ？

时，很好做，因为一定有 。

对于 的情况，从 到 枚举每一个维度，然后合并当前维度下的相邻点。

这样我们就能在知道 的情况下求出 。我们发现这个做法本质上是做了 遍 的问题。

回到原问题。

枚举 到 的每一个维度，并对每个维度，都做一遍 的情况。

然后我们就从 数组得到了 数组。

时间复杂度 + 。