「考试总结2021-04-06」 线代

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) \]

好像证明还可以,所以直接实现即可

上一篇:【题解】 集合论 互测题 分块+欧拉序+压位


下一篇:FFT——快速傅里叶变换