Complementary Subset Transform

2 secs 1024 MB
suisen's icon suisen

Complementary Subset Transform

問題文

非負整数 NN と長さ 2N2^N の整数列 (t0,,t2N1)(t_0,\ldots,t_{2^N-1}) および (v0,,v2N1)(v_0,\ldots,v_{2^N-1}) が与えられます。

全単射な関数 f:2{0,,N1}{0,,2N1}f:2^{\{0,\ldots,N-1\}}\to \{0,\ldots,2^N-1\}f(S)=iS2i\displaystyle f(S)=\sum_{i\in S}2^i で定めます。

関数 g:2{0,,N1}Zg:2^{\{0,\ldots,N-1\}}\to\mathbb{Z} および h:2{0,,N1}Zh:2^{\{0,\ldots,N-1\}}\to\mathbb{Z} について、以下の3つの条件が全て同時に成り立つとき、またその時に限って (g,h)(g,h) は「良い組」と言うことにします。ここで、Z\mathbb{Z} は整数全体の集合を表すものとします。

  • 条件 1:

    S{0,,N1}.    0g(S),h(S)<998244353\forall S\subseteq\{0,\ldots,N-1\}.\;\;0\leq g(S),h(S)\lt 998244353

  • 条件 2:

    h(S)TSg(T)(mod998244353)\displaystyle h(S)\equiv\sum_{T\subseteq S}g(T)\pmod{998244353}

  • 条件 3:

    全ての i=0,,2N1i=0,\ldots,2^N-1 に対して、ti=0t_i=0 ならば g(f1(i))=vig(f ^ {-1}(i))=v_iti=1t_i=1 ならば h(f1(i))=vih(f ^ {-1}(i))=v_i が成り立つ。

ABA \subseteq BAABB の部分集合であることを表し、特に、A=BA=B の場合も ABA \subseteq B であることに注意してください。

「良い組」であるような関数の組 (g,h)(g,h) を求めてください。ここで、この問題の制約下において「良い組」であるような (g,h)(g,h) は必ず存在し、一意に定まることが証明できます。

制約

  • 入力は全て整数で与えられる
  • 0N190\leq N\leq 19
  • ti{0,1}t_i\in\{0,1\}
  • 0vi<9982443530\leq v_i\lt 998244353

入力

N
t_0 v_0
t_1 v_1
 :   :
t_{2^N-1} v_{2^N-1}

出力

1 行目に空白区切りで g(f1(0)),g(f1(1)),,g(f1(2N1))g(f^{-1}(0)),g(f^{-1}(1)),\ldots,g(f^{-1}(2^N-1)) の順に出力し、2 行目に空白区切りで h(f1(0)),h(f1(1)),,h(f1(2N1))h(f^{-1}(0)),h(f^{-1}(1)),\ldots,h(f^{-1}(2^N-1)) の順に出力してください。

注意

入出力量が非常に多くなっている ので、高速な入出力を用いた解答を作成することをおすすめします。

また、Python を使われる方は PyPy を使うなどの更なる高速化が必要になる可能性があるので、注意してください。なお、PyPy で AC 可能なことは確認済みです。

入力例 1

3
0 1
0 2
1 4
1 10
1 6
0 6
1 16
0 8

出力例 1

1 2 3 4 5 6 7 8
1 3 4 10 6 14 16 36

ff について、以下が成り立ちます;

f()=i2i=0,f({0})=i{0}2i=20=1,f({1})=i{1}2i=21=2,f({0,1})=i{0,1}20+21=3,f({2})=i{2}2i=22=4,f({0,2})=i{0,2}2i=20+22=5,f({1,2})=i{1,2}2i=21+22=6,f({0,1,2})=i{0,1,2}2i=20+21+22=7.\begin{aligned}f(\emptyset)&=\sum_{i \in \emptyset} 2^i=0,\\f(\{0\})&=\sum_{i \in \{0\}} 2^i=2^0=1,\\f(\{1\})&=\sum_{i \in \{1\}} 2^i=2^1=2,\\f(\{0,1\})&=\sum_{i \in \{0,1\}} 2^0+2^1=3,\\f(\{2\})&=\sum_{i \in \{2\}} 2^i=2^2=4,\\f(\{0,2\})&=\sum_{i \in \{0,2\}} 2^i=2^0+2^2=5,\\f(\{1,2\})&=\sum_{i \in \{1,2\}} 2^i=2^1+2^2=6,\\f(\{0,1,2\})&=\sum_{i \in \{0,1,2\}} 2^i=2^0+2^1+2^2=7.\end{aligned}

従って、出力は以下を表しています;

g()=1,h()=1,g({0})=2,h({0})=3,g({1})=3,h({1})=4,g({0,1})=4,h({0,1})=10,g({2})=5,h({2})=6,g({0,2})=6,h({0,2})=14,g({1,2})=7,h({1,2})=16,g({0,1,2})=8,h({0,1,2})=36.\begin{aligned}g(\emptyset)&=1,&h(\emptyset)&=1,\\g(\{0\})&=2,&h(\{0\})&=3,\\g(\{1\})&=3,&h(\{1\})&=4,\\g(\{0,1\})&=4,&h(\{0,1\})&=10,\\g(\{2\})&=5,&h(\{2\})&=6,\\g(\{0,2\})&=6,&h(\{0,2\})&=14,\\g(\{1,2\})&=7,&h(\{1,2\})&=16,\\g(\{0,1,2\})&=8,&h(\{0,1,2\})&=36.\end{aligned}

例えば集合 {0,2}\{0,2\} に対して T{0,2}g(T)=g()+g({0})+g({2})+g({0,2})=1414=h({0,2})(mod998244353)\displaystyle\sum_{T\subseteq\{0,2\}}g(T)=g(\emptyset)+g(\{0\})+g(\{2\})+g(\{0,2\})=14\equiv 14=h(\{0,2\}) \pmod{998244353} となっており、他の集合についても同様のことが成り立っています。

入力例 2

0
0 1

出力例 2

1
1

出力は以下を表しています;

g()=1,h()=1.\begin{aligned}g(\emptyset)&=1,&h(\emptyset)&=1.\end{aligned}

入力例 3

4
1 777152734
0 550347992
0 235168257
1 144477563
1 585929863
0 858171584
1 818879757
0 679108730
1 524987698
0 30723482
1 930753192
0 62091982
0 76040925
1 601879738
0 12576214
1 819937728

出力例 3

777152734 550347992 235168257 578297286 807021482 858171584 996025990 679108730 746079317 30723482 170597237 62091982 76040925 749319634 12576214 478925353
777152734 329256373 14076638 144477563 585929863 996205086 818879757 490072290 524987698 107814819 930753192 155725228 409805752 601879738 825929097 819937728

値を 00 以上 998244353998244353 未満に収める必要があること注意してください。

入力例 4

2
1 655889094
1 170766494
1 640786659
0 882726329

出力例 4

655889094 513121753 983141918 882726329
655889094 170766494 640786659 40146035

提出


Go (1.21)