这题可以做到 至多两次矩阵乘法，加上 $O(n^2)$ 的计数工作。设一次 $n\times n$ 矩阵乘法的复杂度为 $M(n)$，总时间就是 $O(M(n)+n^2)$，而不必停留在 $O(n^3)$。

题目给出无向简单图的邻接矩阵，要求统计长度不超过 $6$ 的简单环，且 $n\le 300$。这里统计的是普通简单环，不要求是诱导环，因此环上存在弦不影响计数。([qoj.ac][1])

从理论上说，这达到了矩阵乘法级别，通常记为 $O(n^\omega)$；小环计数可以达到这一复杂度，也是 Alon、Yuster、Zwick 的经典结果。

题解

设邻接矩阵为 $A$，计算 $B=A^2$ 和 $C=A^3$。记 $d_u$ 为顶点 $u$ 的度数，$t_u$ 为包含 $u$ 的三角形数量。对于不同的 $u,v$，$B_{uv}$ 是它们的公共邻居数量；另外，$d_u=B_{uu}$，$t_u=C_{uu}/2$。([Tel Aviv University Math Department][2])

我们还需要知道两个不同顶点之间，长度为 $3$ 的简单路径有多少条。

$C_{uv}$ 统计的是形如 $u\to a\to b\to v$ 的游走，不一定简单。由于没有自环，且 $u\ne v$，不简单只可能是 $b=u$ 或 $a=v$。前者有 $A_{uv}d_u$ 种，后者有 $A_{uv}d_v$ 种，两者的交集是 $u\to v\to u\to v$，有 $A_{uv}$ 种。因此，所需的简单路径数为

$$ P_{uv}=C_{uv}-A_{uv}(d_u+d_v-1),\qquad u\ne v. $$

不必实际存储矩阵 $P$，枚举顶点对时直接计算即可。

对于三元环，枚举一条无向边，再选择一个公共邻居；每个三角形被它的三条边分别统计一次，所以 $N_3=\frac13\sum_{u< v}A_{uv}B_{uv}$。对于四元环，枚举一对相对顶点，再选两个不同的公共邻居；每个四元环有两对相对顶点，所以 $N_4=\frac12\sum_{u< v}\binom{B_{uv}}2$。这两种情况都只需要计算 $A^2$。([Tel Aviv University Math Department][2])

对于五元环，可以将它拆成同端点的一条两边路径和一条三边路径。

固定无序端点对 ${u,v}$，暂时不要求两条路径的内部顶点互不相交，就有 $B_{uv}P_{uv}$ 种选择。不合法时，它们恰好共享一个内部顶点，所用边构成“一个三角形，接出一条指向三角形外的边”。

固定接出额外边的三角形顶点 $x$，三角形有 $t_x$ 种选择，额外边有 $d_x-2$ 种选择。每个这样的结构对应两个不合法路径对，因为可以选择三角形中另外两个顶点中的任意一个，作为外部顶点的配对端点。

因此，不合法路径对总数为 $2\sum_x(d_x-2)t_x$。每个五元环有 $5$ 种拆成两边路径和三边路径的方式，得到 $N_5=\frac15\left(\sum_{u< v}B_{uv}P_{uv}-2\sum_u(d_u-2)t_u\right)$。

真正需要仔细处理的是六元环。

把一个六元环拆成两条端点相同、内部顶点不相交的三边简单路径。固定无序端点对 ${u,v}$，先任意选两条不同的三边简单路径，候选数量为 $\binom{P_{uv}}2$。记候选总数为 $F=\sum_{u< v}\binom{P_{uv}}2$，下面扣除内部顶点相交的情况。

将两条路径都从同一个端点写向另一个端点，记为 $u\to a\to b\to v$ 和 $u\to c\to d\to v$。因为每条路径本身简单，且两条路径不同，不合法情况恰好分成以下三类。

第一类是相同位置的内部顶点重合，即 $a=c$ 或 $b=d$。两者不能同时发生，否则两条路径相同。

这种结构是一个四元环接出一条指向环外的边。例如两条路径为 $u\to x\to a\to v$ 和 $u\to x\to b\to v$，四元环为 $x\to a\to v\to b\to x$，额外边为 $(u,x)$。

先固定四元环的相对顶点 $x,v$，四元环有 $\binom{B_{xv}}2$ 种选择。再选择环外的 $u$，需要从 $x$ 的邻居中排除四元环上的另外三个顶点，因此有 $d_x-2-A_{xv}$ 种选择。合并 $(x,v)$ 与 $(v,x)$ 的贡献，第一类的总数为

$$ S=\sum_{u< v}(d_u+d_v-4-2A_{uv})\binom{B_{uv}}2. $$

第二类是恰好共享一个内部顶点，但该顶点在两条路径中的位置不同，例如 $a=d$。

此时所用边恰好构成两个只共享一个顶点的三角形。我们先统计这种三角形对。

记 $T=\sum_u\binom{t_u}{2}$，它是在每个顶点处选择两个不同三角形的总数。两个只共享一个顶点的三角形在 $T$ 中被统计一次；两个共享一条边的三角形，则在公共边的两个端点处分别被统计，共两次。

再记 $D=\sum_{u< v}A_{uv}\binom{B_{uv}}2$。固定公共边 $(u,v)$，选择两个不同的公共邻居，就得到两个共享该边的三角形，所以 $D$ 正好是共享边的三角形对数量。

因此，只共享一个顶点的三角形对共有 $T-2D$ 对。对于每一对，从两个三角形各自的两个非公共顶点中各选一个作为路径端点，就唯一确定一个不合法路径对，共有 $2\times2=4$ 种选择。第二类的总数就是 $4(T-2D)$。

第三类是两个内部顶点都重合，但顺序相反，即两条路径形如 $u\to a\to b\to v$ 和 $u\to b\to a\to v$。

这恰好对应两个共享边 $(a,b)$ 的三角形：${u,a,b}$ 和 ${v,a,b}$。每一对这样的三角形唯一确定一个不合法路径对，因此第三类的数量就是 $D$。

这三类互不相交，并且已经穷尽所有不合法情况，所以合法路径对数量是 $F-S-4(T-2D)-D=F-S-4T+7D$。每个六元环有三对相对顶点，最终得到

$$ \boxed{N_6=\frac{F-S-4T+7D}{3}.} $$

注意，上面始终统计的是选定的边和路径，没有要求这些结构是诱导子图。额外存在的边不会破坏上述对应关系。

所有公式都只涉及 $A,B,C$ 中的单个元素，以及单重或二重求和。因此，$k=3,4$ 只需一次矩阵乘法，$k=5,6$ 只需两次，其余工作均为 $O(n^2)$。总复杂度为 $O(n^{\omega})$。