All bus tickets in Berland have their numbers. A number consists of n digits (n is even). Only k decimal digits d1,d2,…,dk 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≤n≤2⋅105,1≤k≤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 d1,d2,…,dk
(0≤di≤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
.
4 2
1 8
6
20 1
6
1
10 5
6 1 4 0 3
569725
1000 7
5 4 0 1 8 3 2
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.
题意：给定你K种数可以选，问你有多少排列，使得前半部分的和等于后半部分的和。
思路：我们枚举“和”的大小，令A[i]表示长度为N/2时和为i的方案数，那么答案就是所有的A[i]*A[i];
怎么就Ai呢，就是一个多项式(P0.X0+P1*X1+...*P9*X9)^(N/2)；p是0或者1；
多项式的N次，我们可以用快速幂+FFT来加速，这里要取模，写的NTT。然后就是可以直接一次DFT+快速幂+IDFT。
（之前纠结过为什么可以一次DFT就搞定了，而不是logN次，现在看来是对的，正确性我还需要学习一下。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
#define ll long long
const int G=;
const int maxn=;
const int Mod=;
int mod,n,k,rev[maxn],lim,ilim,s,wn[maxn+];
std::vector<int> v;
inline int pow(int x, int y) {
int ans=;
for(;y;y>>=,x=(ll)x*x%mod)
if(y&) ans=(ll)ans*x%mod;
return ans;
}
inline int& up(int& x, int y) { if ((x+=y)>=mod) x-=mod; return x; }
inline void NTT(int* A, int typ) {
rep(i,,lim-) if (i<rev[i]) swap(A[i], A[rev[i]]);
for (int i=;i<lim;i+=i) {
const int t=lim/i/;
for (int j=;j<lim;j+=i+i) {
for (int k=;k<i; k++) {
int w=typ?wn[t*k]:wn[lim-t*k];
int x=A[k+j],y=(ll)w*A[k+j+i]%mod;
up(A[k+j],y),up(A[k+j+i]=x,mod-y);
}
}
}
if (!typ) rep(i,,lim-) A[i]=(ll)ilim*A[i]%mod;
}
inline void init(int len,int tmod) {
mod=tmod; lim=; s=-;
while(lim<len) lim+=lim,s++; ilim=pow(lim,mod-);
rep(i,,lim-) rev[i]=rev[i>>]>>|(i&)<<s;
int w=pow(G,(mod-)/len);
wn[]=;
rep(i,,lim) wn[i]=(ll)(wn[i-])*w%mod;
}
int A[maxn];
int main() {
scanf("%d%d",&k,&n); k/=;
int x,ans=; rep(i,,n) scanf("%d",&x), A[x]=B[x]=;
init(, );
NTT(A, );
rep(i,,lim-) A[i]=pow(A[i],k);
NTT(A, );
rep(i,,) (ans+=(ll)A[i]*A[i]%Mod)%=Mod;
printf("%d\n",ans);
return ;
}