/ 
実行時間制限: 30 sec / メモリ制限: 1024 MB
注意
問題文中の数式が正しく表示されない場合は、新システム上のページにアクセスし直してご覧ください。
問題文
この問題は「問題 A」と同一の問題であるが、制約が異なる。問題文本文は問題 A のページを、制約は以下を参照のこと。
入力
入力は以下の制約を満たす。
- 3 \leq N \leq 300
- 1 \leq K \leq 1000
- 0 \leq d_i \leq \min(N, 6)
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- 全ての j (1 \leq j \lt d_i) について、v_{i, j} < v_{i, j+1}
- i \neq j ならば \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right]
- d_i = 0 となる行は高々 1 度しか登場しない
- 全ての k (1 \leq k \leq N) に対して、k = v_{i, j} を満たす (i, j) が少なくとも 1 つ存在する
Notification
In case equations are not displayed properly, we recommend taking a look at the new AtCoder system.
Problem Setting
The task in problem setting B is almost equivalent to problem setting A. Hence, for details on the task the contestant is refered to problem setting A. The only difference in Problem B is the shape of the higher order pseudo-Boolean function which serves as an input. This input will now have degree at most 6 (d=6), while still maintaining a sparse structure. For details of the input problem contestants are referred to the section below.
Input Format
The following requirements shall be imposed on the input problem.
- 3 \leq N \leq 300
- 1 \leq K \leq 1000
- 0 \leq d_i \leq min(N,6)
- 1 \leq \left|c_i \right| \leq 100
- 1 \leq v_{i, j} \leq N
- For all j (1 \leq j \lt d_i) we require v_{i, j} < v_{i, j+1}
- For two lines i,j with i \neq j we require \left[ v_{i, 1}, \dots , v_{i, d_i} \right] \neq \left[ v_{j, 1}, \dots, v_{j, d_j} \right], i.e., two separate lines shall not encode the same type of monomial.
- The line d_i = 0 should not exceed beyond the coefficient.
- All of the variables k (1 \leq k \leq N) should appear in at least one of the term, i.e., there exists at least one v_{i,j} such that k = v_{i, j}.