题目 https://cn.vjudge.net/problem/CodeForces-632E
题意
完全背包 N种无限个的商品 去K次 求可能价值情况
思路
FFT
#include <bits/stdc++.h>using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
struct Complex
{double x,y;Complex(double _x = 0.0,double _y = 0.0){x = _x;y = _y;}Complex operator - (const Complex &b) const{return Complex(x - b.x, y - b.y);}Complex operator + (const Complex &b) const{return Complex(x + b.x, y + b.y);}Complex operator * (const Complex &b) const{return Complex(x * b.x - y * b.y, x*b.y + y*b.x);}
};
void change(Complex y[], int len)
{int i,j,k;for(i=1,j=len/2; i < len-1; i++){if(i < j){swap(y[i],y[j]);}k = len/2;while(j >= k){j -= k;k /= 2;}if(j < k){j += k;}}return ;
}void fft(Complex y[],int len,int on)
{change(y,len);for(int h = 2; h<=len; h<<=1){Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j = 0; j<len; j+=h){Complex w(1,0);for(int k = j; k<j+h/2; k++){Complex u = y[k];Complex t = w*y[k+h/2];y[k] = u+t;y[k+h/2] = u-t;w = w*wn;}}}if(on == -1){for(int i = 0; i < len; i++){y[i].x /= len;}}
}
const int maxn = 1<<20;
Complex x[5*maxn],y[5*maxn];
int a[5*maxn];
ll sum[5*maxn];
ll siz[5*maxn];
int main()
{int t,n,m;scanf("%d %d",&n, &m);memset(siz,0,sizeof(siz));ll len1 = 0;int maxx = 0;for(int i = 0; i< n; i++){scanf("%d",&a[i]);siz[a[i]] = 1;maxx = max(maxx,a[i]);}len1 = maxx * m;int len = 1;while(len < len1) len <<= 1;for(int i = 0; i<len; i++)x[i] = Complex(siz[i],0);y[0] = Complex(1,0);for(int i = 1;i < len;i++)y[i] = Complex(0,0);fft(x,len,1);fft(y,len,1);
// cout<<len<<endl;while(m){if(m % 2 == 1){for(int i = 0; i < len; i++)y[i] = x[i]*y[i];fft(y,len,-1);for(int i = 0; i < len; i++)sum[i] = (int)(y[i].x + 0.5);for(int i = 0; i < len; i++){if(sum[i]) sum[i] = 1;}for(int i = 0;i < len;i++)y[i] = Complex(sum[i],0);fft(y,len,1);}for(int i = 0; i < len; i++)x[i] = x[i]*x[i];fft(x,len,-1);for(int i = 0; i < len; i++)sum[i] = (int)(x[i].x + 0.5);for(int i = 0; i < len; i++){if(sum[i]) sum[i] = 1;}for(int i = 0;i < len;i++)x[i] = Complex(sum[i],0);fft(x,len,1);m /= 2;}fft(y,len,-1);memset(siz,0,sizeof(siz));for(int i = 0;i < len;i++){siz[i] = (ll)(y[i].x + 0.5);}for(int i = 1; i <= len; i++){if(siz[i])printf("%d ",i);}return 0;
}