A. 环形划分
输出所有三个互不相同的 \(i,j,k\) 满足 \(i<j<k,i+j+k\equiv 0 \bmod n\) 即可
如果一种边的两端标号 \((i,j)\) 使得 \(i+j+i\equiv 0 \bmod n\),那么不会被输出
显然这样的边不会超过 \(n-1\) 个(枚举 \(i\),同时 \(n\) 不合法)
所以这个做法是正确的
B. 最小表示
考虑 \(SAM\) 来维护这样的子串,最后还是len[i]-len[fa[i]]
来统计答案
对于题目中的最小表示的定义,显然在其当前第一次出现的时候会不一样
下述视角均为从后往前,也就是下一次为通常意义上的左边一次
那么我们考虑其上一次出现之后到其的位置,维护每个位置最后在 \(SAM\) 上出现的位置 \(pos[i]\) 和其下一次在原串中出现的位置 \(dst[i]\)
每次扩展 \(pos[i],dst[i]\) ,注意只对当前点所对应的后缀自动机上的点的 \(size\) 加一
(要写那种广义自动机形式的东西)
最后遍历后缀树,对于有 \(size\) 大小的节点进行答案统计
后缀自动机上的节点不超过 \(\Theta(nm)\),证明考虑每种字符向前统计不超过 \(n\) 次
C. 置换矩阵
每天感受多项式和线性代数水之深
首先环的个数大于 \(1\) 则行列式的值为 \(0\),这个结论使用线性代数可以证明,但是我并不会证,貌似能打表
环的个数不大于 \(1\) 的部分考虑如下结论:
\[\texttt{n 阶循环矩阵的行列式为}=\prod_{j=0}^{n-1} A(\omega^j) \]其中 \(A(x)=\sum a_{i}x^i\) ,\(a_i\) 表示第一行第 \(i\) 列的元素
构造向量 \([\omega^0,\omega^1\cdots \omega ^{n-1}]\) 作为矩阵的特征值
那么把每一行计算出来,注意使用单位根的性质:\(\omega^{n-1}\times \omega =1\)
如果设 \(\lambda =A_{Line 1}\),那么矩阵的值就是 \(\lambda\) 的值
把单位根再拆(\(\omega=\omega'^{k}\)),之后有 \(\lambda_k=a_0+a_1\omega'^k+\cdots \omega^{'(n-1)k}\)
不难得到如果把 \(\lambda_k,k\in [0,n-1]\) 写成一个矩阵的形式,这个是一个 \(Vandemonder\) 矩阵,其行列式在组合数学里面写过了
\[\mathrm{Determine(B)}=\prod_{1\le i<j\le n} (\omega'^i-\omega'^{j}) \]显然这个矩阵的行列式不能为零,也就是 \(\lambda_k,k\in [0,n-1]\) 线性无关,所以矩阵 \(A\) 的行列式为
\[\mathrm{Determine(A)}=\prod_{i=0}^{n-1}\lambda_i \]这里使用了特征值的性质 \(\prod \lambda =\mathrm{Determine}(A)\),这个性质的证明并不会
最后把定义带入得证
为了得到一个循环矩阵,首先用置换把它换成一个循环矩阵,也就是把置换环断开成链,放上元素,这里需要统计逆序对来判断正负号
然后考虑模意义下并不能搞单位根,但是我们可以多项式 \(gcd\),也就是考虑 \(\omega_n^i\) 是 \(B(x)=x^n-1\) 的根,同时 \(\lambda\) 是多项式 \(A(x)=a_0+a_1\omega^k+\cdots \omega^{(n-1)k}\) 的根
不难发现这个 \(F(A,B)=b_m^n\prod A(\omega^i)\) 是原答案
这个函数有些性质(下设 \(B\) 为 \(m\) 次,\(A\) 为 \(n\) 次)
\[F(A,B)=(-1)^{nm}F(B,A) \] \[F(A,B)=a_n^mb_m^n[m=0\ or\ n=0] \] \[F(A,B)=b_m^{deg(A)-deg(A-CB)}F(A-CB,B) \]好像证明还可以,所以直接实现即可