102127: [AtCoder]ABC212 H - Nim Counting
Description
Score : $600$ points
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$.
Input
题意翻译
### 题目描述 给定两个数 $N,K$,以及一个长度为 $K$ 的整数数组 $(A_i,A_2...A_K)$。 两个人玩 [Nim 游戏](https://www.luogu.com.cn/problem/P2197)。 现在通过以下方式生成一个游戏： > 任意选择一个 $1\le M\le N$，$M$ 表示石子堆数。 > > 对于每一堆，其石子数是 $A$ 中任意一个数。 对于 $\sum_{i=1}^N K^i$ 种游戏，求先手获胜的游戏数，答案对 $998244353$ 取模。 ### 输入格式 第一行两个数 $N,K$。 ### 输出格式 一行一个数，表示答案。 ### 数据范围 - $1\le N\le 2\times 10^5$ - $1\le A_i,K<2^{16}$。 - $A_i$ 两两不同。 ### 样例 $1$ 解释 总共有 $6$ 种可能的游戏 $(1),(2),(1,2),(2,1),(1,1),(2,2)$。 其中先手赢的是 $(1),(2),(1,2),(2,1)$,一共 $4$ 种情况。 $\textsf{\textbf{Translated by @\color{5eb95e}nr0728}}.$Output
分数：$600$分
问题描述
给定正整数$N$，$K$和由$K$个正整数$(A_1, A_2, \ldots, A_K)$组成的序列。
高桥和青木将玩一个石子游戏。最初，有一些石子堆，每个堆都包含一个或多个石子。玩家轮流执行以下操作，由高桥先开始。
- 选择一个还剩下至少一个石子的堆。从该堆中移除$1$到$X$（包括$X$）之间的任意数量的石子，其中$X$是剩余的石子数量。
首先无法执行操作的玩家输掉比赛。
现在，考虑满足以下条件的初始石子堆排列。
- 石子堆的数量$M$满足$1\leq M\leq N$。
- 每个堆的石子数量是以下之一：$A_1, A_2, \ldots, A_K$。
假设堆是有序的，这样的初始石子堆排列有$K+K^2+\cdots +K^N$种。在这些排列中，找出在假设两个玩家都发挥最优的情况下，导致高桥获胜的排列数量，对$998244353$取模。
约束
- $1 \leq N \leq 2\times 10^5$
- $1 \leq K < 2^{16}$
- $1 \leq A_i < 2^{16}$
- 所有$A_i$都是不同的。
- 输入中的所有值都是整数。
输入
输入从标准输入以以下格式给出：
$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$
输出
打印答案。
样例输入 1
2 2 1 2
样例输出 1
4
有六种可能的初始石子堆排列：$(1)$，$(2)$，$(1,1)$，$(1,2)$，$(2,1)$和$(2,2)$。
对于其中的四种排列：$(1)$，$(2)$，$(1,2)$和$(2,1)$，高桥有获胜策略；对于另外两种排列，青木有获胜策略。因此，我们应该打印$4$。
样例输入 2
100 3 3 5 7
样例输出 2
112184936
一定要找到对$998244353$取模后的计数。