← 返回题目列表

AtCoder · fps_24_v

V. 12 个方向

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

分数: 7 点

问题陈述

在 2D 平面坐标上,有一块放置在 (0, 0).
您将执行以下操作 N 次:

  • 选择一个整数 i 这样 0 \leq i \leq 11.
    如果棋子的当前位置是 (x, y),将其移至 (x + \cos(30i)^\circ, y + \sin(30i)^\circ).

计算导致工件返回到的操作序列的数量 (H, W) 之后 N 运算,并输出结果模 998244353.

约束

  • 1 \leq N \leq 2.5 \times 10^5
  • -N \leq H \leq N
  • -N \leq W \leq N
  • N, H, W 是整数

部分分数

该问题有部分评分:

  • 如果您使用以下方法求解所有数据集 (H, W) = (0, 0),您将获得 5 点。

输入

输入由标准输入给出,格式如下:

N H W

输出

打印有效操作序列的数量,模数 998244353.


示例输入 1

2 0 0

示例输出 1

12

对于每个整数 n 这样 0 \leq n \leq 11,如果第一个操作选择 i = n 第二个操作选择 i = (n+6) \bmod 12,满足条件。因此,有 12 有效序列。


示例输入 2

123456 0 0

示例输出 2

352845935

示例输入 3

50 -12 34

示例输出 3

391874286

示例输入 4

234567 89012 -34567

示例输出 4

523418763