← 返回题目列表

AtCoder · xmascon23_h

H. 如何提出这样的问题

中文机器翻译题面 查看原题

配点 : 100 点

我们做到了 不 证明我们的解决方案适用于 (1 - \varepsilon) 在相当小的限制内所有可能的情况 \varepsilon。我们致以最诚挚的歉意。我们郑重声明,实际测试是按照问题陈述中所述随机生成的,无意支持我们的解决方案。我们祝您圣诞快乐,以便您可以安全地忽略可能会给您的解决方案带来麻烦的罕见情况。 给出

問題文

正整数 N 以及 16 整数 W_{i,j} (0 \le i,j \le 3)。在这里,W_{0,0}=0 有保证。

兔子当前在平面上的坐标 站在 (0,0) 处,根据需要多次执行以下操作。

  • 当前站立坐标 (x,y) 。整数 i,j (0 \le i,j \le 3)和坐标 跳转到 (x+i,y+j) 并移动。这时, 必须满足x+i \geq y+j 。这个操作重量是 W_{i,j} 。

操作序列权重 将定义为其中执行的操作权重的总乘积。 解决

各 k=1,2,\ldots,N 的以下问题。

  • 阿兔终于找到坐标了 导致 (k,k) 的所有操作序列的权重之和为 除以 998244353 求余数。

将公开有关此问题的测试用例的以下信息。

  • 对于除样本之外的所有测试用例,W_{i,j} 的值是在约束范围内统一随机选择的。
  • 不包括样本的测试用例总数为 按此顺序输出 10 。

制約

  • 2 \le N \le 250\,000.
  • 0 \le W_{i,j} < 998244353 (0 \le i,j \le 3).
  • W_{0,0}=0.

入力

输入是按以下格式从标准输入给出的。

N
W_{0,0} W_{0,1} W_{0,2} W_{0,3}
W_{1,0} W_{1,1} W_{1,2} W_{1,3}
W_{2,0} W_{2,1} W_{2,2} W_{2,3}
W_{3,0} W_{3,1} W_{3,2} W_{3,3}

出力

各 k=1,2,\ldots,N 的答案,并用空格分隔。


入力例 1

10
0 1 0 0
1 0 0 0
0 0 0 0
0 0 0 0

出力例 1

1 2 5 14 42 132 429 1430 4862 16796

入力例 2

20
0 130171465 825060067 310308502
32807742 472394518 556273189 402133431
18860036 731819479 614014131 516327409
540765157 764797868 805340356 885719657

出力例 2

220800069 663178740 402492745 787371697 340681055 764687638 248275291 239071271 579317784 142439206 202142764 449124008 17082226 208225793 292943419 63532736 780653882 855023292 155627784 988995756