第三个比赛原题？

题目描述

        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
#include <bits/stdc++.h>

#pragma GCC optimize(3)

#define MOD 998244353
#define G 3
#define N 1000005
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;
}