2022 寒假测试 8 解析

发表于 更新于 分类于 本文字数： 2879 阅读时长 ≈ 7 分钟

2022 年寒假第 8 次测试解析。

T1 「JOISC 2016 Day 2」女装大佬

原题为 JOISC 2016 Day2 T3 「トイレ」。

题面

题面

题目描述

题目译自 JOISC 2016 Day2 T3 「トイレ」
题面魔改原因：原题是男选手太多所以要借用女厕所 译者表示无法接受
IOI 的队服有两种，一种男装，一种是女装。然而很遗憾，所有参赛队伍中并没有女生，只有女装大佬。现在 IOI 设置了两个发放点，一个点只发放男装，另一个点只发放女装。
现在，所有队伍总共 2N 个参赛队员，他们排成一列来领取队服，领取队服的规则如下：

  1. 当前队首是女装大佬，如果领取女装的地方是空的，那么他就会领取女装，否则如果领取男装的地方是空的，他会去领取男装；
  2. 当前队首是正常男生，如果领取男装的地方是空的，那么他会领取男装，否则如果女装位空着，他就发挥绅♂士精神，给身后的最前面的女装大佬让位，让他先领取女装。
    已知任意一个人领取队服都需要一分钟的时间，现在你需要重排所有人的顺序，使他们在 N 分钟内领完队服 。
    定义一个人的 Dark 值为：在重排队伍之前在他后面，且重排队伍之后在他前面的人的数量。
    你现在需要找出重排后整个队伍最大的 Dark 值至少为多少。

输入格式

第一行为一个数 N ，为领完队服的时限，同时 2N 代表着总领队服人数，需要注意的是，这不意味着正常男生和女装大佬刚好各占 N 个；
第二行为一个数 M，指队伍共有 M 种；
之后的 M 行，第 i 行包括一个字符串和一个数字，描述该队伍的组成，其中 M 表示正常男生，F 表示女装大佬，之后的一个数字，表示该字符串连续出现了几次。所有字符串长度乘上出现次数的和等于 2N。

输出格式

一个数，表示重排后最大 Dark 值的最小值，如果在 N 分钟内不能完成领取队服的任务，输出 −1。

思路

（这里的说法是基于原题 “トイレ” 的背景 —— 撤硕分配来说的）

首先我们需要判断哪个序列是一个可行的方案。

我们虽然可以从头开始模拟，但是这样需要耗费的时间实在是太多了。
因此，我们考虑从最后一分钟倒推。

既然我们有两个撤硕，总共 2N 个人，需要在 N 分钟内解决问题，那么必须是每一分钟都有两个人在上厕所。

那么我们看一下最后一分钟。
如果最后一分钟在队列里面等待的是两个男生，那么他们已经可以商量谁去女厕所了。
所以我们可以猜想，男的必须尽量靠前。

我们尝试将每一个 F 当做 −1，M 当做 1，基于此统计其后缀和。
我们需要确保所有人加起来不大于 0，即最多有 N 个男生。
我们还需要确保每一段后缀和都不大于 1。自己用手推算一下的话，那么我们可以轻易发现，一旦有后缀和超过 1 的情况的话，那么最后肯定有两个（或更多）男生需要决定谁进女厕所。

我们可以选择二分让队尾多少个男生去往队头，也可以统计整个序列中后缀和最大值之后再 + 1。

代码

100 分代码：

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
#include<bits/stdc++.h>
#define ll long long
const int N = 100010;
using namespace std;
ll n, m;
ll chq, ans, temp;
ll t[N], p[N], maxp[N];
char s[N << 1];
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        cin >> s + 1 >> t[i];
        int lens = strlen(s + 1);
        for(int j = lens; j >= 1; j--)
        {
            p[i] += (s[j] == 'F' ? -1 : 1);
            maxp[i] = max(p[i], maxp[i]);
        }
        chq += p[i] * t[i];
    }
    if(chq > 0)
    {
        puts("-1");
        return 0;
    }
    ans = 1;
    for(int i = m; i >= 1; i--)
    {
        if(p[i] > 0)
        {
            ans = max(ans, temp + (t[i] - 1) * p[i] + maxp[i]);
        }
        else
        {
            ans = max(ans, temp + maxp[i]);
        }
        temp += p[i] * t[i];
    }
    printf("%lld", ans - 1);
    return 0;
}

一发 36 分的 Java8 代码：

Java8

 
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
//import java.util.Arrays;
import java.util.Scanner;

