Score : $600$ points

问题描述

给定正整数 $N$、$K$ 以及一个包含 $K$ 个整数的序列 $(A_1, A_2, \ldots, A_K)$。

高桥和青木将玩一场石头游戏。最初，有一些堆石头，每堆包含一个或多个石头。玩家轮流执行以下操作，由高桥先手。

• 选择一个仍有剩余石头的堆。从该堆中移除 $1$ 到 $X$（包括）之间的任意数量的石头，其中 $X$ 是该堆剩余的石头数量。

最先无法执行操作的玩家输掉游戏。

现在，考虑满足以下条件的初始石头排列：

• 堆的数量 $M$ 满足 $1\leq M\leq N$。
• 每堆石头的数量为 $A_1, A_2, \ldots, A_K$ 中的一个。

假设堆是有序排列的，共有 $K+K^2+\cdots +K^N$ 种这样的初始石头排列。在这些排列中，假设两位玩家都采取最优策略，请计算出高桥能赢得游戏的初始排列数模 $998244353$ 后的结果。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Given are positive integers $N$, $K$, and a sequence of $K$ integers $(A_1, A_2, \ldots, A_K)$.

Takahashi and Aoki will play a game with stones. Initially, there are some heaps of stones, each of which contains one or more stones. The players take turns doing the following operation, with Takahashi going first.

• Choose a heap with one or more stones remaining. Remove any number of stones between $1$ and $X$ (inclusive) from that heap, where $X$ is the number of stones remaining.

The player who first gets unable to do the operation loses.

Now, consider the initial arrangements of stones satisfying the following.

• $1\leq M\leq N$ holds, where $M$ is the number of heaps of stones.
• The number of stones in each heap is one of the following: $A_1, A_2, \ldots, A_K$.

Assuming that the heaps are ordered, there are $K+K^2+\cdots +K^N$ such initial arrangements of stones. Among them, find the number, modulo $998244353$, of arrangements that lead to Takahashi's win, assuming that both players play optimally.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq K < 2^{16}$
• $1 \leq A_i < 2^{16}$
• All $A_i$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $K$

$A_1$ $A_2$ $\ldots$ $A_K$

Output

Print the answer.

Sample Input 1

2 2
1 2

Sample Output 1

4

There are six possible initial arrangements of stones: $(1)$, $(2)$, $(1,1)$, $(1,2)$, $(2,1)$, and $(2,2)$.
Takahashi has a winning strategy for four of them: $(1)$, $(2)$, $(1,2)$, and $(2,1)$, and Aoki has a winning strategy for the other two. Thus, we should print $4$.

Sample Input 2

100 3
3 5 7

Sample Output 2

112184936

Be sure to find the count modulo $998244353$.

update @ 2024/3/10 09:28:42