我是靠谱客的博主 无情汽车,这篇文章主要介绍Educational Codeforces Round 9 E. Thief in a Shop(FFT模板题)题意分析Code,现在分享给大家,希望可以做个参考。

题意

  给出一个包含 n n 个数的集合,问从中任取k个(可重复取)求和,可得到的数有哪些。

分析

  这种题一看就是FFT模板题辣!我们只要构造一个多项式,使得第 i i 项的系数为用这些数构成数字i的方案有几种,将这个多项式 k k 次方就可以得到用k个数字来构成这个数的方案数为多少了,只要一次FFT就行了。(注意,如果是NTT的话,模数如果是998244353会被卡WA,所以要用一些不怎么常用的模数)

Code

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #include<bits/stdc++.h> using namespace std; typedef long long ll; bool Finish_read; template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;} template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');} template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('n');} template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);} /*================Header Template==============*/ const ll mod=985661441; namespace { inline ll Pow(ll a,ll b) { ll res=1; while(b) { if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } inline ll Inv(const ll &x) { return Pow(x,mod-2); } inline ll Add(const ll &x,const ll &y) { ll res=x+y; if(res>=mod) res-=mod; return res; } inline ll Sub(const ll &x,const ll &y) { ll res=x-y; if(res<0) res+=mod; return res; } inline ll Mul(const ll &x,const ll &y) { ll res=x*y; if(res>=mod) res%=mod; return res; } inline ll Div(const ll &x,const ll &y) { ll res=x*Inv(y); if(res>=mod) res%=mod; return res; } } namespace Transform { static const int fmaxn=20,Fmaxn=(1<<fmaxn)+1,G=3; int mx=0,rev[Fmaxn],W[fmaxn][Fmaxn]; inline void DFT(int *a,int n) { if(mx<n) { for(int i=mx;i<n;++i) { int len=(1<<i); ll w0=Pow(G,(mod-1)/(len<<1)),w=1; for(int j=0;j<len;++j) W[i][j]=w,w=Mul(w,w0); } mx=n; } rev[0]=0; for(int i=1;i<(1<<n);++i) { rev[i]=i&1?rev[i^1]|(1<<(n-1)):rev[i>>1]>>1; if(i<rev[i]) swap(a[i],a[rev[i]]); } for(int l=0;l<n;++l) { int len=(1<<l); for(int i=0;i<(1<<n);i+=(len<<1)) { for(int j=0;j<len;++j) { int x=a[i+j],y=Mul(a[i+j+len],W[l][j]); a[i+j]=Add(x,y),a[i+j+len]=Sub(x,y); } } } } inline void IDFT(int *a,int n) { reverse(a+1,a+(1<<n)); DFT(a,n); ll invn=Inv((1<<n)); for(int i=0;i<(1<<n);++i) a[i]=Mul(a[i],invn); } } int n,m,v[1005],mx,now[1048577]; int main() { read(n),read(m); for(int i=1;i<=n;++i) read(v[i]),mx=max(mx,v[i]); sort(v+1,v+n+1); n=unique(v+1,v+n+1)-v-1; mx=m*mx; int lim=0; while((1<<lim)<mx) lim++; for(int i=1;i<=n;++i) now[v[i]]=1; Transform::DFT(now,lim); for(int i=0;i<=(1<<lim);++i) now[i]=Pow(now[i],m); Transform::IDFT(now,lim); for(int i=0;i<=(1<<lim);++i) if(now[i]) printf("%d ",i); puts(""); }

最后

以上就是无情汽车最近收集整理的关于Educational Codeforces Round 9 E. Thief in a Shop(FFT模板题)题意分析Code的全部内容,更多相关Educational内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(56)

评论列表共有 0 条评论

立即
投稿
返回
顶部