[ARC134E] Modulo Nim
题意翻译
Snuke 见到了一个空的黑板、
Snuke 要在黑板上进行 $N$ 次操作,第 $i$ 次操作选择一个 $[1,a_i]$ 中的正整数,将之写在黑板上。
写完 $N$ 个数之后,先手太郎和后手次郎要在黑板上玩游戏。先手太郎先开始,两人轮流进行以下操作:
+ 考虑当前黑板上的最大数 $X$。
+ 若 $X=0$,则当前操作的玩家**获胜**,游戏结束。
+ 选择一个 $[1,X]$ 中的正整数 $m$。
+ 将 $N$ 个数全部对 $m$ 取模。
对于 Snuke 所有可能的 $\prod_{i=1}^Na_i$ 种写数字的方法,若两人都采取最优策略,请求出先手太郎能获胜的情况数取模 $998244353$ 的结果。
题目描述
[problemUrl]: https://atcoder.jp/contests/arc134/tasks/arc134_e
すぬけ君は何も書かれていない黒板を見つけました。
すぬけ君が $ N $ 回黒板に操作をします。 $ i $ 回目の操作では黒板に $ 1 $ 以上 $ a_i $ 以下の整数を選んで書き込みます。
黒板に $ N $ 個の整数が書き込まれたあと、先手太郎君と後手次郎君がこの黒板を使ったゲームで遊ぶ予定です。 ゲームでは先手太郎君から始めて、交互に以下の操作を行います。
- 黒板に書かれている最大の整数を $ X $ とする。
- $ X=0 $ のとき、手番のプレイヤーの**勝ち**としてゲームを終了する。
- $ 1 $ 以上 $ X $ 以下の整数を選ぶ(これを $ m $ とする)。
- 黒板に書かれている $ N $ 個の整数をそれぞれ $ m $ で割ったあまりに置き換える。
すぬけ君の書き込み方は $ \prod_{i=1}^{N}a_i $ 通りありえますが、そのうち $ 2 $ 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を $ 998244353 $ で割ったあまりを求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ \cdots $ $ a_N $
输出格式
$ 2 $ 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を $ 998244353 $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
1
3
输出样例 #1
1
输入样例 #2
2
5 10
输出样例 #2
47
输入样例 #3
20
200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200
输出样例 #3
273710435
说明
### 制約
- 与えられる入力は全て整数
- $ 1\ \leq\ N\ \leq\ 200 $
- $ 1\ \leq\ a_i\ \leq\ 200 $
### Sample Explanation 1
\- 先手太郎君が勝つのはすぬけ君が $ 3 $ を書き込んだ場合に限られます。 - それ以外の場合、先手太郎君は黒板に書かれている整数が $ 0 $ になるように手を打つしかありません。
### Sample Explanation 3
\- $ 998244353 $ で割ったあまりを求めるのを忘れずに。