指数公式 - Problème

数え上げ問題において、$998244353$ や $10^9+7$ で割った余りを求めたり、FFT を2回回して多点評価をしたりすることには、もう皆さんも飽き飽きしていることでしょう。

小さな素数を法とする問題についても、例えば昨年 zx2003 が皆さんに伝えようとした、小さな素数における小さな多項式の高階冪の遠方の係数のような先例がいくつかあります。

今日は余計なことはせず、法を $2$ とします。つまり、ゼロとイチの世界を見ていきましょう。

正の整数の集合 $S$ が与えられます。$1\le k\le n$ のそれぞれについて、番号 $1$ から $k$ までのボールをいくつかの箱に入れる方法のうち、各箱に入っているボールの個数が $S$ に属するようなものの総数を求めてください。ただし、答えの偶奇のみを知りたいものとします。

注意：ボールは区別でき、箱は区別できません。

長さ $n$ の 01 文字列が与えられます。第 $x$ 文字目が $1$ であることは、$x\in S$ であることを意味します。

長さ $n$ の 01 文字列を出力してください。第 $k$ 文字目は $a_k \bmod 2$ を表します。

例 1 について、各 $k$ に対する組み合わせの総数は以下の通りです。

$k=1$：$\{\{1\}\}$、計 $1$ 通り。

$k=2$：$\{\{1\},\{2\}\}$、計 $1$ 通り。

$k=3$：$\{\{1\},\{2\},\{3\}\},\{\{1,2,3\}\}$、計 $2$ 通り。

$k=4$：

$k=5$：計 $16$ 通り。すべてを列挙することは省略します。

$10\%$ のデータについて、$n\le 10$。

$40\%$ のデータについて、$n\le 2000$。

$70\%$ のデータについて、$n\le 3\times 10^5$。

$100\%$ のデータについて、$n\le 2\times 10^6$。

QOJ.ac