No.2264 Gear Coloring
タグ : / 解いたユーザー数 43
作問者 :
sotanishy
/ テスター :
Problem Statement
There are $N$ gears, and the $i$-th gear has $A_i$ teeth. For $i=1,2,\dots,N-1$, gear $i$ and gear $i+1$ are meshed: when gear $i$ rotates by 1 tooth, gear $i+1$ also rotates by 1 tooth along with it.
You will now paint each tooth of each gear using $M$ colors. Two colorings are considered the same if they coincide after a rotation. How many colorings are there? Find the count modulo $998244353$.
Input
$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$
- $2 \leq N \leq 1000$
- $1 \leq M$$ \le 10^9$ (Updated 2026/05/29)
- $3 \leq A_i \lt 998244353$
- $\mathrm{lcm}(A_1,A_2,\dots,A_N) \lt 998244353$
- All inputs are integers.
Output
Output the answer modulo $998244353$. Print a newline at the end.
Sample
Sample 1
Input
2 2 3 3
Output
24
Sample 2
Input
2 3 3 4
Output
264
Sample 3
Input
3 4 3 5 7
Output
11701248
Sample 4
Input
4 100 10 1000 100000 100000000
Output
827082837
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。