public class S2544 {
    static int N=100010;
    static long[] t=new long[N];
    static long[] p=new long[N];
    static long[] maxp=new long[N];
    static long chq=0,ans=0,temp=0;
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        long n=scan.nextInt();
        int m=scan.nextInt();
        for(int i=1;i<=m;i++){
            String inp=scan.next();
            t[i]=scan.nextInt();
            int len=inp.length();
            char[] s=inp.toCharArray();
            for(int j=len-1;j>=0;j--){
                p[i]+=(s[j]=='F'?-1:1);
                maxp[i]=max(p[i],maxp[i]);
            }
            chq+=p[i]*t[i];
        }
        if(chq>0){
            System.out.println("-1");
        }else{
            ans=1;
            for(int i=m;i>=1;i--){
                if(p[i]>0){
                    ans=max(ans,temp+(t[i]-1)*p[i]+maxp[i]);
                }else{
                    ans=max(ans,temp+maxp[i]);
                }
                temp+=p[i]*t[i];
            }
            System.out.println(ans-1);
            scan.close();
        }
    }

    private static long max(long a,long b){
        if(a>=b){
            return a;
        }else{
            return b;
        }
    }
}

T2 【常中 20180812T3】 test

题面

题面

题目背景

Tom 在学写动态树，但是做题时过了样例，提交 RE。Tom 抓住 Jerry 要他写个暴力来对拍。Jerry 觉得这任务太简单了，就让你来完成一下。

题目描述

有一棵 n 个节点的树，初始时根节点为 1。现在要支持如下操作 ——

  1. 将某节点设置为根；
  2. 改变某节点权值；
  3. 询问以某节点为根的子树内节点权值之和；
  4. 询问以某两点为端点的链上的节点权值之和。

输入格式

第一行两个正整数 n 和 q ，表示树的节点数和操作个数。
接着 n−1 行每行两个整数 u 和 v ，表示有连接 u 和 v 的一条边。
随后一行 n 个正整数，表示每个点的初始权值。
之后 q 行每行格式如下：
首先一个范围为 [1,4] 的正整数，表示该操作类型。
对于 1 操作，之后一个正整数 x ，表示将 x 节点设置为根。
对于 2 操作，之后两个正整数 x 和 v ，表示将 x 节点的权值改为 v 。
对于 3 操作，之后一个正整数 x ，表示询问以 x 为根的子树内节点权值之和。
对于 4 操作，之后两个正整数 x 和 y ，表示询问以 x 和 y 为端点的链上的节点权值之和。

输出格式

对于每个操作 3 和操作 4，输出一行一个整数表示询问的答案。

思路

根据题目所给出的要求，我们可以使用 LCT 做这道题。

但是 LCT 太难了我不会啊 QwQ

所以我们考虑退而求其次，使用换根树剖来做。
实测可行。

换根操作只会影响作用于一个节点子树上的操作，比如子树加，子树求和等等。

巧了，这里就有一个。

那就有点头疼。

我们根据要需要操作的节点 x 和现根节点 rt 的关系来考虑分三种情况：

  1. x==rt
    这种情况明显很简单 —— 就是整棵树。

  2. lca(x,rt)！=x
    这样我们可以知道现在的根 rt 没有在 x 的子树里，此时 x 的子树与根为 1 时的子树无异，可以直接操作。

  3. lca(x,rt)==x
    这时候我们发现 rt 在 x 的子树里面。
    此时，x 的子树就会发生很大的改变。原先 x 的子树包含 rt 的那个儿子现在成为了 x 的父亲，而其他儿子不变。原先为 x 父亲的节点成为了 x 的其中一个儿子，原先除其子树以外的节点都成为了其子树。
    我们称这个子树包含 rt 的儿子为 v 。
    现在 x 的子树是 [1,idv)∪(idv+szv−1,n] 这两段连续的区间。
    我们可以考虑对这两段区间分别操作，也可以选择对整棵树操作以后在减去中间的那一块 er。

代码

