sparse or not

行列 $M$ の $i$ 行 $j$ 列成分を $M_{i, j}$ と表記します。

$A \coloneqq \vec{u}^\top \vec{v}$ と置くと、$A_{i, j} = u_i v_j$ であるため

$(A^2)_{i, j} = \displaystyle\sum_{k = 1}^n A_{i, k} A_{k, j} = \displaystyle\sum_{k = 1}^n (u_i v_k) (u_k v_j) = \left(\displaystyle\sum_{k = 1}^n u_k v_k \right) u_i v_j = (\vec{u} \cdot \vec{v}) A_{i, j}$

が成り立ちます。

このように行列 $A$ に対して $A$ を掛けることはスカラー $(\vec{u} \cdot \vec{v})$ 倍することと等しいので、$A^k = (\vec{u} \cdot \vec{v})^{k - 1} A$ となります。

以下、場合分けして考えます。

1. $\ k = 1 \$ の場合

上記の内容とは関係無く、単に行列 $\vec{u}^\top \vec{v}$ に含まれる $0$ の数を求める問題となります。九九表のような表の中にいくつ $0$ があるかを数えることをイメージすると良いです。

$\vec{u}, \, \vec{v}$ の成分のうち $0$ であるものの個数をそれぞれ $u_0, \, v_0$ と置きます。「九九」の「$0$ の段」に表れる要素は全て $0$ となるので、重複を含めてそれらを数えた後に数えすぎた部分を引くことを考えると、答えは $(u_0 \times n + v_0 \times n - u_0 \times v_0)$ となります。

2. $\ k \neq 1 \$ かつ $\ \vec{u} \cdot \vec{v} \neq 0 \$ の場合

行列 $A$ は何乗しても（非零の）定数倍されるだけなので、$A^k$ に含まれる $0$ の個数と $A$ に含まれる $0$ の個数は等しいです。そのため、$k = 1$ として考えればよいです。

3. $\ k \neq 1 \$ かつ $\ \vec{u} \cdot \vec{v} = 0 \$ の場合

$A^k = (\vec{u} \cdot \vec{v})^{k - 1} A = 0 A$ より、$A^k$ は零行列です。よって答えは $n^2$ です。

---

解答例 (C++)

解答例 (Python 3)