Codeforces632E Thief in a Shop(NTT + 快速幂)

时间:2022-09-22 13:58:16

题目

Source

http://codeforces.com/contest/632/problem/E

Description

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 Input

3 2
1 2 3

5 5
1 1 1 1 1

3 3
3 5 11

Sample Output

2 3 4 5 6
5
9 11 13 15 17 19 21 25 27 33

分析

题目大概说给有n种价值各一的物品,每种数量都无限多,问取出k个物品能取出的物品价值和的所有情况。

用母函数解,价值为指数、存不存在为系数,构造多项式求k次幂即可。
这自然想到FFT+快速幂求,这样时间复杂度才够。

FFT直接求的话结果的系数最大到达10001000太爆炸了,当然也可以求一次卷积后非0指数重新赋值成1;不过我想着开头一次DFT结尾一次IDFT这样更快、更轻松点,所以用NTT了。。

我NTT模数取1004535809 WA在20,取998244353 WA在21。。看样子是系数取模后变为0了,数据叼叼的。。于是我就两个模数都取,然后4000多ms险过了。。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1048576 //const long long P=50000000001507329LL; // 190734863287 * 2 ^ 18 + 1
long long P=1004535809; // 479 * 2 ^ 21 + 1
//const long long P=998244353; // 119 * 2 ^ 23 + 1
const int G=3; long long mul(long long x,long long y){
return (x*y-(long long)(x/(long double)P*y+1e-3)*P+P)%P;
}
long long qpow(long long x,long long k,long long p){
long long ret=1;
while(k){
if(k&1) ret=mul(ret,x);
k>>=1;
x=mul(x,x);
}
return ret;
} long long wn[25];
void getwn(){
for(int i=1; i<=21; ++i){
int t=1<<i;
wn[i]=qpow(G,(P-1)/t,P);
}
} int len;
void NTT(long long y[],int op){
for(int i=1,j=len>>1,k; i<len-1; ++i){
if(i<j) swap(y[i],y[j]);
k=len>>1;
while(j>=k){
j-=k;
k>>=1;
}
if(j<k) j+=k;
}
int id=0;
for(int h=2; h<=len; h<<=1) {
++id;
for(int i=0; i<len; i+=h){
long long w=1;
for(int j=i; j<i+(h>>1); ++j){
long long u=y[j],t=mul(y[j+h/2],w);
y[j]=u+t;
if(y[j]>=P) y[j]-=P;
y[j+h/2]=u-t+P;
if(y[j+h/2]>=P) y[j+h/2]-=P;
w=mul(w,wn[id]);
}
}
}
if(op==-1){
for(int i=1; i<len/2; ++i) swap(y[i],y[len-i]);
long long inv=qpow(len,P-2,P);
for(int i=0; i<len; ++i) y[i]=mul(y[i],inv);
}
}
void Convolution(long long A[],long long B[],int n){
for(len=1; len<(n<<1); len<<=1);
for(int i=n; i<len; ++i){
A[i]=B[i]=0;
} NTT(A,1); NTT(B,1);
for(int i=0; i<len; ++i){
A[i]=mul(A[i],B[i]);
}
NTT(A,-1);
} long long A[MAXN],B[MAXN],C[MAXN];
long long cnt[MAXN]; int main(){
getwn();
int n,k,a;
scanf("%d%d",&n,&k);
int mx=0;
for(int i=0; i<n; ++i){
scanf("%d",&a);
++cnt[a];
mx=max(mx,a);
}
for(len=1; len<mx*k; len<<=1); memcpy(A,cnt,sizeof(cnt));
NTT(A,1);
memcpy(B,A,sizeof(B));
--k;
int tmp=k;
while(k){
if(k&1){
for(int i=0; i<len; ++i) B[i]=mul(A[i],B[i]);
}
for(int i=0; i<len; ++i) A[i]=mul(A[i],A[i]);
k>>=1;
}
NTT(B,-1); P=998244353;
getwn();
memcpy(A,cnt,sizeof(cnt));
NTT(A,1);
memcpy(C,A,sizeof(C));
k=tmp;
while(k){
if(k&1){
for(int i=0; i<len; ++i) C[i]=mul(A[i],C[i]);
}
for(int i=0; i<len; ++i) A[i]=mul(A[i],A[i]);
k>>=1;
}
NTT(C,-1); for(int i=0; i<len; ++i){
if(B[i] || C[i]) printf("%d ",i);
}
return 0;
}