100 分代码：

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
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 100010, M = N << 1;
int n, m;
int w[N], h[N], e[M], ne[M], idx;
int id[N], nw[N], cnt;
int dep[N], sz[N], top[N], fa[N], son[N];
struct SegTree
{
    int l, r;
    ll sum;
}tr[N << 3];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs1(int p, int vater, int depth)
{
    dep[p] = depth, fa[p] = vater, sz[p] = 1;
    for(int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == vater)continue;
        dfs1(j, p, depth + 1);
        sz[p] += sz[j];
        if(sz[son[p]] < sz[j])son[p] = j;
    }
}
void dfs2(int p, int t)
{
    id[p] = ++cnt, nw[cnt] = w[p], top[p] = t;
    if(!son[p])return;
    dfs2(son[p], t);
    for(int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa[p] || j == son[p])continue;
        dfs2(j, j);
    }
}
void pushup(int p)
{
    tr[p].sum = tr[p << 1].sum + tr[p << 1 | 1].sum;
}
void build(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    if(l == r)
    {
        tr[p].sum = nw[r];
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pushup(p);
    return;
}
void segchg(int p, int ed, ll k)
{
    if((tr[p].l == ed) && (tr[p].r == ed))
    {
        tr[p].sum = k;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(ed <= mid)segchg(p << 1, ed, k);
    if(ed > mid)segchg(p << 1 | 1, ed, k);
    pushup(p);
    return;
}
ll segsum(int p, int l, int r)
{
    if((tr[p].l >= l) && (tr[p].r <= r))return tr[p].sum;
    ll res = 0;
    int mid = (tr[p].l + tr[p].r) >> 1;
    if(l <= mid)res += segsum(p << 1, l, r);
    if(r > mid)res += segsum(p << 1 | 1, l, r);
    return res;
}
ll sumtree(int p)
{
    return segsum(1, id[p], id[p] + sz[p] - 1);
}
ll sumpath(int p, int q)
{
    ll res = 0;
    while(top[p] != top[q])
    {
        if(dep[top[p]] < dep[top[q]])swap(p, q);
        res += segsum(1, id[top[p]], id[p]);
        p = fa[top[p]];
    }
    if(dep[p] < dep[q])swap(p, q);
    res += segsum(1, id[q], id[p]);
    return res;
}
int lca(int p, int q)
{
    while(top[p] != top[q])
    {
        if(dep[top[p]] < dep[top[q]])swap(p, q);
        p = fa[top[p]];
    }
    if(dep[p] < dep[q])swap(p, q);
    return q;
}
int get_v(int p, int q)
{
    while(top[p] != top[q])
    {
        if(dep[top[p]] < dep[top[q]])swap(p, q);
        if(fa[top[p]] == q)return top[p];
        p = fa[top[p]];
    }
    if(dep[p] < dep[q])swap(p, q);
    return son[q];
}
using namespace std;
int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    for(int i = 1; i <= n; i++)scanf("%d", &w[i]);
    dfs1(1, 0, 1);
    dfs2(1, 1);
    build(1, 1, n);
    int rt = 1;
    for(int i = 1; i <= m; i++)
    {
        int op, x, y;
        scanf("%d%d", &op, &x);
        if(op == 1)
        {
            rt = x;
        }
        else if(op == 2)
        {
            ll z;
            scanf("%lld", &z);
            segchg(1, id[x], z);
        }
        else if(op == 3)
        {
            if(x == rt)
            {
                printf("%lld\n", tr[1].sum);
            }
            else
            {
                if(lca(x, rt) != x)
                {
                    printf("%lld\n", sumtree(x));
                }
                else
                {
                    printf("%lld\n", tr[1].sum - sumtree(get_v(rt, x)));
                }
            }
        }
        else if(op == 4)
        {
            scanf("%d", &y);
            printf("%lld\n", sumpath(x, y));
        }
    }
    return 0;
}

re 的 Java8 代码（求调）：

Java8

 
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
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int[] w=new int[100010];
    static int[] h=new int[100010];
    static int[] e=new int[200020];
    static int[] ne=new int[200020];
    static int idx=0;
    static int[] id=new int[100010];
    static int[] nw=new int[100010];
    static int cnt=0;
    static int[] dep=new int[100010];
    static int[] sz=new int[100010];
    static int[] top=new int[100010];
    static int[] fa=new int[100010];
    static int[] son=new int[100010];
    static SegTree[] tr=new SegTree[800080];
    public static void main(String[] args) {
        Arrays.fill(h,-1);
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int m=scan.nextInt();
        for(int i=1;i<n;i++){
            int a=scan.nextInt();
            int b=scan.nextInt();
            add(a,b);
            add(b,a);
        }
        for(int i=1;i<=n;i++){
            w[i]=scan.nextInt();
        }
        dfs1(1,0,1);
        dfs2(1,1);
        build(1,1,n);
        int rt=1;
        for(int i=1;i<=m;i++){
            int op=scan.nextInt();
            int x=scan.nextInt();
            if(op==1){
                rt=x;
            }else if(op==2){
                int y=scan.nextInt();
                segchg(1,id[x],y);
            }else if(op==3){
                if(x==rt){
                    System.out.printf("%d\n",tr[1].sum);
                }else{
                    if(lca(x,rt)!=x){
                        System.out.printf("%d\n",sumtree(x));
                    }else{
                        System.out.printf("%d\n",tr[1].sum-sumtree(get_v(rt,x)));
                    }
                }
            }else if(op==4){
                int y=scan.nextInt();
                System.out.printf("%d\n",sumpath(x,y));
            }
        }
    }
    private static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    private static void dfs1(int p,int father,int depth){
        dep[p]=depth;
        fa[p]=father;
        sz[p]=1;
        for(int i=h[p];i!=-1;i=ne[i]){
            int j=e[i];
            if(j==father)continue;
            dfs1(j,p,depth+1);
            if(sz[son[p]]<sz[j])son[p]=j;
        }
        return;
    }
    private static void dfs2(int p,int t){
        id[p]=++cnt;
        nw[cnt]=w[p];
        top[p]=t;
        if(son[p]==0)return;
        dfs2(son[p],t);
        for(int i=h[p];i!=-1;i=ne[i]){
            int j=e[i];
            if((j==fa[p])||(j==son[p]))continue;
            dfs2(j,j);
        }
        return;
    }
    private static void pushup(int p){
        tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
    }
    private static void build(int p,int l,int r){
        tr[p].l=l;
        tr[p].r=r;
        if(l==r){
            tr[p].sum=nw[r];
            return;
        }
        int mid=(l+r)>>1;
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        pushup(p);
        return;
    }
    private static void segchg(int p,int ed,int k){
        if((tr[p].l==ed)&&(tr[p].r==ed)){
            tr[p].sum=k;
            return;
        }
        int mid=(tr[p].l+tr[p].r)>>1;
        if(ed<=mid)segchg(p<<1,ed,k);
        if(ed>mid)segchg(p<<1|1,ed,k);
        return;
    }
    private static int segsum(int p,int l,int r){
        if((tr[p].l>=l)&&(tr[p].r<=r))return tr[p].sum;
        int res=0;
        int mid=(tr[p].l+tr[p].r)>>1;
        if(l<=mid)res+=segsum(p<<1,l,r);
        if(r>mid)res+=segsum(p<<1|1,l,r);
        return res;
    }
    private static int sumtree(int p){
        return segsum(1,id[p],id[p]+sz[p]-1);
    }
    private static int sumpath(int p,int q){
        int res=0;
        while(top[p]!=top[q]){
            if(dep[top[p]]<dep[top[q]]){
                int temp=p;
                p=q;
                q=temp;
            }
            res+=segsum(1,id[top[p]],id[p]);
            p=fa[top[p]];
        }
        if(dep[p]<dep[q]){
            int temp=p;
            p=q;
            q=temp;
        }
        res+=segsum(1,id[q],id[p]);
        return res;
    }
    private static int lca(int p,int q){
        while(top[p]!=top[q]){
            if(dep[top[p]]<dep[top[q]]){
                int temp=p;
                p=q;
                q=temp;
            }
            p=fa[top[p]];
        }
        if(dep[p]<dep[q]){
            int temp=p;
            p=q;
            q=temp;
        }
        return q;
    }
    private static int get_v(int p,int q){
        while(top[p]!=top[q]){
            if(dep[top[p]]<dep[top[q]]){
                int temp=p;
                p=q;
                q=temp;
            }
            if(fa[top[p]]==q)return top[p];
            p=fa[top[p]];
        }
        if(dep[p]<dep[q]){
            int temp=p;
            p=q;
            q=temp;
        }
        return son[q];
    }
}

