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
#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; }
Không có nhận xét nào:
Đăng nhận xét