题解是 GPT 写的。

1. 规则抽象成集合递推

设模数为 $M$。

• 第一天被感染的集合记为

  $$B \subseteq \{0,1,\dots,M-1\}$$

• 第 $d$ 天被感染的集合记为 $S_d$。

题意说：某人 $p$ 在某天会被感染，当且仅当存在

• $a \in S_{d-1}$（前一天感染过）

• $b \in B$（第一天感染过）
  使得

$$a\times b \equiv p \pmod M$$

因此有递推：

$$S_d = S_{d-1}\ \otimes\ B$$

其中 $\otimes$ 表示“集合乘法”：

$$A\otimes C = \{(x\cdot y)\bmod M \mid x\in A,\ y\in C\}$$

又因为 $S_1 = B$，所以

$$S_2 = B\otimes B,\quad S_3 = (B\otimes B)\otimes B = B^3,\ \dots$$

最终得到：

$$S_K = B^K$$

这里 $B^K$ 表示在模 $M$ 下取 $K$ 次集合乘法（允许重复选同一个元素，符合“可以重复感染”的含义）。

---

2. 关键：如何计算集合乘法 $A\otimes C$

用一个长度为 $M$ 的布尔数组表示集合（0/1）：

• A[i]=1 表示 $i\in A$

• C[j]=1 表示 $j\in C$

则

D[(i*j)%M] = 1  当且仅当存在 i∈A, j∈C

朴素做法就是两层枚举 $i,j$，复杂度 $O(M^2)$。因为 $M\le 1500$，$1500^2=2.25\times 10^6$，是可以接受的。

---

3. 由于 K 很大：对集合做快速幂

我们要算 $B^K$。这是“幂”的结构，所以可以用二进制快速幂（Exponentiation by Squaring）。

关键点是需要一个“乘法单位元”集合：

• 在模乘法下单位元是数字 $1$

• 所以单位集合是 $\{1\}$

令：

• R = {1}（答案集合，初始为单位元）

• Base = B

按 $K$ 的二进制位从高到低（或从低到高）迭代：

• 每一步先做：R = R ⊗ R（相当于指数翻倍/平方）

• 如果当前位为 1：R = R ⊗ Base

最后得到的 R 就是 $B^K$，也就是第 $K$ 天会感染的所有编号。

你给的代码正是这个过程：

• ans 保存当前集合 R

• 先平方（两层循环用 ans[org] 和 ans[org]）

• 如果该位在 k 里为 1，再乘一次 baza（即 B）

---

4. 正确性简述

• 递推部分：由题目定义直接推出 $S_d = S_{d-1}\otimes B$，归纳可得 $S_K = B^K$。

• 快速幂部分：集合乘法满足结合律（本质来自整数乘法 mod $M$ 的结合律），因此二进制快速幂完全成立；从单位元 $\{1\}$ 出发，按位累乘能得到精确的 $B^K$。

---

5. 复杂度

• 集合乘法一次：$O(M^2)$

• 快速幂需要约 $\log_2 K \le 60$ 次平方 + 若干次乘底

• 总复杂度：

  $$O(M^2\log K)$$

  在 $M=1500$ 时大约是 $2.25\times 10^6 \times 60 \approx 1.35\times 10^8$ 级别，C++ 里可行。

• 空间：$O(M)$

---

6. 输出

最终集合里为 1 的下标按从小到大输出即可。若 $N=0$，则 $B$ 为空，任何乘法都得空集，输出空行也符合题意。

#include <bits/stdc++.h>
using namespace std;
// Time complexity: O(max_mod * max_mod * log(k))
const int max_mod = 1500;
char baza[max_mod];
char ans[2][max_mod], org = 0;
int mod;
long long k;
void load() {
  int n, t;
  scanf("%lld%d%d", &k, &mod, &n);
  for (int j = 0; j < n; ++j)
    scanf("%d", &t) && (baza[t] = 1);
}
void solve() {
  ans[org][1] = 1;
  for (unsigned long long mask = (1ll<<60); mask; mask >>=1) {
    memset(ans[!org], 0, mod);
    for (int i = 0; i < mod; ++i)
      for (int j = 0; j < mod; ++j)
        if (ans[org][i] && ans[org][j])
          ans[!org][ (i*j) % mod ] = 1;
    org = !org;
    if (mask & k) {
      memset(ans[!org], 0, mod);
      for (int i = 0; i < mod; ++i)
        for (int j = 0; j < mod; ++j)
          if (ans[org][i] && baza[j])
            ans[!org][ (i*j) % mod ] = 1;
      org = !org;
    }
  }
  for (int j = 0; j < mod; ++j) {
    if (ans[org][j])
      printf("%d ", j);
  }
  printf("\n");
}

int main() {
  load();
  solve();
  return 0;
}