class SegTree{
    public int l;
    public int r;
    public int sum;
}

T3 【20180819 省队班】 取数字

题面

题面

题目描述

给定 n 个整数 ai，你需要从中选取若干个数，使得它们的和是 m 的倍数。问有多少种方案。有多个询问，每次询问一个的 m 对应的答案。

输入格式

第一行两个正整数 n，q，分别表示整数的数量和询问的数量。
第二行 n 个整数 ai 。
接下来 q 行，每行表示一个 m。

输出格式

对于每个询问，输出一行答案 mod1e9+7。

思路

这道题是个背包计数的问题，背包的容量是模 m 循环的。
记 f[i][j] 表示考虑了前 i 个整数，当前余数是 j，有选和不选两种情况。那么对于一次询问 q，我们直接做的复杂度是 O(nm)，总复杂度 O(nmq)。这档暴力分应该拿到。

我们注意到 m 很小，而 n 很大，也就是说有很多重复的值，那么我们考虑设计一个下标为 dp[m][m] 的 DP 方法，每次考虑一类数。
假设第 i 种数有 k[i] 个，我们的转移是：
(1)dp[i][j]=∑h=0k[i]Ck[i]hdp[i−1][j−h×a[i]modm]
注意到 ∑k[i]=n ，以及 dp 数组的第二维最大只有 m，因此我们可以每次 O(k[i]) 地预处理出组合数的系数，表示 dp[i-1][j] 的贡献。写成伪代码就是：

