方法一

现有限制
\[a_1\neq a_2, a_2\neq a_3,...a_n\neq a_1\]
共 \(n\) 条。

设我们选定其中 \(k\) 条必须要违反，则有 \(n-k\) 个数的数值可以任取，方案数是
\[n^{n-k}\]
特别地，若 \(k\) 取 \(n\) ，这里答案是\(n\)

由容斥原理知，答案应当是
\[\sum_{k=0}^{n} (-1)^kC_n^k * n^{\max(1,{n-k})}\]

方法二

本题相当于求完全图 \(K_n\) 中的长度为 \(k\) 的圈的数量，即答案是\(tr(A(K_n)^k)\)

其中A(x)表示图x的邻接矩阵，tr(A)表示矩阵A的迹，\(\lambda_i\)表示矩阵的各个特征值。

运用线性代数的知识，可知\(tr = \sum \lambda_i^k\), 而完全图\(K_n\)的邻接矩阵\(A(K_n)\)的特征值有\(n-1\)个\(1\)和一个\(-(n-1)\)，所以答案是 \[(-(n-1))^k+(n-1)\]

时间复杂度是\(\mathcal{O(\log k)}\)

第一种方法得到的式子经过化简，也可以得到这样的答案。