No.985 Hadamard
問題文最終更新日: 2020-02-11 19:02:45
English (AI translation)
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.
$|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もしくは右上の雲マークをクリックしてアカウントを作成してください。
tubuann1
beet