/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 7 点
問題文
2 次元座標上の (0, 0) に駒が置かれています。あなたは次の操作を N 回行います。
- 0 \leq i \leq 11 を満たす整数 i を選ぶ。駒が今置かれている座標を (x, y) として、駒を (x + \cos(30i)^\circ, y + \sin(30i)^\circ) に移動させる。
N 回の操作後に (H, W) に駒が置かれた状態になるような操作列の個数を 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
0 \leq n \leq 11 を満たす整数 n 全てについて、1 回目の操作で i = n を選んだ後に 2 回目の操作で i = (n+6) \bmod {12} を選べば条件を満たします。よって答えは 12 通りです。
入力例 2
123456 0 0
出力例 2
352845935
入力例 3
50 -12 34
出力例 3
391874286
入力例 4
234567 89012 -34567
出力例 4
523418763
Score: 7 points
Problem Statement
On a 2D coordinate plane, there is a piece placed at (0, 0).
You will perform the following operation N times:
- Choose an integer i such that 0 \leq i \leq 11.
If the current position of the piece is (x, y), move it to (x + \cos(30i)^\circ, y + \sin(30i)^\circ).
Count the number of operation sequences that result in the piece being back at (H, W) after N operations, and output the result modulo 998244353.
Constraints
- 1 \leq N \leq 2.5 \times 10^5
- -N \leq H \leq N
- -N \leq W \leq N
- N, H, W are integers
Partial Score
This problem has partial scoring:
- If you solve all datasets with (H, W) = (0, 0), you will earn 5 points.
Input
The input is given from standard input in the following format:
N H W
Output
Print the number of valid operation sequences, modulo 998244353.
Sample Input 1
2 0 0
Sample Output 1
12
For every integer n such that 0 \leq n \leq 11, if the first operation chooses i = n and the second operation chooses i = (n+6) \bmod 12, the condition is satisfied. Thus, there are 12 valid sequences.
Sample Input 2
123456 0 0
Sample Output 2
352845935
Sample Input 3
50 -12 34
Sample Output 3
391874286
Sample Input 4
234567 89012 -34567
Sample Output 4
523418763