102766: [AtCoder]ABC276 G - Count Sequences
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Score : $600$ points
Problem Statement
Find the number of sequences of integers with $N$ terms, $A=(a_1,a_2,\ldots,a_N)$, that satisfy the following conditions, modulo $998244353$.
- $0 \leq a_1 \leq a_2 \leq \ldots \leq a_N \leq M$.
- For each $i=1,2,\ldots,N-1$, the remainder when $a_i$ is divided by $3$ is different from the remainder when $a_{i+1}$ is divided by $3$.
Constraints
- $2 \leq N \leq 10^7$
- $1 \leq M \leq 10^7$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$
Output
Print the answer.
Sample Input 1
3 4
Sample Output 1
8
Here are the eight sequences that satisfy the conditions.
- $(0,1,2)$
- $(0,1,3)$
- $(0,2,3)$
- $(0,2,4)$
- $(1,2,3)$
- $(1,2,4)$
- $(1,3,4)$
- $(2,3,4)$
Sample Input 2
276 10000000
Sample Output 2
909213205
Be sure to find the count modulo $998244353$.
Input
题意翻译
计算有多少个 $N$ 个元素的数组 $A = (a_1,...,a_N)$ 满足以下条件，并且将结果对 $998244353$ 取模。 - $0 \le a_1 \le a_2 \le...\le a_N \le M$ - 对于每一个 $i = 1,2,..,N-1$，满足 $a_i$ 和 $a_{i+1}$ 对 $3$ 取模的余数不同。 $2 \le N \le 10^7,1 \le M \le 10^7.$Output
得分：600分
问题描述
求满足以下条件的整数序列A=(a1,a2,…,aN)的数量，模998244353。
- 0≤a1≤a2≤…≤aN≤M。
- 对于每个i=1,2,…,N-1，ai除以3的余数与ai+1除以3的余数不同。
限制条件
- 2≤N≤107
- 1≤M≤107
- 输入中的所有值都是整数。
输入
输入是通过标准输入给出的，格式如下：
$N$ $M$
输出
输出答案。
样例输入1
3 4
样例输出1
8
以下是满足条件的八个序列。
- (0,1,2)
- (0,1,3)
- (0,2,3)
- (0,2,4)
- (1,2,3)
- (1,2,4)
- (1,3,4)
- (2,3,4)
样例输入2
276 10000000
样例输出2
909213205
确保找到的数量模998244353。