1
2
for h : [0, k[i]]
    c[h % m] += C(k[i], h)

然后我们再递推 dp[i][j]，把 dp[i−1][j]×c[k]→dp[i][j+k×imodm] 即可。

总复杂度 O(q(n+m3))。

代码

100 分代码：

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200020, M = 110, mod = 1e9 + 7;
ll T, n, m, k;
ll a[N], fac[N], inv[N];
ll t[M], f[M][M], pre[M];
ll qpow(ll x, ll k)
{
    ll ans = 1;
    while(k)
    {
        if(k & 1)ans = (ans * x) % mod;
        x = (x * x) % mod;
        k >>= 1;
    }
    return ans;
}
ll C(ll b, ll a)
{
    return (((fac[b] * inv[a]) % mod) * (inv[b - a])) % mod;
}
void init()
{
    fac[0] = 1ll;
    for(int i = 1; i < N; i++)fac[i] = (fac[i - 1] * i) % mod;
    inv[N - 1] = qpow(fac[N - 1], mod - 2);
    for(int i = N - 2; i >= 0; i--)inv[i] = ((i + 1) * inv[i + 1]) % mod;
}
int main()
{
    init();
    scanf("%lld%lld", &n, &T);
    for(int i = 1; i <= n; i++)scanf("%lld", &a[i]);
    while(T--)
    {
        memset(t, 0, sizeof(t));
        memset(f, 0, sizeof(f));
        scanf("%lld", &m);
        for(int i = 1; i <= n; i++)t[(a[i] % m + m) % m]++;
        f[0][0] = qpow(2, t[0]);
        for(int i = 1; i < m; i++)
        {
            memset(pre, 0, sizeof(pre));
            for(int k = 0; k <= t[i]; k++)pre[k % m] = (pre[k % m] + C(t[i], k)) % mod;
            for(int j = 0; j < m; j++)
            {
                for(int k = 0; k <= min(m - 1, t[i]); k++)
                {
                    f[i][(j + i * k) % m] = (f[i][(j + i * k) % m] + f[i - 1][j] * pre[k] % mod) % mod;
                }
            }
        }
        printf("%lld\n", f[m - 1][0]);
    }
    return 0;
}

re 的 Java8 代码（求调）：

Java8

 
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
import java.util.Arrays;
import java.util.Scanner;

public class Main{
    static int N=200020,M=110,mod=(int)(1e9+7);
    static long[] a=new long[N];
    static long[] fac=new long[N];
    static long[] inv=new long[N];
    static long[] t=new long[M];
    static long[][] f=new long[M][M];
    static long[] pre=new long[M];
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        init();
        int n=scan.nextInt();
        int T=scan.nextInt();
        for(int i=1;i<=n;i++)a[i]=scan.nextInt();
        while((T--)!=0){
            Arrays.fill(t,0);
            for(int i=1;i<M;i++){
                for(int j=1;j<M;j++)f[i][j]=0;
            }
            int m=scan.nextInt();
            for(int i=1;i<=n;i++)t[(int)((a[i]%m+m)%m)]++;
            f[0][0]=qpow(2,t[0]);
            for(int i=1;i<m;i++){
                Arrays.fill(pre,0);
                for(int k=0;k<=t[i];k++)pre[k%m]=(pre[k%m]+C((int)t[i],k))%mod;
                for(int j=0;j<m;j++){
                    for(int k=0;k<=min(m-1,(int)t[i]);k++){
                        f[i][(j+i*k)%m]=(f[i][(j+i*k)%m]+f[i-1][j]*pre[k]%mod)%mod;
                    }
                }
            }
            System.out.println(f[m-1][0]);
        }
        scan.close();
    }
    
    private static long qpow(long x,long k){
        long ans=1;
        while(k!=0){
            if((k&1)==1)ans=(ans*x)%mod;
            x=(x*x)%mod;
            k>>=1;
        }
        return ans;
    }
    private static long C(int b,int a){
        return (((fac[b]*inv[a])%mod)*(inv[b-a]))%mod;
    }
    private static void init(){
        fac[0]=1l;
        for(int i=1;i<N;i++)fac[i]=(fac[i-1]*i)%mod;
        inv[N-1]=qpow(fac[N-1],mod-2);
        for(int i=N-2;i>=0;i--)inv[i]=((i+1)*inv[i+1])%mod;
    }
    private static int min(int a,int b){
        if(a>=b){
            return a;
        }else{
            return b;
        }
    }
}