Lucky Tickets
题意翻译
一个 $n$ 位数,每位可以是给出的 $k$ 个数码中的一个数,可以有前导 $0$,输出前 $\frac n 2$ 位之和与后 $\frac n 2$ 位之和相等的方案数,保证 $n$ 是偶数。
输入的第一行是两个整数 $n,k$,接下来的一行有 $k$ 个数 $d_1,d_2,\cdots,d_k(0\leq d_i\leq 9)$。
输出一个数,为方案数模 $998244353$ 的值。
题目描述
All bus tickets in Berland have their numbers. A number consists of $ n $ digits ( $ n $ is even). Only $ k $ decimal digits $ d_1, d_2, \dots, d_k $ can be used to form ticket numbers. If $ 0 $ is among these digits, then numbers may have leading zeroes. For example, if $ n = 4 $ and only digits $ 0 $ and $ 4 $ can be used, then $ 0000 $ , $ 4004 $ , $ 4440 $ are valid ticket numbers, and $ 0002 $ , $ 00 $ , $ 44443 $ are not.
A ticket is lucky if the sum of first $ n / 2 $ digits is equal to the sum of remaining $ n / 2 $ digits.
Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo $ 998244353 $ .
输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ $ (2 \le n \le 2 \cdot 10^5, 1 \le k \le 10) $ — the number of digits in each ticket number, and the number of different decimal digits that may be used. $ n $ is even.
The second line contains a sequence of pairwise distinct integers $ d_1, d_2, \dots, d_k $ $ (0 \le d_i \le 9) $ — the digits that may be used in ticket numbers. The digits are given in arbitrary order.
输出格式
Print the number of lucky ticket numbers, taken modulo $ 998244353 $ .
输入输出样例
输入样例 #1
4 2
1 8
输出样例 #1
6
输入样例 #2
20 1
6
输出样例 #2
1
输入样例 #3
10 5
6 1 4 0 3
输出样例 #3
569725
输入样例 #4
1000 7
5 4 0 1 8 3 2
输出样例 #4
460571165
说明
In the first example there are $ 6 $ lucky ticket numbers: $ 1111 $ , $ 1818 $ , $ 1881 $ , $ 8118 $ , $ 8181 $ and $ 8888 $ .
There is only one ticket number in the second example, it consists of $ 20 $ digits $ 6 $ . This ticket number is lucky, so the answer is $ 1 $ .