Sets#253

Sets (Editorial)

Знайдемо замкнену формулу для $f ([n], k)$ f([n], k).

Почнемо з бази: $f ([n], 1)$ f([n], 1) — кількість підмножин множини з $n$ елементів, тобто $2^{n}$ 2^n.

Тепер загальний крок. За означенням

f ([n], k) = s \subseteq [n] \sum f (s, k - 1) .

f([n], k) = \sum_{s \subseteq [n]} f(s, k-1).

Значення $f (s, k - 1)$ f(s, k-1) залежить лише від розміру $s$ , а підмножин розміру $j$ рівно $(j n)$ \binom{n}{j}. Тому, позначивши $F_{k} (n) = f ([n], k)$ F_k(n) = f([n], k), маємо

F_{k} (n) = j = 0 \sum n (j n) F_{k - 1} (j) .

F_k(n) = \sum_{j=0}^{n} \binom{n}{j} F_{k-1}(j).

Припустимо (індукція за $k$ ), що $F_{k - 1} (j) = k^{j}$ F_{k-1}(j) = k^{\,j}. Це вірно для $k - 1 = 1$ k-1 = 1, бо $2^{j}$ 2^j. Тоді

F_{k} (n) = j = 0 \sum n (j n) k^{j} \cdot 1^{n - j} = (k + 1)^{n}

F_k(n) = \sum_{j=0}^{n} \binom{n}{j} k^{\,j} \cdot 1^{\,n-j} = (k+1)^n

за біномом Ньютона.

Отже, відповідь — просто

f ([n], k) = (k + 1)^{n} mod (1 0^{9} + 7) .

f([n], k) = (k+1)^n \bmod (10^9 + 7).

Перевіримо на прикладах з умови: $n = 1$ n = 1, $k = 1$ k = 1 дає $2^{1} = 2$ 2^1 = 2; $n = 2$ n = 2, $k = 2$ k = 2 дає $3^{2} = 9$ 3^2 = 9. Обидва збігаються.

Обчислюється це швидким піднесенням до степеня за $O (lo g n)$ \mathcal{O}(\log n). Не забудьте взяти $k + 1$ k+1 за модулем перед піднесенням, бо $k$ сягає $1 0^{9}$ 10^9.

f ([n], k)

f ([n], 1)

2^{n}

f ([n], k) = s \subseteq [n] \sum f (s, k - 1) .

f (s, k - 1)

(j n)

F_{k} (n) = f ([n], k)

F_{k} (n) = j = 0 \sum n (j n) F_{k - 1} (j) .

F_{k - 1} (j) = k^{j}

k - 1 = 1

2^{j}

F_{k} (n) = j = 0 \sum n (j n) k^{j} \cdot 1^{n - j} = (k + 1)^{n}

f ([n], k) = (k + 1)^{n} mod (1 0^{9} + 7) .

n = 1

k = 1

2^{1} = 2

n = 2

k = 2

3^{2} = 9

O (lo g n)

k + 1

1 0^{9}