AT_xmascon23_h.How to Pose Such a Problem

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个正整数 $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$ 。

输入格式

输入以如下格式从标准输入读入：

$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

输出#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

说明/提示

数据范围

$2 \le N \le 250\,000$ 。
$0 \le W_{i,j} < 998244353$ （ $0 \le i,j \le 3$ ）。
$W_{0,0}=0$ 。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页