题解 CF632E 【Thief in a Shop】

Weng_Weijie · 2018-09-21 14:01:01 · 题解

题解：

对所有物品构造生成函数F(x)=\displaystyle\sum_{i\in S}x^i

取 k 个物品相当于选取其中的 k 项相乘

于是计算 F^k(x) 输出其中不为零的项即可

需要注意的一点是：模数 998244353 和 1004535809 都被hack了

可以选择双模数防止被hack(至少CF没有卡双模的数据)

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#define N 1048576
using LL = long long;
const int G = 3;
int mod;
int n, k, rev[N], lim, ilim, s, wn[N + 1];
std::vector<int> v;
inline int pow(int x, int y) {
    int ans = 1;
    for (; y; y >>= 1, x = static_cast<LL> (x) * x % mod)
        if (y & 1) ans = static_cast<LL> (ans) * x % mod;
    return ans;
}
inline int& up(int& x, int y) { if ((x += y) >= mod) x -= mod; return x; }
inline void NTT(int* A, int typ) {
    for (int i = 0; i < lim; i++) if (i < rev[i]) std::iter_swap(A + i, A + rev[i]);
    for (int i = 1; i < lim; i += i) {
        const int t = lim / i / 2;
        for (int j = 0; j < lim; j += i + i) {
            for (int k = 0; k < i; k++) {
                int w = typ ? wn[t * k] : wn[lim - t * k];
                int x = A[k + j], y = static_cast<LL> (w) * A[k + j + i] % mod;
                up(A[k + j], y), up(A[k + j + i] = x, mod - y);
            }
        }
    }
    if (!typ) for (int i = 0; i < lim; i++) A[i] = static_cast<LL> (ilim) * A[i] % mod;
}
inline void init(int len, int mod) {
    ::mod = mod;
    lim = 1, s = -1; while (lim < len) lim += lim, s++; ilim = pow(lim, mod - 2);
    for (int i = 0; i < lim; i++) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
    int w = pow(G, (mod - 1) / len);
    wn[0] = 1;
    for (int i = 1; i <= lim; i++) wn[i] = static_cast<LL> (wn[i - 1]) * w % mod;
}
int A[N], B[N];
int main() {
    std::ios::sync_with_stdio(0);
    std::cin >> n >> k;
    for (int i = 1, x; i <= n; i++) std::cin >> x, A[x] = B[x] = 1;
    init(1048576, 998244353);
    NTT(A, 1);
    for (int i = 0; i < lim; i++) A[i] = pow(A[i], k);
    NTT(A, 0);
    for (int i = 1; i <= 1000000; i++) if (A[i]) v.push_back(i);
    init(1048576, 1004535809);
    NTT(B, 1);
    for (int i = 0; i < lim; i++) B[i] = pow(B[i], k);
    NTT(B, 0);
    for (int i = 1; i <= 1000000; i++) if (B[i]) v.push_back(i);
    std::sort(v.begin(), v.end()); int tot = std::unique(v.begin(), v.end()) - v.begin();
    v.resize(tot);
    for (int i : v) std::cout << i << " ";
    return 0;
}