2019 Multi-University Training Contest 1 1012 Sequence

发表于 | 更新于 | 分类于 ， | 阅读次数：
本文字数： 5.8k | 阅读时长 ≈ 5 分钟

2019 Multi-University Training Contest 1
HDU 6589 Sequence
果然不看大佬博客不会写题。顺手把板子也扒了。
题解: x 只有 1 2 3三种情况。直接观察前缀.
可以发现当 x=1 的时候 $c_1$表示 1出现的个数

预理出 $C[j]=C_{c_1-1+j}^{j}$上式就变成了

是不是绝对上述这个式子非常眼熟，就是卷积中的一项。。。
发现了这个，就是一个组合数加个NTT
当x=2的时候就把数组分奇数项和偶数项求一个上式
当x=3的时候就求3个
实际上，只要改一下$c[j]$
把按照x=1的求一下x=2
c[j]=j%2==0>c[j/2]:0
x=3``c[j]=j%3==0?c[j/3]:0

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include "bits/stdc++.h"

using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
#define VNAME(value) (#value)
#define bug printf("*********\n");
#define debug(x) cout<<"["<<VNAME(x)<<" = "<<x<<"]"<<endl;
#define mid (l + r) / 2
#define chl 2 * k + 1
#define chr 2 * k + 2
#define lson l, mid, chl
#define rson mid + 1, r, chr
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a));


const LL mod = (LL) 998244353;
const int maxn = (int) 1e6 + 5;
const int INF = 0x7fffffff;
const LL inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1);
#ifndef ONLINE_JUDGE
clock_t prostart = clock();
#endif

void f() {
#ifndef ONLINE_JUDGE
    freopen("../data.in", "r", stdin);
#endif
}

int t;
int n, m;
LL a[maxn];
int c[maxn];
LL b[maxn];

const int Comb_Maxn = 1e6 + 10;

LL Fac_inv[Comb_Maxn];
LL Fac[Comb_Maxn];

inline void Comb_init() {
    Fac_inv[0] = Fac[0] = 1;
    Fac_inv[1] = 1;
    for (int i = 1; i < Comb_Maxn; i++)
        Fac[i] = Fac[i - 1] * (LL) i % mod;
    for (int i = 2; i < Comb_Maxn; i++)
        Fac_inv[i] = (LL) (mod - mod / i) * Fac_inv[mod % i] % mod;
    for (int i = 1; i < Comb_Maxn; i++)
        Fac_inv[i] = Fac_inv[i - 1] * Fac_inv[i] % mod;
}

LL Comb(int n, int m) {
    if (m > n || m < 0 || n < 0)return 0;
    return Fac[n] * Fac_inv[m] % mod * Fac_inv[n - m] % mod;
}

typedef LL ll;
const int N = maxn;


struct NumberTheoreticTransform {
    int pow2(int x) {
        int res = 1;
        while (res < x)
            res <<= 1;
        return res;
    }


    inline LL pow_mod(ll x, int n) {
        ll res;
        for (res = 1; n; n >>= 1, x = x * x % mod)
            if (n & 1)
                res = res * x % mod;
        return res;
    }

    inline int add_mod(int x, int y) {
        x += y;
        return x >= mod ? x - mod : x;
    }

    inline int sub_mod(int x, int y) {
        x -= y;
        return x < 0 ? x + mod : x;
    }

    void NTT(LL a[], int n, int op) {
        for (int i = 1, j = n >> 1; i < n - 1; ++i) {
            if (i < j)
                swap(a[i], a[j]);
            int k = n >> 1;
            while (k <= j) {
                j -= k;
                k >>= 1;
            }
            j += k;
        }
        for (int len = 2; len <= n; len <<= 1) {
            LL g = pow_mod(3, (mod - 1) / len);
            for (int i = 0; i < n; i += len) {
                LL w = 1;
                for (int j = i; j < i + (len >> 1); ++j) {
                    LL u = a[j], t = 1ll * a[j + (len >> 1)] * w % mod;
                    a[j] = (u + t) % mod, a[j + (len >> 1)] = (u - t + mod) % mod;
                    w = 1ll * w * g % mod;
                }
            }
        }
        if (op == -1) {
            reverse(a + 1, a + n);
            LL inv = pow_mod(n, mod - 2);
            for (int i = 0; i < n; ++i)
                a[i] = 1ll * a[i] * inv % mod;
        }
    }

    void mul(LL A[], LL B[], int Asize, int Bsize) {
        int n = pow2(Asize + Bsize - 1);
        for (int i = Asize; i < n; ++i)
            A[i] = 0;
        for (int i = Bsize; i < n; ++i)
            B[i] = 0;
        NTT(A, n, 1);
        NTT(B, n, 1);
        for (int i = 0; i < n; ++i) {
            A[i] = 1ll * A[i] * B[i] % mod;
            B[i] = 0;
        }
        NTT(A, n, -1);
        return;
    }
} ntt;


template<typename T>
void read(T &w) {  //读入
    char c;
    while (!isdigit(c = getchar()));
    w = c & 15;
    while (isdigit(c = getchar()))w = w * 10 + (c & 15);
}

int main() {
    f();
    read(t);
    Comb_init();
    while (t--) {
        read(n);
        read(m);
        for (int i = 0; i < n; i++) {
            read(a[i]);
        }
        c[0] = c[1] = c[2] = c[3] = 0;
        while (m--) {
            int x;
            scanf("%d", &x);
            c[x]++;
        }
        if (c[1] > 0) {
            for (int i = 0; i < n; i++) {
                b[i] = Comb(c[1] + i - 1, i);
            }
            ntt.mul(a, b, n, n);
        }
        if (c[2] > 0) {
            for (int i = 0; i < n; i += 2) {
                b[i] += Comb(c[2] + i / 2 - 1, i / 2);
                b[i + 1] = 0;
            }
            ntt.mul(a, b, n, n);
        }
        if (c[3] > 0) {
            for (int i = 0; i < n; i += 3) {
                b[i] = Comb(c[3] + i / 3 - 1, i / 3);
            }
            ntt.mul(a, b, n, n);
        }
        LL ans = 0;
        for (int i = 0; i < n; i++) {
            ans ^= (i + 1LL) * a[i];
        }
        printf("%lld\n", ans);

    }
#ifndef ONLINE_JUDGE
    cout << "运行时间:" << 1.0 * (clock() - prostart) / CLOCKS_PER_SEC << "s\n";
#endif // ONLIN_JUDGE
    return 0;
}