QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB
[0]

# 5194. 游戏

Statistics

题目描述

小 C 和小 W 两个人打算玩一局双人博弈游戏。

现在小 C 手里有 n 颗相同的石子,小 W 打算把它们分为有顺序的 m 堆,其中第 i 堆石子的数量不能超过 ai,但允许为 0

随后,由小 C 先手,两人轮流进行操作,每次可以选择一堆非空的石子并拿走其中若干个(至少 1 个),无法操作者输。

作为算法竞赛界的老司机,小 C 和小 W 早已对各种游戏的策略摸得门儿清,于是这次他们打算玩点不一样的:他们想要知道,有多少种分石子的方法能使得小 C 有必胜策略。

输入格式

第一行:2 个正整数 n,m (n1018,m10)

第二行:m 个非负整数 ai (ai1018)

输出格式

一个非负整数,表示方案数对 998244353 取模的结果。

样例数据

样例 1 输入

6 3
2 3 4

样例 1 输出

4

样例 1 解释

以下 4 种方案是符合题意的:(0,2,4)(1,1,4)(2,0,4)(2,2,2)