​ 为什么要topo排序呢？辣么判断复杂而且还容易出锅qwq（我太菜了） ​ 直接上tarjan就好了啊！ ​ 这道题还是比较简单的，不过，如果我们dp方程没设好的话，在某些网站上就容易被卡（比如只有128MB的空间限制） ​ 我们观察题目，发现题目的K值很小，最大也就50，于是，我们可以从K值入手。 ​ 我们设dp(i,j)表示我们走到i号点，此时与最短路的“偏差值为j”的方案数 ​ 由于dp太烦，所以我选择记搜 ​ 我们先用dijkstra跑出1到每个点的最短路，设为dis[i] ​ 然后我们就来记搜。如果我们到达了n号点，我们就将现在的答案加一，但注意，不要直接return，因为我们可以...

相信大佬们都已经可以乱玩这道题了，所以大家就当看着玩吧。。。      提供一个新算法。。。   首先,我们来分析一下题目:  给一个有n个点的环图n种颜色，问本质不同的方案数  那么，很明显的，这是一个polya定理（废话，题目名说明了一切）  我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。）  我们就可以开始枚举置换了   首先，我们枚举每次平移的单位长度，那么很明显的本质不同的平移有n种，分别是平移0-(n-1)个单位  可以发现，每一种平移方案就是一种置换  所以，我们可以枚举平移长度，假设现在单步平移i个单位，那么要使得序列&...

【模板】Polya定理 题解 提供一个新算法。。。 首先,我们来分析一下题目: 给一个有n个点的环图n种颜色，问本质不同的方案数 那么，很明显的，这是一个polya定理（废话，题目名说明了一切） 我们先来看看这道题的“操作”，很明显的操作就是只有一个——平移（有人说旋转，但我个人更喜欢看成平移。。。） 我们就可以开始枚举置换了 首先，我们枚举每次平移的单位长度，那么很明显的本质不同的平移有n种，分别是平移0-(n-1)个单位 可以发现，每一种平移方案就是一种置换 所以，我们可以枚举平移长度，假设现在单步平移i个单位，那么要使得序列"平移"回来，我们假设最少要k步。那么k一定满足:i*k%n==...