No.985 Hadamard

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : tubuann1tubuann1 / テスター : beetbeet
1 ProblemId : 3876 / 出題時の順位表
問題文最終更新日: 2020-02-11 19:02:45

おことわり

想定解は Python3 では TLE しますが PyPy3 で提出すれば AC することが確認されています。

問題文

第 $0$ 項から第 $2^N-1$ 項までの $2^N$ 項からなる有理数の列 $A$ であって、以下の条件をみたすものを見つけてください。

  • $\displaystyle 0 \leq i \leq 2^N-1$ をみたす全ての整数 $i$ に対して、$\displaystyle L_i \leq \sum_{j=0}^{2^N-1} {(-1)}^{|i \& j|} A_j \leq H_i$
  • 上の条件をみたすもののなかで、$\displaystyle \sum_{i=0}^{2^N-1} (C_i \times A_i)$ が最大である。
$\& $ は bitwise and を表します。
$|x|$ は $x$ を二進数で表現したときに、$1$ である桁の数です。

条件をみたす有理数の列 $A$ が存在するなら、$\displaystyle \sum_{i=0}^{2^N-1} (C_i \times A_i) \bmod 998244353$ を求めてください。
そうでないなら、$-1$ を出力してください。

整数 $P$ と $998244353$ の倍数でない整数 $Q$ を用いて $\frac{P}{Q}$ と表せる有理数に対して、$\frac{P}{Q} \bmod 998244353$ とは、$P \equiv Q \times R \bmod 998244353$ をみたす最小の非負整数 $R$ のことです。
条件をみたす $A$ が存在するなら、この問題の制約のもと、答えをそのように表すことができると証明できます。

入力

$N$
$C_0\ C_1\ \ldots \ C_{2^N-1}$
$L_0\ H_0$
$\vdots$
$L_{2^N-1}\ H_{2^N-1}$

$1 \leq N \leq 18$
$-10^5 \leq C_i \leq 10^5$
$-10^5 \leq L_i \leq H_i \leq 10^5$
入力は全て整数である

出力

答えを一行に出力する。

サンプル

サンプル1
入力
2
0 0 0 0
-100 100
-100 100
-100 100
-100 100
出力
0

サンプル2
入力
2
2 -1 -1 -1
-100 100
-100 100
-100 100
-100 100
出力
250

サンプル3
入力
3
812 -1289 1103 -987 1010 999 -1111 -1079
-12783 89123
98 29138
-32894 8293
-10 10
-21399 89233
-81323 -13278
-82139 -31728
17839 78123
出力
561535060

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。