• 这里定义一种群(G, \cdot), 满足如下条件: (m为常数)

    a,b \in G

    \text{if} a + b\le m, \text{then } a+b \in G

题意

给定A集合, 求S集合: 使得S的生成子群为A, 且最小化S大小.

\min (|S|) \text{ s.t.} < S >=A

sol

记录一下这个套路吧, 好像之前一直没有记住啊.

  • 判断无解的情况非常好做: 如果A不封闭, 那么必然无解, 否则肯定有解(SA即可).

然后考虑最小化答案集合的大小!

那么有一个非常重要且显然的性质:

  • A集合等于S所有sum不超过m的线性组合.

不妨令0加入该集合, 并不影响讨论.

对于a(a\in A) 来说, 必定\exist b, c(b, c \in A) \text{ s.t. } b+c=a

也就是A中任一元素a必然可以变成b+c的形式

Proof

考虑a被表示为S中元素的线性组合:

a=\sum_i s_i \cdot x_i

由于a > 0, 故必定存在k \text{ s.t. } x_k > 0

那么取 b=\bigg( \sum_i s_i\cdot x_i \bigg) – s_k, c=s_k

b必然小于a, 且也是一个S的一个线性组合, c同理.


然后考虑如何输出方案.

很显然, 由于< S >= A\Rightarrow S \subset A, 那么只要在A中找S就好了.

我们将A变成多项式f:

f(x)=\sum_i x^{a_i} \ (a_i \in A)

然后了令g = f * f

  1. 如果[x^a] g(x) \neq 0[x^a]f(x) = 0 直接输出NO, 即有它不封闭.

  2. 如果[x^a]g(x) > 2a可以表示成b+c的形式

    那么它肯定不是S集合的数

  3. 如果[x^a]g(x) =2 那么a就是S中的数.

证明从简自己证(gan)证(xing)就好了

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1 << 21 | 10;
const int mod = 998244353, g = 3;

namespace {
    inline void upd(int &a, int b) {
        a += b; if(a >= mod) a -= mod;
    }
    inline int add(int a, int b) {
        return a + b < mod ? a + b : a + b - mod;
    }
    inline int sub(int a, int b) {
        return a - b < 0 ? a - b + mod : a - b;
    }
    inline int mul(int a, int b) {
        return (long long) a * b % mod;
    }
    inline int Pow(int a, int b = mod - 2) {
        int res = 1;
        for(; b; b >>= 1, a = mul(a, a))
            if(b & 1) res = mul(res, a);
        return res;
    }
}

int n, m, x, a[N], b[N];

namespace poly {
    int lim, rev[N], o[N], wn[30], iwn[30];

    inline void init(int n) {
        for(lim = 1; lim < n; lim *= 2);
        for(int i = 0; i < 25; ++i)
            wn[i] = Pow(g, (mod - 1) >> i), iwn[i] = Pow(wn[i]);
        for(int i = 1; i < lim; ++i)
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    }
    void dft(int *a, int f) {
        static int m, u, v, w;
        for(int i = 0; i < lim; ++i)
            if(i < rev[i]) swap(a[i], a[rev[i]]);
        for(int len = 2, icnt = 1; len <= lim; len <<= 1, ++icnt) {
            m = len >> 1;
            w = (f < 0) ? iwn[icnt] : wn[icnt];
            o[0] = 1;
            for(int i = 1; i < m; ++i)
                o[i] = mul(o[i - 1], w);
            for(int j = 0; j < lim; j += len)
                for(int i = j; i < j + m; ++i) {
                    u = a[i], v = a[i + m];
                    a[i] = add(u, mul(o[i - j], v));
                    a[i + m] = sub(u, mul(o[i - j], v));
                }
        }
        if(f < 0)
            for(int i = 0, iv = Pow(lim); i < lim; ++i)
                a[i] = mul(a[i], iv);
    }

    void main() {
        static vector<int> ans;
        ans.clear(), ++m;
        for(int i = 0; i < m; ++i)
            b[i] = a[i];
        init(m * 2 - 1), dft(b, 1);
        for(int i = 0; i < lim; ++i)
            b[i] = mul(b[i], b[i]);
        dft(b, -1);
        for(int i = 0; i < m; ++i) {
            if(b[i] && !a[i]) {
                puts("NO");
                exit(0);
            }
            if(b[i] == 2)
                ans.push_back(i);
        }
        puts("YES");
        printf("%d\n", (int) ans.size());
        for(int i = 0; i < (int) ans.size(); ++i)
            printf("%d ", ans[i]);
        puts("");
    }
}

int main() {
    scanf("%d%d", &n, &m);
    a[0] = 1;
    for(int i = 1; i <= n; ++i)
        scanf("%d", &x), a[x] = 1;
    poly :: main();
    return 0;
}