/ 
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
すぬけ君は何も書かれていない黒板を見つけました。
すぬけ君が N 回黒板に操作をします。 i 回目の操作では黒板に 1 以上 a_i 以下の整数を選んで書き込みます。
黒板に N 個の整数が書き込まれたあと、先手太郎君と後手次郎君がこの黒板を使ったゲームで遊ぶ予定です。 ゲームでは先手太郎君から始めて、交互に以下の操作を行います。
- 黒板に書かれている最大の整数を X とする。
- X=0 のとき、手番のプレイヤーの勝ちとしてゲームを終了する。
- 1 以上 X 以下の整数を選ぶ(これを m とする)。
- 黒板に書かれている N 個の整数をそれぞれ m で割ったあまりに置き換える。
すぬけ君の書き込み方は \prod_{i=1}^{N}a_i 通りありえますが、そのうち 2 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を 998244353 で割ったあまりを求めてください。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 200
- 1 \leq a_i \leq 200
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \cdots a_N
出力
2 人が最適に行動したときに勝つのが先手太郎君であるような書き込み方の個数を 998244353 で割ったあまりを出力せよ。
入力例 1
1 3
出力例 1
1
- 先手太郎君が勝つのはすぬけ君が 3 を書き込んだ場合に限られます。
- それ以外の場合、先手太郎君は黒板に書かれている整数が 0 になるように手を打つしかありません。
入力例 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
- 998244353 で割ったあまりを求めるのを忘れずに。
Score : 900 points
Problem Statement
Snuke found a blackboard with nothing written on it.
He will do N operations on this blackboard. In the i-th operation, he chooses an integer between 1 and a_i (inclusive) and writes it on the blackboard.
After N integers are written on the blackboard, Taro The First and Jiro The Second will play a game using it. In the game, the two alternately do the operation below, with Taro The First going first.
- Let X be the largest integer written on the blackboard.
- If X=0, the current player wins and the game ends.
- Choose an integer m between 1 and X (inclusive).
- Replace each of the N integers written on the blackboard with its remainder when divided by m.
There are \prod_{i=1}^{N}a_i ways for Snuke to write numbers on the blackboard. Find the number of ways among them that will result in Taro The First's win if both players play optimally, modulo 998244353.
Constraints
- All values in input are integers.
- 1 \leq N \leq 200
- 1 \leq a_i \leq 200
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \cdots a_N
Output
Print the number of ways to write integers that will result in Taro The First's win if both players play optimally, modulo 998244353.
Sample Input 1
1 3
Sample Output 1
1
- Taro The First will win only if Snuke writes 3.
- Otherwise, Taro The First can only play a move that makes the integer on the blackboard 0.
Sample Input 2
2 5 10
Sample Output 2
47
Sample Input 3
20 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200
Sample Output 3
273710435
- Be sure to find the count modulo 998244353.