Thief in a Shop (Codeforces 632E)
Tags: Math, fft

A thief made his way to a shop.As usual he has his lucky knapsack with him. The knapsack can contain k objects. There are n kinds of products in the shop and an infinite number of products of each kind. The cost of one product of kind i is ai.The thief is greedy, so he will take exactly k products (it's possible for some kinds to take several products of that kind).Find all the possible total costs of products the thief can nick into his knapsack.

Input: The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of products the thief will take.The second line contains n integers ai (1 ≤ ai ≤ 1000) — the costs of products for kinds from 1 to n.

Output: Print the only line with all the possible total costs of stolen products, separated by a space. The numbers should be printed in the ascending order.


Sample Inputs:
3 2
1 2 3

5 5
1 1 1 1 1

3 3
3 5 11

Sample Outputs:
2 3 4 5 6

5

9 11 13 15 17 19 21 25 27 33

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g, p):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    if not p:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i ^ l] % mod
    else:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    ans = [0] * c
    for i in range(c):
        if u[i]:
            ans[i] = 1
    return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] * (max(a) + 1)
for i in a:
    x[i] = 1
v = [1]
while k:
    if k & 1:
        v = convolve(x, v, 0)
    k >>= 1
    if k:
        x = convolve(x, x, 1)
ans = []
for i in range(len(v)):
    if v[i]:
        ans.append(i)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]
u = [0] * (1 << 23)

def convolve(f, g, p):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    for i in range(lf):
        u[i] = f[i]
    for i in range(lf, l):
        u[i] = 0
    for i in range(lg):
        u[i ^ l] = g[i]
    for i in range(lg, l):
        u[i ^ l] = 0
    m = l >> 1
    if not p:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i ^ l] % mod
    else:
        for k in range(x, 0, -1):
            r0 = r[k]
            for i in range(0, l, m << 1):
                y = 1
                for j in range(i, m + i):
                    (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                    y = y * r0 % mod
            m >>= 1
        for i in range(l):
            u[i] = u[i] * u[i] % mod
    m = 1
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    ans = [0] * c
    for i in range(c):
        if u[i]:
            ans[i] = 1
    return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
x = [0] * (max(a) + 1)
for i in a:
    x[i] = 1
v = [1]
while k:
    if k & 1:
        v = convolve(x, v, 0)
    k >>= 1
    if k:
        x = convolve(x, x, 1)
ans = []
for i in range(len(v)):
    if v[i]:
        ans.append(i)
sys.stdout.write(' '.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
mod = 998244353
r = [pow(3, mod - 1 >> i, mod) for i in range(23)]
ir = [pow(i, mod - 2, mod) for i in r]

def convolve(f, g):
    (lf, lg) = (len(f), len(g))
    c = lf + lg - 1
    x = c.bit_length()
    l = 1 << x
    u = [0] * (l << 1)
    for i in range(lf):
        u[i] = f[i]
    for i in range(lg):
        u[i ^ l] = g[i]
    m = l >> 1
    for k in range(x, 0, -1):
        r0 = r[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m]) % mod, (u[j] - u[j + m]) * y % mod)
                (u[j + l], u[j + m + l]) = ((u[j + l] + u[j + m + l]) % mod, (u[j + l] - u[j + m + l]) * y % mod)
                y = y * r0 % mod
        m >>= 1
    m = 1
    for i in range(l):
        u[i] = u[i] * u[i ^ l] % mod
    for k in range(1, x + 1):
        r0 = ir[k]
        for i in range(0, l, m << 1):
            y = 1
            for j in range(i, m + i):
                (u[j], u[j + m]) = ((u[j] + u[j + m] * y) % mod, (u[j] - u[j + m] * y) % mod)
                y = y * r0 % mod
        m <<= 1
    ans = [0] * c
    for i in range(c):
        if u[i]:
            ans[i] = 1
    return ans
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
u = [0] * (max(a) + 1)
for i in a:
    u[i] = 1
v = [1]
while k:
    if k & 1:
        v = convolve(u, v)
    k >>= 1
    if k:
        u = convolve(u, u)
ans = []
for i in range(len(v)):
    if v[i]:
        ans.append(i)
sys.stdout.write(' '.join(map(str, ans)))