[CF1096G]Lucky Tickets
/ / 阅读耗时 6 分钟 第三个比赛原题?
题目描述
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 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 $\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.
输入输出格式
输入格式
The first line contains two integers $n$ and$k$ $(2≤n≤2⋅10^5,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 $d_1,d_2,…,d_k (0≤d_i≤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.
输入输出样例
Sample input1
4 2
1 8
Sample output1
6
Sample input2
20 1
6
Sample output2
1
Sample input3
10 5
6 1 4 0 3
Sample output3
569725
Sample input4
1000 7
5 4 0 1 8 3 2
Sample output4
460571165
题解
生成函数。构造一个多项式如下:
$a_i$在$i$被选入时为1,否则为0。对这个多项式求$\frac {n} {2}$次幂,每一项的系数就是它的方案数,答案就是这些系数的平方和。
常数可能过大,导致$exp$与$ln$的快速幂T了,换倍增快速幂就能AC。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
int tr[N << 2];
struct Pol {//多项式类
int l, op[N << 2] = {0};//l最高项指数
} pol, tmp, ans;
int n;
int qPow(int a, int b) {
int ans = 1, x = a;
while (b) {
if (b & 1)ans = 1ll * ans * x % MOD;
x = 1ll * x * x % MOD, b >>= 1;
}
return ans;
}
void NTT(int l, int *c, int type) {
for (register int i = 0; i < l; i++)if (i < tr[i])swap(c[i], c[tr[i]]);
for (register int mid = 1; mid < l; mid <<= 1) {
register int wn = qPow(G, (MOD - 1) / (mid << 1));
if (type == -1)wn = qPow(wn, MOD - 2);
for (register int len = mid << 1, j = 0; j < l; j += len) {
register int w = 1;
for (register int k = 0; k < mid; k++, w = 1ll * w * wn % MOD) {
register int x = c[j + k], y = 1ll * w * c[j + mid + k] % MOD;
c[j + k] = ((x + y) % MOD + MOD) % MOD, c[j + mid + k] = ((x - y) % MOD + MOD) % MOD;
}
}
}
}
inline void multiple(Pol *ans, Pol *a, Pol *b) {//将a与b相乘并计入ans
int l = 1, le = 0;
while (l <= a->l + b->l)l <<= 1, ++le;
for (register int i = 0; i < l; i++) {
tr[i] = (tr[i >> 1] >> 1) | ((i & 1) << (le - 1));
if (i > a->l)a->op[i] = 0;
if (i > b->l)b->op[i] = 0;
}
NTT(l, a->op, 1), NTT(l, b->op, 1);
for (register int i = 0; i < l; i++)a->op[i] = 1ll * a->op[i] * b->op[i] % MOD;
NTT(l, a->op, -1), l = qPow(l, MOD - 2), ans->l = a->l + b->l;
for (register int i = 0; i <= ans->l; i++)ans->op[i] = 1ll * a->op[i] * l % MOD;
}
inline int read() {
char e = getchar();
int s = 0;
while (e < '-')e = getchar();
while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
return s;
}
vector<int> vvp;
int main() {
int n = read() >> 1, k = read();
pol.l = 9, ans.op[0] = 1, ans.l = 0;
for (register int i = 1; i <= k; i++)vvp.push_back(read());
for (register int i = 0; i < vvp.size(); i++)pol.op[vvp[i]] = 1;
while (n) {//倍增快速幂
if (n & 1) {
tmp.l = pol.l;
for (int i = 0; i <= pol.l; i++)tmp.op[i] = pol.op[i];
multiple(&ans, &tmp, &ans);
}
for (int i = 0; i <= pol.l; i++)tmp.op[i] = pol.op[i];
tmp.l = pol.l, multiple(&pol, &tmp, &pol);
n >>= 1;
}
long long sans = 0;
for (register int i = 0; i <= ans.l; i++)sans = (sans + 1ll * ans.op[i] * ans.op[i] % MOD) % MOD;
cout << sans;
return 0;
}