問題一覧 > 通常問題

No.985 Hadamard

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : tubuann1 / テスター : beet
お気に入りにしたユーザー ProblemId : 3876 / 自分の提出
問題文最終更新日: 2020-02-11 19:02:45
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 236 (順位表) の他の問題:

Disclaimer

It has been confirmed that the intended solution gets TLE in Python3 but gets AC when submitted in PyPy3.

Problem Statement

Find a sequence $A$ of rational numbers consisting of $2^N$ terms, from the $0$-th term to the $2^N-1$-th term, that satisfies the following conditions.

  • For every integer $i$ satisfying $\displaystyle 0 \leq i \leq 2^N-1$, $\displaystyle L_i \leq \sum_{j=0}^{2^N-1} {(-1)}^{|i \& j|} A_j \leq H_i$.
  • Among those satisfying the above condition, $\displaystyle \sum_{i=0}^{2^N-1} (C_i \times A_i)$ is maximum.
$\& $ denotes bitwise and.
$|x|$ is the number of digits that are $1$ when $x$ is represented in binary.

If a sequence $A$ of rational numbers satisfying the conditions exists, find $\displaystyle \sum_{i=0}^{2^N-1} (C_i \times A_i) \bmod 998244353$.
Otherwise, output $-1$.

For a rational number that can be expressed as $\frac{P}{Q}$ using an integer $P$ and an integer $Q$ that is not a multiple of $998244353$, $\frac{P}{Q} \bmod 998244353$ is the smallest non-negative integer $R$ satisfying $P \equiv Q \times R \bmod 998244353$.
If an $A$ satisfying the conditions exists, it can be proved that under the constraints of this problem, the answer can be expressed in this way.

Input

$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$
All inputs are integers.

Output

Output the answer on a single line.

Sample

Sample 1
Input
2
0 0 0 0
-100 100
-100 100
-100 100
-100 100
Output
0

Sample 2
Input
2
2 -1 -1 -1
-100 100
-100 100
-100 100
-100 100
Output
250

Sample 3
Input
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
Output
561535060

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