综合考察???.

Description

给一个集合, 要生成一个长为$n$的序列, 每个位置都从集合里选数, 要求各数之积被$m$整除, 求方案数.

Solution

个数之积不像和那样可以随便卷. 但是我们有一个东西叫指标, 也就是离散对数, 这玩意是可以把乘积视为质数上的相加的.

因为保证给的数是个质数, 所以可以求原根和指标, 暴力就行.

然后要实现NTT循环卷积. 也要快速幂.

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

using namespace std;
typedef long long ll;

inline ll quick_power(ll base, ll index) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = ret * base % mod;
    index >>= 1;
    base = base * base % mod;
  }
  return ret;
}
inline ll quick_power(ll base, ll index, ll p) {
  ll ret = 1;
  while (index) {
    if (index & 1) ret = (base * ret) % p;
    index >>= 1;
    base = base * base % p;
  }
  return ret;
}
namespace math {
  static const int maxm = 100010;
  int npr[maxm], pr[maxm >> 1], cnt;
  int mindiv[maxm], ind[maxm], G, m;
  void euler() {
    for (int i = 2; i <= m; ++i) {
      if (!npr[i]) {
        pr[++cnt] = i;
        mindiv[i] = i;
      }
      for (int j = 1; j <= cnt && i * pr[j] <= m; ++j) {
        npr[i * pr[j]] = 1;
        mindiv[i * pr[j]] = pr[j];
        if (!(i % pr[j])) break;
      }
    }
  }
  inline bool check(int g, int ori) {
    int tmp = 1;
    for (int i = 1; i < ori; ++i) {
      tmp = (tmp * g) % m;
      if (tmp == 1) return 0;
    }
    // printf("%d\n", g);
    return 1;
  }
  int getG() {
    int g = 2;
    for (; g < m; ++g) {
      if (check(g, m - 1)) break;
    }
    return g;
  }
  void getI() {
    for (int k = 0, w = 1; k < m; w = (w * G) % m, k++)
      ind[w] = k;//, printf("%d = %d\n", w, k);
  }
}
namespace NTT {
  using math::maxm;
  static const ll G = 3;
  int rev[maxm];
  ll A[maxm], B[maxm], C[maxm];
  int N, L;
  int n, m, x, s;
  void init() {
    for (int i = 0; i < N; ++i) {
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
    }
  }
  void DFT(ll *a, int typ) {
    for (int i = 0; i < N; ++i) 
      if (i > rev[i]) swap(a[i], a[rev[i]]);
    for (int i = 2; i <= N; i <<= 1) {
      int m = (i >> 1);
      ll e = quick_power(G, (mod - 1) / i);
      //if (typ == -1) e = quick_power(e, mod - 2);
      for (int j = 0; j < N; j += i) {
        ll w = 1;
        for (int k = 0; k < m; ++k) {
          ll t = w * a[j + m + k] % mod;
          a[m + j + k] = (a[j + k] - t + mod) % mod;
          a[j + k] = (a[j + k] + t) % mod;
          w = w * e % mod;
        }
      }
    }
    if (typ == 1) return;
    reverse(a + 1, a + N); ll inv = quick_power(N, mod - 2);
    for (int i = 0; i < N; ++i) a[i] = a[i] * inv % mod;
    for (int i = m; i < N; ++i) {
      int x = ((i % (m - 1)) ? (i % (m - 1)) : (m - 1));
      a[x] = (a[i] + a[x]) % mod;
      a[i] = 0;
    }
  }
  void NTTpow(ll *a, int index) {
    for (int i = 0; i < N; ++i) B[i] = a[i];
    index--;
    while (index) {
      DFT(a, 1);
      if (index & 1) {
        DFT(B, 1);
        for (int i = 0; i < N; ++i) B[i] = B[i] * a[i] % mod;
        DFT(B, -1);
      }
      for (int i = 0; i < N; ++i) a[i] = a[i] * a[i] % mod;
      index >>= 1;
      DFT(a, -1);
    }
    for (int i = 0; i < N; ++i) a[i] = B[i];
  }

  void solve() {
    scanf("%d%d%d%d", &n, &m, &x, &s);
    math::m = m;
    // math::euler();
    math::G = math::getG();
    // printf("%d\n", math::G);
    math::getI();
    int u;
    for (int i = 1; i <= s; ++i) {
      scanf("%d", &u);
      // printf("%d\n", math::ind[u]);
      C[math::ind[u]]++;
    }
    N = 1; L = 0;
    while (N <= (m << 1)) N <<= 1, L++;
    init();
    // for (int i = 0; i < N; ++i) printf("%lld\n", C[i]);
    // puts("");
    A[math::ind[1]] = 1;
    NTTpow(C, n); 
    // for (int i = 0; i < N; ++i) printf("%lld\n", C[i]);
    // puts("");
    DFT(A, 1); DFT(C, 1);
    for (int i = 0; i < N; ++i)
      A[i] = A[i] * C[i] % mod;
    DFT(A, -1);
    printf("%lld\n", A[math::ind[x]]);
  }
}

int main() {
  NTT::solve();
  return 0;
}