Thief in a Shop

n个物品每个价值a_i，要求选k个，可以重复。问能取到哪几个价值？

1?≤?n,?k?≤?1000，1?≤?a_i?≤?1000

题解

将选一个物品能取到的价值的01生成函数k次方即可得到选k个物品得到的某个权值的方案数。

出题人卡NTT模数，998244353和1004535809都会被卡。然而469762049没被卡……

CO int N=1048576;
int a[N];
int rev[N],omg[N];

void NTT(int a[],int lim){
    for(int i=0;i<lim;++i)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int i=1;i<lim;i<<=1)
        for(int j=0;j<lim;j+=i<<1)
            for(int k=0;k<i;++k){
                int t=mul(omg[lim/(i<<1)*k],a[j+i+k]);
                a[j+i+k]=add(a[j+k],mod-t),a[j+k]=add(a[j+k],t);
            }
}

int main(){
    int n=read<int>(),m=read<int>();
    while(n--) a[read<int>()]=1;
    int len=ceil(log2(m*1000+1)),lim=1<<len;
    for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
    omg[0]=1,omg[1]=fpow(3,(mod-1)/lim);
    for(int i=2;i<lim;++i) omg[i]=mul(omg[i-1],omg[1]);
    NTT(a,lim);
    for(int i=0;i<lim;++i) a[i]=fpow(a[i],m);
    omg[0]=1,omg[1]=fpow(omg[1],mod-2);
    for(int i=2;i<lim;++i) omg[i]=mul(omg[i-1],omg[1]);
    NTT(a,lim);
    int ilim=fpow(lim,mod-2);
    for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
    for(int i=0;i<lim;++i)
        if(a[i]) printf("%d ",i);
    return 0;
}

这题还有背包DP做法。将权值排序，对于i>1，把a_i-=a₁。然后做一个最短路径DP，只要路径长度≤k就可以凑出来。

之所以要减去a₁，是因为最短路径长度<k的结果相当于用了(k-长度)个a₁。

int n,k,a[1005],dp[1000005];
int main(){
    n=read(),k=read();
    for(int i=0;i<n;i++)
        a[i]=read();
    sort(a,a+n);
    for(int i=1;i<n;i++)
        a[i]-=a[0];
    for(int i=1;i<=k*a[n-1];i++)
        dp[i]=3000;
    for(int i=1;i<n;i++)
        for(int j=a[i];j<=a[i]*k;j++)
            dp[j]=min(dp[j],dp[j-a[i]]+1);
    for(int i=0;i<=k*a[n-1];i++)
        if(dp[i]<=k)printf("%d ",k*a[0]+i);
    return 0;
}

Lightsabers (hard)

有\(n\)个有颜色的球，颜色编号为\(1\dots m\)中的一个。现在让你从中拿\(k\)个球，问拿到的球的颜色所构成的可重集合有多少种不同的可能。

注意同种颜色球是等价的，但是两个颜色为\(x\)的球不等价于一个。

\(1\leq n\leq 2\times 10^5,\quad 1\leq m,k\leq n。\)

题解

此题把每种颜色能选的数量的01生成函数乘起来就好了。

但是有个问题，那就是如果对每个多项式都做长度为\(k\)的FFT的话，是会TLE的。

所以需要用到启发式合并，每次选两个长度最小的多项式进行合并。可以用堆来维护，时间复杂度\(O(n \log^2 n)\)。

可以使用STL的make_heap，push_heap，pop_heap系列函数，比priority_queue更快。

co double pi=acos(-1);
struct node {
double x,y;
node(){}
node(double x,double y):x(x),y(y){}
};
il node operator+(co node&a,co node&b){
    return (node){a.x+b.x,a.y+b.y};
}
il node operator-(co node&a,co node&b){
    return (node){a.x-b.x,a.y-b.y};
}
il node operator*(co node&a,co node&b){
    return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}

co int N=1<<18,mod=1009;
int n,m,k,num[N];

node w[N],A[N],B[N];
int rev[N];

void trans(node a[],int lim){
    for(int i=0;i<lim;++i)
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int step=1;step<lim;step<<=1){
        int quot=lim/(step<<1);
        for(int i=0;i<lim;i+=step<<1){
            int j=i+step;
            for(int k=0;k<step;++k){
                node t=w[quot*k]*a[j+k];
                a[j+k]=a[i+k]-t,a[i+k]=a[i+k]+t;
            }
        }
    }
}
void mul_to(co vector<int>&a,co vector<int>&b,vector<int>&c){
    for(int i=0;i<a.size();++i) A[i]=(node){a[i],0};
    for(int i=0;i<b.size();++i) B[i]=(node){b[i],0};
    int len=ceil(log2(a.size()+b.size()-1)),lim=1<<len;
    for(int i=0;i<lim;++i){
        rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
        w[i]=(node){cos(i*2*pi/lim),sin(i*2*pi/lim)};
    }
    for(int i=a.size();i<lim;++i) A[i]=(node){0,0};
    for(int i=b.size();i<lim;++i) B[i]=(node){0,0};
    trans(A,lim),trans(B,lim);
    for(int i=0;i<lim;++i){
        A[i]=A[i]*B[i];
        w[i].y=-w[i].y;
    }
    trans(A,lim);
    c.resize(a.size()+b.size()-1);
    for(int i=0;i<c.size();++i)
        c[i]=(long long)round(A[i].x/lim)%mod;
}

vector<int> col[N<<1];
int tot;

il bool cmp(int a,int b){
    return col[a].size()>col[b].size();
}
int heap[N],siz;

int main(){
    read(n),read(m),read(k);
    for(int i=1;i<=n;++i) ++num[read<int>()];
    for(int i=1;i<=m;++i){
        if(!num[i]) continue;
        ++tot,col[tot].resize(num[i]+1);
        for(int j=0;j<=num[i];++j) col[tot][j]=1;
        heap[++siz]=tot;
    }
    make_heap(heap+1,heap+siz+1,cmp);
    while(siz>=2){
        int x=heap[1];
        pop_heap(heap+1,heap+siz+1,cmp),--siz;
        int y=heap[1];
        pop_heap(heap+1,heap+siz+1,cmp),--siz;
        mul_to(col[x],col[y],col[++tot]);
        heap[++siz]=tot,push_heap(heap+1,heap+siz+1,cmp);
    }
    printf("%d\n",col[tot][k]);
    return 0;
}

CF632E Thief in a Shop 和 CF958F3 Lightsabers (hard)

原文：https://www.cnblogs.com/autoint/p/11271996.html