Codeforces632E Thief in a Shop(NTT + 快速幂)的更多相关文章

  1. CF632E: Thief in a Shop(快速幂&plus;NTT)(存疑)

    A thief made his way to a shop. As usual he has his lucky knapsack with him. The knapsack can contai ...

  2. BZOJ 3992&colon; &lbrack;SDOI2015&rsqb;序列统计 NTT&plus;快速幂

    3992: [SDOI2015]序列统计 Time Limit: 30 Sec  Memory Limit: 128 MBSubmit: 1155  Solved: 532[Submit][Statu ...

  3. 2018&period;12&period;31 bzoj3992&colon; &lbrack;SDOI2015&rsqb;序列统计(生成函数&plus;ntt&plus;快速幂)

    传送门 生成函数简单题. 题意:给出一个集合A={a1,a2,...as}A=\{a_1,a_2,...a_s\}A={a1​,a2​,...as​},所有数都在[0,m−1][0,m-1][0,m− ...

  4. Educational Codeforces Round 9 E&period; Thief in a Shop NTT

    E. Thief in a Shop   A thief made his way to a shop. As usual he has his lucky knapsack with him. Th ...

  5. bzoj 3992&colon; &lbrack;SDOI2015&rsqb;序列统计【原根&plus;生成函数&plus;NTT&plus;快速幂】

    还是没有理解透原根--题目提示其实挺明显的,M是质数,然后1<=x<=M-1 这种计数就容易想到生成函数,但是生成函数是加法,而这里是乘法,所以要想办法变成加法 首先因为0和任何数乘都是0 ...

  6. BZOJ 3992 DP&plus;NTT&plus;快速幂

    思路: 普通的DP很好想吧 f[i][j]+=f[i-1][j*s[k]]  前i个数  mod m=j 的个数 m是质数  模数是质数  这就很有趣了 那么我们就求出来原根  所有的数都取指数 搞出 ...

  7. codeforces632E&period; Thief in a Shop &lpar;dp&rpar;

    A thief made his way to a shop. As usual he has his lucky knapsack with him. The knapsack can contai ...

  8. CF1096&period; G&period; Lucky Tickets&lpar;快速幂NTT&rpar;

    All bus tickets in Berland have their numbers. A number consists of n digits (n is even). Only k dec ...

  9. bzoj 3992 &lbrack;SDOI2015&rsqb;序列统计——NTT(循环卷积&amp&semi;&amp&semi;快速幂)

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3992 有转移次数.模M余数.方案数三个值,一看就是系数的地方放一个值.指数的地方放一个值.做 ...

随机推荐

  1. 洛谷P1156 垃圾陷阱

    动规仍然是难关啊 题目描述 卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中.“垃圾井”是农夫们扔垃圾的地方,它的深度为D(2<=D<=100)英尺. 卡门想 ...

  2. Android&colon;单元测试Junit的配置

    在实际开发中,开发android软件的过程需要不断地进行测试.而使用Junit测试框架,侧是正规Android开发的必用技术,在Junit中可以得到组件,可以模拟发送事件和检测程序处理的正确性.... ...

  3. Android WebView默认GONE出现的问题记录

    前段时间重构一批相似度80%以上的项目[真搞不懂前人们是怎么忍受十几个类似的应用一直CVU的,冗余代码和资源达到40%以上] 其中需要抽出一个公共的带WebView的Activity基类,由于脑残测试 ...

  4. javascript 正则test、exec、search、match区别?

    都可以放正则表达示 exec是RegExp类的匹配方法 match是字符串类的匹配方法 test() 方法用于检测一个字符串是否匹配某个模式.返回 true,否则返回 false. var resul ...

  5. Python学习笔记五

    一. 递归 递归函数: def a (): print ("from b") b() def b(): print("from a ") a() a() 递推和 ...

  6. Object-Oriented(二)原型对象

    自用备忘笔记 1. 理解原型对象 只要创建函数,函数上就会创建一个 prototype 属性指向函数的原型对象. function Person() {} Person.prototype //指向该 ...

  7. jQuery筛选--hasClass&lpar;class&rpar;和eq&lpar;index&vert;-index&rpar;

    hasClass(class) 概述 检查当前的元素是否含有某个特定的类,如果有,则返回true 参数 class  用于匹配的类名 <!DOCTYPE html> <html&gt ...

  8. Material Designer的低版本兼容实现(三)——Color

    在Material Designer中,色彩再一次被摆到了重要的位置上.官方文档中竟然给出了500种配色方案进行选择.就是为了给不同的手机.电视.手表上带来一直的用户体验. 更多用于控制色彩的属性,可 ...

  9. 导入自定义模块model

    编写m2.py,脚本内容如下: #!/usr/bin/python # -*- coding: utf-8 -*- 'its a module test' __author__ = 'mm' impo ...

  10. antDesign DatePicker 禁用日期

    const disabledDate = (current) => { return current < moment().subtract(29, 'days') || current ...