102566: [AtCoder]ABC256 G - Black and White Stones
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
There is a regular $N$-gon with side length $D$.
Starting from a vertex, we place black or white stones on the circumference at intervals of $1$. As a result, each edge of the $N$-gon will have $(D+1)$ stones on it, for a total of $ND$ stones.
How many ways are there to place stones so that all edges have the same number of white stones on them? Find the count modulo $998244353$.
Constraints
- $3 \leq N \leq 10^{12}$
- $1 \leq D \leq 10^4$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $D$
Output
Print the answer.
Sample Input 1
3 2
Sample Output 1
10
There are $10$ ways, as follows:
Sample Input 2
299792458 3141
Sample Output 2
138897974
Find the count modulo $998244353$.
Input
题意翻译
你现在有一个正 $n$ 边形 , 边长为 $d$。从顶点开始，你每个长度 $1$ 放一个石子，白色或者黑色。换句话说，每条边上有 $d+1$ 个石子，相邻两边公用一个石子。 请问有多少种方案，使得所有边上的白色石子数量相同。对 $998244353$ 取模。 $n \le 10^{12}$，$d\le 10^4$。注意 $n$ 的范围。Output
得分：$600$分
问题描述
有一个边长为$D$的正$N$边形。
从一个顶点开始，每隔$1$个单位在圆周上放置黑色或白色棋子。这样，$N$边形的每条边将有$(D+1)$个棋子，总共$ND$个棋子。
有多少种放置棋子的方法，使得所有边上的白色棋子数量相同？取答案模$998244353$。
限制条件
- $3 \leq N \leq 10^{12}$
- $1 \leq D \leq 10^4$
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出：
$N$ $D$
输出
打印答案。
样例输入1
3 2
样例输出1
10
有$10$种方法，如下所示：
样例输入2
299792458 3141
样例输出2
138897974
取答案模$998244353$。