Codeforces 286E Ladies' Shop

考虑 \(p_i\) 满足什么不会被选。
令当前选出来的 \(p_j\) 的集合为 \(S\)。
能发现当用 \(S\) 中的数能够凑（可多选，可选重）出 \(p_i\) 时 \(p_i\) 就不会被选。
考虑凑出 \(p_i\) 的最后一步所用的 \(2\) 个数 \(x + y = p_i\)。
因为这 \(2\) 个数一定能被 \(S\) 中的数凑出且题目中合法的条件为 \(S\) 中能凑出来 \(\le m\) 的数都必须出现在 \(p\) 中，所以 \(x, y\) 就会出现在 \(p\) 种。
即是存在 \(j, k\) 满足 \(p_j + p_k = p_i\)，\(p_i\) 就不会被选。

考虑把判定存在转为方案数，即判断有多少组 \(j, k\) 满足 \(p_j + p_k = p_i\)。
令 \(p_i\) 的集合为 \(P\)，记 \(f(x) = \sum\limits_{i = 0}^x [i\in P][x - i\in P]\)，即判断 \(f(p_i)\) 是否 \(> 0\) 即可。
能发现这个式子很像多项式。
于是令 \(G(x) = \sum\limits_{i = 0}^m [i\in P]x^i, F(x) = \sum\limits_{i = 0}^m f(i)x^i\)，有 \(F(x) = G^2(x)\)。
用 \(\text{NTT}\) 即可。

时间复杂度 \(O(m\log m)\)。

#include<bits/stdc++.h>
using i64 = long long;
constexpr i64 mod = 998244353, G = 3;
constexpr inline i64 qpow(i64 a, i64 b) {i64 v = 1; while (b) b & 1 && ((v *= a) %= mod), (a *= a) %= mod, b >>= 1; return v;}
constexpr inline i64 inv(i64 a) {return qpow(a, mod - 2);}
constexpr i64 invG = inv(G);
inline i64 Mod(i64 x) {return x >= mod ? (x - mod) : x;}
inline i64 Mod(i64 x, i64 y) {return Mod(x + y);}
inline i64 Modf(i64 x, i64 y) {return Mod(x + mod - y);}
const int maxn = (1 << 21) + 10;
inline int pw2N(int n) {int N = 1; while (N <= n) N <<= 1; return N;}
inline void NTT(i64 *f, int n, bool isI) {
    static int rev[maxn]; static i64 th[maxn];
    for (int i = 1; i < n; i++) rev[i] = (rev[i >> 1] >> 1) | (i & 1 ? (n >> 1) : 0);
    for (int i = 0; i < n; i++) i < rev[i] && (std::swap(f[i], f[rev[i]]), 1);
    for (int len = 1; len < n; len <<= 1) {
        i64 I = qpow(isI ? invG : G, (mod - 1) / len / 2);
        th[0] = 1;
        for (int i = 1; i < len; i++) th[i] = th[i - 1] * I % mod;
        for (int s = 0; s < n; s += len + len) for (int t = 0; t < len; t++) {
            i64 v = th[t] * f[s | t | len] % mod;
            f[s | t | len] = Modf(f[s | t], v), f[s | t] = Mod(f[s | t], v);
        }
    }
    if (isI) {
        i64 invn = inv(n);
        for (int i = 0; i < n; i++) (f[i] *= invn) %= mod;
    }
}
i64 f[maxn];
bool vis[maxn];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        f[x] = 1, vis[x] = 1;
    } 
    int N = pw2N(m << 1);
    NTT(f, N, 0);
    for (int i = 0; i < N; i++) (f[i] *= f[i]) %= mod;
    NTT(f, N, 1);
    for (int i = 0; i <= m; i++) if (! vis[i] && f[i]) return puts("NO"), 0;
    std::vector<int> P;
    for (int i = 0; i <= m; i++) vis[i] && ! f[i] && (P.push_back(i), 1);
    printf("YES\n%zu\n", P.size());
    for (int x : P) printf("%d ", x);
    return 0;
}