No.985 Hadamard
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 15
作問者 :
tubuann1
/ テスター :
beet
タグ : / 解いたユーザー数 15
作問者 :
tubuann1
/ テスター :
beet
問題文最終更新日: 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)$ が最大である。
$|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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。