Для множества $$$\mathcal{A}$$$ целых чисел от $$$0$$$ до $$$n - 1$$$ определим величину $$$f(\mathcal{A})$$$ следующим образом. Над множеством выполняется последовательность из $$$n - 1$$$ шагов: на шаге с номером $$$i$$$ ($$$1 \le i \le n - 1$$$) каждый элемент $$$x$$$ текущего множества заменяется на $$$(x + 1) \bmod (n - i)$$$. Обратите внимание, что все элементы заменяются одновременно и содержатся в множестве в единственном экземпляре, из-за чего после очередного шага размер множества может уменьшиться.
Обозначим через $$$\mathcal{A}_i$$$ множество, полученное после $$$i$$$-го шага. Тогда $$$f(\mathcal{A})$$$ равно сумме значений $$$\operatorname{mex}$$$$$$^{\text{∗}}$$$ всех полученных множеств: $$$$$$f(\mathcal{A}) = \operatorname{mex}(\mathcal{A}_1) + \operatorname{mex}(\mathcal{A}_2) + \ldots + \operatorname{mex}(\mathcal{A}_{n - 1}).$$$$$$
У Димы есть множество $$$\mathcal{S}$$$, состоящее из различных целых чисел от $$$0$$$ до $$$n - 1$$$.
Дима хочет найти сумму $$$f(\mathcal{S}')$$$ по всем множествам $$$\mathcal{S}'$$$ таким, что $$$\mathcal{S} \subseteq \mathcal{S}' \subseteq \{0, 1, \ldots, n - 1\}$$$. Другими словами, он хочет найти сумму значений $$$f$$$ по всем надмножествам $$$\mathcal{S}$$$, содержащимся в $$$\{0, 1, \ldots, n - 1\}$$$. Пожалуйста, помогите ему.
Поскольку ответ может быть очень большим, выведите его по модулю $$$10^9 + 7$$$.
$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$x$$$, которое не встречается в наборе чисел $$$c$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$) — длину строки.
Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, задающую множество $$$\mathcal{S}$$$. Для каждого $$$0 \le i \lt n$$$ целое число $$$i$$$ принадлежит $$$\mathcal{S}$$$ тогда и только тогда, когда $$$(i+1)$$$-й символ строки $$$s$$$ равен 1.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — искомую сумму по модулю $$$10^9 + 7$$$.
4510110300091010101016000111
301430678
В первом примере существует всего $$$4$$$ множества, содержащих данное $$$\mathcal{S}$$$ в качестве подмножества: $$$\{0, 2, 3\}$$$, $$$\{0, 1, 2, 3\}$$$, $$$\{0, 2, 3, 4\}$$$ и $$$\{0, 1, 2, 3, 4\}$$$.
Для множества $$$\mathcal{A} = \{0, 2, 3\}$$$ последовательность изменений выглядит следующим образом: $$$$$$\{0, 2, 3\} \to \{0, 1, 3\} \to \{1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ Значения $$$\operatorname{mex}$$$ полученных множеств равны соответственно $$$2, 0, 2, 1$$$, поэтому: $$$$$$f(\{0, 2, 3\}) = 2 + 0 + 2 + 1 = 5.$$$$$$
Для множества $$$\mathcal{A} = \{0, 1, 2, 3\}$$$: $$$$$$\{0, 1, 2, 3\} \to \{0, 1, 2, 3\} \to \{0, 1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 1, 2, 3\}) = 4 + 3 + 2 + 1 = 10.$$$$$$
Для множества $$$\mathcal{A} = \{0, 2, 3, 4\}$$$: $$$$$$\{0, 2, 3, 4\} \to \{0, 1, 3\} \to \{1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 2, 3, 4\}) = 2 + 0 + 2 + 1 = 5.$$$$$$
Для множества $$$\mathcal{A} = \{0, 1, 2, 3, 4\}$$$: $$$$$$\{0, 1, 2, 3, 4\} \to \{0, 1, 2, 3\} \to \{0, 1, 2\} \to \{0, 1\} \to \{0\}$$$$$$ $$$$$$f(\{0, 1, 2, 3, 4\}) = 4 + 3 + 2 + 1 = 10.$$$$$$
Таким образом, итоговый ответ равен сумме по этим четырем множествам: $$$$$$5 + 10 + 5 + 10 = 30.$$$$$$
Во втором наборе входных данных множество $$$\mathcal{S}$$$ пусто, поэтому рассматриваются все $$$8$$$ подмножеств $$$\{0, 1, 2\}$$$. Значение $$$f$$$ равно $$$0$$$ для пустого множества, $$$1$$$ для каждого из множеств $$$\{0\}$$$, $$$\{2\}$$$ и $$$\{0, 2\}$$$, $$$2$$$ для $$$\{1\}$$$ и $$$3$$$ для каждого из трех оставшихся множеств. Таким образом, ответ равен $$$0 + 3 \cdot 1 + 2 + 3 \cdot 3 = 14$$$.
| Codeforces Round 1132 (Div. 2) |
|---|
| Закончено |
