题面

题目描述

有一个小偷进入了一个商店。

像平常一样，他把他的幸运背包带在身上，他的背包里能放 k 个东西。商店里有 n 种产品，每种产品都有无限多个。对于每个第 i 种产品，它的价值是 a[i] 。

小偷很贪婪，所以他会准确地拿 k 个产品（他有可能把某一种产品拿很多个）。

你需要找出所有小偷可能偷走的物品价值之和。

输入输出格式

输入格式：

第一行有两个整数 n 和 k（1<=n,k<=1000）—— 物品的数量和小偷会拿的物品数量。 第二行有 n 个整数，每一个 a[i]（1<=a[i]<=1000) 是从第 1 个到第 n 个物品的价值。

输出格式：

输出一行，所有可能的被偷窃的物品的价值，每两个之间用一个空格分隔。输出应该以一个递增序列输出。

输入输出样例

输入样例#1：

3 2

1 2 3

输出样例#1：

2 3 4 5 6

输入样例#2：

5 5

1 1 1 1 1

输出样例#2：

5

输入样例#3：

3 3

3 5 11

输出样例#3：

9 11 13 15 17 19 21 25 27 33

题目分析

多项式快速幂裸题。。

直接参见模板。由于有人hack模数，所以使用双模数。。

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define MAXN 0x7ffffffftypedef long long LL;const int N=1100005,mod1=998244353,mod2=1004535809;using namespace std;inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}int ksm(int x,int k,int mod){ int ret=1; while(k){ if(k&1)ret=1ll*ret*x%mod; x=1ll*x*x%mod,k>>=1; } return ret;}void NTT(int *a,int x,int K,int mod){ static int rev[N],lst; int n=(1<
            
             >1]>>1)|((i&1)<