解説

$N$ 個の単語から $i$ 個の単語を選んで並べる方法は $N \times (N - 1) \times (N - 2) \times \cdots \times (N - i + 1)$ 通りあります。この値を $P(N, i)$ とおきます。例えば、$5$ 個の単語から $3$ 個の単語を選んで並べる方法は $P(5, 3) = 5 \times 4 \times 3 = 60$ 通りあります。

この問題では単語を $1$ 個以上 $N$ 個以下選んで並べる場合の数を問われているため、答えは $\displaystyle\sum_{i = 1}^N P(N, i)$ となります。

各 $i$ に対して毎回 $P(N, i)$ の値を定義通り計算する $\left( \displaystyle\sum_{i = 1}^N \displaystyle\prod_{j = N - i + 1}^N j \ を 2 重ループで計算する \right)$ アルゴリズムの時間計算量は $\Theta(N^2)$ となる (整数の加算と乗算の時間計算量が $\Theta(1)$ であることを仮定しています) ため、2 秒間の実行時間制限に恐らく間に合いません。

しかし、$P(N, i)$ の値は $P(N, i - 1)$ の計算結果を利用して求められることに注目すると時間計算量を $\Theta(N)$ に削減することができ、この問題に正解できます。

$P(N, i - 1) = \textcolor{red}{N \times (N - 1) \times (N - 2) \times \cdots \times \{N - (i - 1) + 1\}}$

$P(N, i) \hspace{1.75em} = \textcolor{red}{N \times (N - 1) \times (N - 2) \times \cdots \times \{N - (i - 1) + 1\}} \times (N - i + 1)$

$\hspace{5.3em} = P(N, i - 1) \times (N - i + 1)$

解答例 (C++)

おまけ

walking dictionary