Codeforces Round 57- Bài 7

Bài 7: 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,...,d_k$ can be used to form ticket numbers. If $0$ is among these digits, then numbers may have leading zeroes. For eample, 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 $\frac{n}{2}$ digits is equal to the sum of remaining $\frac{n}{2}$ digits.
Calculate the number of different lucky tickets in Berland. Since the answer may be big, print it modulo $998244353$.
Input
The first line contains two integers $n$ and $k(2\le n\le 2.10^5,1\le k\le 10)$- the number of digits in each ticket number, and the number of 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,...,d_k(0\le d_i\le 9)$- the digits that may be used in ticket numbers. The digits are given in arbitrary order.
Output
Print the number of lucky ticket numbers, taken modulo $998244353$.

Examples

input

Copy

4 2
1 8

output

Copy

6

input

Copy

20 1
6

output

Copy

1

input

Copy

10 5
6 1 4 0 3

output

Copy

569725

input

Copy

1000 7
5 4 0 1 8 3 2

output

Copy

460571165

 Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn = 1000111;
int n, k;
bool a[11];
ll b[maxn], inv[maxn];
int main()
{
 inv[1] = 1;
 for (int i=2; i<=maxn; i++) inv[i] = mod-(mod/i)*inv[mod%i]%mod;
 cin>>n>>k;
 n /= 2;
 int mn = 10;
 vector<int> v;
 for (int i=0; i<k; i++)
 {
  int x;
  cin>>x;
  v.push_back(x);
  mn = min(mn, x);
 }
 for (auto x:v) a[x-mn] = 1;
 b[0] = 1;
 ll ans = 0;
 for (int i=0; i<=n*10; i++)
 {
  ll sum = 0;
  for (int j=1; j<10&&j<=i; j++) sum -= b[i-j+1]*(i-j+1)%mod*a[j];
  for (int j=0; j<10&&j<=i; j++) sum += b[i-j]*a[j+1]*(j+1)%mod*n%mod;
  b[i+1] = sum%mod*inv[i+1]%mod;
  ans = (ans+b[i]*b[i])%mod;
 }
 cout<<(ans+mod)%mod<<endl;
 return 0;
}