CodeChef May Challenge 2018 Division 1 Solutions

前言

大概是退役前最后一次 CC 马拉松了?接下来几个月并不知道有没有时间打。
蹭着几何大原题打到了 rank13 ,多项式依然很菜,突击了好多 SERSUM 的必备知识,却没有时间写。
最后差 10 的 Rating 就可以红了?CC 的 Rating 机制还是 naive 啊,每一场划划水就能慢慢续到红名了。


DBFB

傻逼题不解释。

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
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int P=1000000007;
const int M=100005;
const int N=100005;
int fib[N][2];
int a[M],b[M];
int n,m,T,ans;
int main()
{
freopen("dbfb.in","r",stdin),freopen("dbfb.out","w",stdout);
for (T=read();T--;)
{
m=read(),n=read();
for (int i=1;i<=m;++i) a[i]=read();
for (int i=1;i<=m;++i) b[i]=read();
fib[1][0]=1,fib[2][1]=1;
for (int i=3;i<=n;++i) fib[i][0]=(fib[i-2][0]+fib[i-1][0])%P,fib[i][1]=(fib[i-2][1]+fib[i-1][1])%P;
ans=0;
for (int i=1;i<=m;++i) (ans+=1ll*a[i]*fib[n][0]%P*m%P)%=P,(ans+=1ll*b[i]*fib[n][1]%P*m%P)%=P;
printf("%d\n",ans);
}
fclose(stdin),fclose(stdout);
return 0;
}


FAKEBS

经过的位置是固定的,直接贪心检测就好了。

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <map>
using namespace std;
typedef long long LL;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int buf[30];
inline void write(LL x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}
const int N=100005;
int a[N],b[N];
int T,n,q;
map<int,int> exist;
int main()
{
freopen("fakebs.in","r",stdin),freopen("fakebs.out","w",stdout);
for (T=read();T--;)
{
n=read(),q=read(),exist.clear();
for (int i=1;i<=n;++i) exist[a[i]=read()]=i;
for (int i=1;i<=n;++i) b[i]=a[i];
sort(b+1,b+1+n);
for (int x,l,r,rk,pos,ans0,ans1,cnt0,cnt1;q--;)
{
x=read(),l=1,r=n,rk=0;
for (int mid;l<=r;)
{
mid=l+r>>1;
if (b[mid]<=x) l=(rk=mid)+1;
else r=mid-1;
}
pos=exist[x],l=1,r=n,ans0=ans1=cnt0=cnt1=0;
for (int mid;l<=r;)
{
mid=l+r>>1;
if (pos==mid) break;
if (pos<mid)
{
if (a[mid]<x) ++ans1;
++cnt1,r=mid-1;
}
else
{
if (a[mid]>x) ++ans0;
++cnt0,l=mid+1;
}
}
if (cnt0<rk&&cnt1<=n-rk) write(max(ans0,ans1));
else write(-1);
putchar('\n');
}
}
fclose(stdin),fclose(stdout);
return 0;
}


CHSIGN

发现一些简单的性质然后直接 $dp$。

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
#include <iostream>
#include <climits>
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long LL;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int buf[30];
inline void write(LL x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}
const LL INF=LLONG_MAX>>2;
const int N=100005;
bool f_[N][2],g_[N];
LL f[N][2],g[N];
int a[N],b[N];
int T,n;
inline bool judge(int x)
{
int sum=(x>1?a[x-1]:0)+(x<n?a[x+1]:0);
return sum<a[x];
}
void generatef(int x,bool sig);
void generateg(int x);
void generatef(int x,bool sig)
{
if (!x) return;
b[x]=a[x];
if (x==1) return;
if (sig) generatef(x-1,f_[x][1]);
else
{
b[x-1]=-a[x-1];
if (f_[x][0]) generatef(x-2,1);
else generateg(x-2);
}
}
void generateg(int x)
{
if (!x) return;
b[x]=a[x];
if (x==1) return;
b[x-1]=-a[x-1];
if (g_[x]) generatef(x-2,1);
else generateg(x-2);
}
void dp()
{
for (int i=1;i<=n;++i) f[i][0]=f[i][1]=g[i]=INF;
f[1][0]=g[1]=a[1];
if (a[1]<a[2]) f[2][0]=g[2]=a[2]-a[1];
for (int i=1;i<n;++i)
{
if (f[i+1][1]>f[i][0]+a[i+1]) f[i+1][1]=f[i][0]+a[i+1],f_[i+1][1]=0;
if (f[i+1][1]>f[i][1]+a[i+1]) f[i+1][1]=f[i][1]+a[i+1],f_[i+1][1]=1;
if (!judge(i)) g[i]=INF;
if (i+2>n||a[i+1]>=a[i]||a[i+1]>=a[i+2]) continue;
if (f[i+2][0]>f[i][1]-a[i+1]+a[i+2]) f[i+2][0]=f[i][1]-a[i+1]+a[i+2],f_[i+2][0]=1;
if (g[i+2]>f[i][1]-a[i+1]+a[i+2]) g[i+2]=f[i][1]-a[i+1]+a[i+2],g_[i+2]=1;
if (g[i+2]>g[i]-a[i+1]+a[i+2]) g[i+2]=g[i]-a[i+1]+a[i+2],g_[i+2]=0;
if (f[i+2][0]>g[i]-a[i+1]+a[i+2]) f[i+2][0]=g[i]-a[i+1]+a[i+2],f_[i+2][0]=0;
}
if (!judge(n)) g[n]=INF;
LL ans0=f[n][1],ans1=a[n]>=a[n-1]?INF:f[n-1][1]-a[n],ans2=g[n],ans3=a[n]>=a[n-1]?INF:g[n-1]-a[n];
if (ans0<=ans1&&ans0<=ans2&&ans0<=ans3) generatef(n,1);
else if (ans1<=ans0&&ans1<=ans2&&ans1<=ans3) b[n]=-a[n],generatef(n-1,1);
else if (ans2<=ans0&&ans2<=ans1&&ans2<=ans3) generateg(n);
else b[n]=-a[n],generateg(n-1);
}
int main()
{
freopen("chsign.in","r",stdin),freopen("chsign.out","w",stdout);
for (T=read();T--;)
{
n=read();
for (int i=1;i<=n;++i) a[i]=read();
dp();
for (int i=1;i<=n;++i) write(b[i]),putchar("\n "[i<n]);
}
fclose(stdin),fclose(stdout);
return 0;
}


STMINCUT

直接造一个最大生成树,所有边补齐成路径最大值。
为什么是对的?结合最小割树的性质感受一下(划掉)。

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
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long LL;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int INF=INT_MAX>>1;
const int N=1005;
const int E=N<<1;
const int M=N*N;
int tov[E],nxt[E],len[E];
int a[N][N],d[N][N];
int last[N],fa[N];
int T,n,tot,ecnt;
LL ans;
struct edge
{
int x,y,len;
inline edge (int x_=0,int y_=0,int len_=0){x=x_,y=y_,len=len_;}
inline bool operator<(edge const e)const{return len>e.len;}
}e[M];
inline void insert(int x,int y,int z){tov[++tot]=y,len[tot]=z,nxt[tot]=last[x],last[x]=tot;}
int getfather(int son){return fa[son]==son?son:fa[son]=getfather(fa[son]);}
void Kruscal()
{
sort(e+1,e+1+ecnt);
for (int x=1;x<=n;++x) fa[x]=x;
for (int i=1,x,y,fx,fy;i<=ecnt;++i)
{
fx=getfather(x=e[i].x),fy=getfather(y=e[i].y);
if (fx!=fy) insert(x,y,e[i].len),insert(y,x,e[i].len),fa[fy]=fx;
}
}
void dfs(int x,int fa,int cur,int *d)
{
d[x]=cur;
for (int i=last[x],y;i;i=nxt[i])
if ((y=tov[i])!=fa) dfs(y,x,min(cur,len[i]),d);
}
int main()
{
freopen("stmincut.in","r",stdin),freopen("stmincut.out","w",stdout);
for (T=read();T--;)
{
n=read(),ecnt=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
e[++ecnt]=edge(i,j,a[i][j]=read());
Kruscal();
for (int x=1;x<=n;++x) dfs(x,0,INF,d[x]);
ans=0;
for (int i=1;i<=n;++i)
for (int j=1;j<=n;++j)
if (i!=j) ans+=d[i][j]-a[i][j];
printf("%lld\n",ans);
for (;tot;nxt[tot--]=0);
for (int x=1;x<=n;++x) last[x]=0;
}
fclose(stdin),fclose(stdout);
return 0;
}


EDGEST

中规中矩的很套路的数据结构题。
“中国人玩烂的东西印度人玩。”——不知道谁说的
考虑只有第一个限制,我们可以通过 DFS 序+线段树来做。
加入第二个限制之后,我们通过 DFS +线段树合并来保证第一个限制,至于第二个限制,我们将第二棵树中的边,在第一棵树的对应端点都挂上 $+1$ 标记,在 $lca$ 处挂上 $-2$ 标记。然后处理标记的时候相当于在第二棵树对应位置单点加,查询的时候是路径查询,这个可以写树剖,也可以直接用欧拉序来维护。
时间复杂度 $O(n\log n)$ 吧。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int buf[30];
inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}
const int N=200005;
const int LGN=18;
const int E=N<<1;
const int EL=N<<1;
const int LGEL=19;
const int MAX_EVT=N*3;
int app[N],ext[N],head[N],root[N],LOG[N],ans[N];
int adj[MAX_EVT],stp[MAX_EVT];
bool sig[MAX_EVT];
int T,n,el,evt_cnt;
struct tree
{
int last[N],depth[N];
int anc[N][LGN];
int tov[E],nxt[E];
int tot;
inline void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;}
void dfs(int x)
{
for (int i=last[x],y;i;i=nxt[i])
if ((y=tov[i])!=anc[x][0])
depth[y]=depth[anc[y][0]=x]+1,dfs(y);
}
void pre()
{
for (int i=1;i<=LOG[n];++i)
for (int x=1;x<=n;++x)
anc[x][i]=anc[anc[x][i-1]][i-1];
}
inline int adjust(int x,int h)
{
for (int i=LOG[depth[x]];i>=0;--i) if (depth[anc[x][i]]>=h) x=anc[x][i];
return x;
}
inline int lca(int x,int y)
{
if (depth[x]>=depth[y]) swap(x,y);
y=adjust(y,depth[x]);
if (x==y) return x;
for (int i=LOG[depth[x]];i>=0;--i) if (anc[x][i]!=anc[y][i]) x=anc[x][i],y=anc[y][i];
return anc[x][0];
}
void clear()
{
for (;tot;nxt[tot]=0,--tot);
for (int x=1;x<=n;++x) last[x]=0;
}
}t[2];
inline void add_event(int x,int y,bool delta){adj[++evt_cnt]=y,sig[evt_cnt]=delta,stp[evt_cnt]=head[x],head[x]=evt_cnt;}
void travel(int x)
{
app[x]=++el;
for (int i=t[1].last[x],y;i;i=t[1].nxt[i])
if ((y=t[1].tov[i])!=t[1].anc[x][0])
travel(y);
ext[x]=++el;
}
namespace segment_tree
{
const int V=EL*LGEL;
int son[V][2];
int sum[V];
int tot;
int query(int rt,int st,int en,int l,int r)
{
if (!rt||st>en) return 0;
if (st==l&&en==r) return sum[rt];
int mid=l+r>>1;
if (en<=mid) return query(son[rt][0],st,en,l,mid);
else if (mid+1<=st) return query(son[rt][1],st,en,mid+1,r);
else return query(son[rt][0],st,mid,l,mid)+query(son[rt][1],mid+1,en,mid+1,r);
}
void modify(int &rt,int x,int l,int r,int delta)
{
if (!rt) sum[rt=++tot]=0,son[rt][0]=son[rt][1]=0;
sum[rt]+=delta;
if (l==r) return;
int mid=l+r>>1;
if (x<=mid) modify(son[rt][0],x,l,mid,delta);
else modify(son[rt][1],x,mid+1,r,delta);
}
int merge(int rt0,int rt1)
{
if (!rt0||!rt1) return rt0^rt1;
sum[rt0]+=sum[rt1],son[rt0][0]=merge(son[rt0][0],son[rt1][0]),son[rt0][1]=merge(son[rt0][1],son[rt1][1]);
return rt0;
}
};
inline int query_path(int rt,int x,int y)
{
int z=t[1].lca(x,y);
return segment_tree::query(rt,1,app[x],1,el)+segment_tree::query(rt,1,app[y],1,el)-(segment_tree::query(rt,1,app[z],1,el)<<1);
}
void calc(int x,int e=0)
{
root[x]=0;
for (int i=t[0].last[x],y;i;i=t[0].nxt[i])
if ((y=t[0].tov[i])!=t[0].anc[x][0])
calc(y,i+1>>1),root[x]=segment_tree::merge(root[x],root[y]);
for (int i=head[x],y;i;i=stp[i]) y=adj[i],segment_tree::modify(root[x],app[y],1,el,sig[i]?1:-2),segment_tree::modify(root[x],ext[y],1,el,sig[i]?-1:2);
if (t[0].anc[x][0]) ans[e]=query_path(root[x],x,t[0].anc[x][0]);
}
void cleardata()
{
t[0].clear(),t[1].clear();
for (;evt_cnt;stp[evt_cnt]=0,--evt_cnt);
for (int x=1;x<=n;++x) head[x]=0;
}
int main()
{
freopen("edgest.in","r",stdin),freopen("edgest.out","w",stdout);
for (T=read();T--;cleardata())
{
n=read(),LOG[1]=0;
for (int i=2;i<=n;++i) LOG[i]=LOG[i-1]+(1<<LOG[i-1]+1==i);
for (int s=0;s<2;++s)
{
for (int i=1,x,y;i<n;++i) x=read(),y=read(),t[s].insert(x,y),t[s].insert(y,x);
t[s].depth[1]=1,t[s].dfs(1),t[s].pre();
}
for (int x=2,y;x<=n;++x) y=t[1].anc[x][0],add_event(x,x,1),add_event(y,x,1),add_event(t[0].lca(x,y),x,0);
el=0,travel(1),segment_tree::tot=0,calc(1);
for (int i=1;i<n;++i) write(ans[i]),putchar("\n "[i<n-1]);
}
fclose(stdin),fclose(stdout);
return 0;
}


RUBBER

大原题,这里 有详细讲解。
XIV Open Cup named after E.V. Pankratiev, Grand Prix of Udmurtia, Division 1, Problem B, Black hole
有一道在这个思想上加强的题目
ACM International Collegiate Programming Contest, Japan Domestic Contest, Tokyo, Japan, Problem F, Tighten Up!
考虑现实意义中缩进橡皮筋的过程,其实就是将一些无用的拐角删除。
我们过每个钉子做一条竖直线,分成上下两条射线,对每一条射线编号。
射线穿过多边形折线的时候,在对应位置写上射线的编号。
从任意位置开始按顺序遍历多边形折线,将沿途的编号记录下来,可以发现,所谓的无用的拐角,就是相邻两个一样的数。
每次删掉相邻两个一样的数,如果最后可以拿走橡皮筋,那么一定没有数剩下。使用栈实现一下就好了。
时间复杂度 $O(nm)$。

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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long double db;
const int N=1005;
const int M=3005;
const db EPS=1e-8;
inline bool equ(db x,db y){return fabs(x-y)<EPS;}
inline int sgn(db x){return equ(x,0.)?0:(x<0?-1:1);}
struct P
{
db x,y;
inline P (db x_=0.,db y_=0.){x=x_,y=y_;}
inline bool operator<(P const p)const{return sgn(x-p.x)<0||!sgn(x-p.x)&&sgn(y-p.y)<0;}
inline P operator+(P const p)const{return P(x+p.x,y+p.y);}
inline P operator-(P const p)const{return P(x-p.x,y-p.y);}
inline P operator*(db const k)const{return P(x*k,y*k);}
inline db operator*(P const p)const{return x*p.x+y*p.y;}
inline db operator^(P const p)const{return x*p.y-y*p.x;}
}nail[N],rub[M];
inline P rotate(P p,db a){return P(p.x*cos(a)-p.y*sin(a),p.x*sin(a)+p.y*cos(a));}
int stack[N*M];
int T,n,m,top;
void judge()
{
top=0,rub[0]=rub[m];
for (int i=1;i<=m;++i)
if (sgn(rub[i].x-rub[i-1].x)>0)
for (int j=1;j<=n;++j)
{
if (sgn(rub[i].x-nail[j].x)>0&&sgn(nail[j].x-rub[i-1].x)>0)
{
P p=(rub[i]-rub[i-1])*((nail[j].x-rub[i-1].x)/(rub[i].x-rub[i-1].x))+rub[i-1];
if (sgn(nail[j].y-p.y)>0) stack[++top]=(j<<1)-1;
else stack[++top]=j<<1;
for (;top>1&&stack[top]==stack[top-1];top-=2);
}
}
else
for (int j=n;j>=1;--j)
{
if (sgn(nail[j].x-rub[i].x)>0&&sgn(rub[i-1].x-nail[j].x)>0)
{
P p=(rub[i]-rub[i-1])*((nail[j].x-rub[i-1].x)/(rub[i].x-rub[i-1].x))+rub[i-1];
if (sgn(nail[j].y-p.y)>0) stack[++top]=(j<<1)-1;
else stack[++top]=j<<1;
for (;top>1&&stack[top]==stack[top-1];top-=2);
}
}
}
int main()
{
freopen("rubber.in","r",stdin),freopen("rubber.out","w",stdout);
for (scanf("%d",&T);T--;)
{
scanf("%d",&n);
for (int i=1;i<=n;++i){double x,y;scanf("%lf%lf",&x,&y),nail[i]=rotate(P(x,y),0.233);}
scanf("%d",&m);
for (int i=1;i<=m;++i){double x,y;scanf("%lf%lf",&x,&y),rub[i]=rotate(P(x,y),0.233);}
sort(nail+1,nail+1+n),judge();
printf(top?"NO\n":"YES\n");
}
fclose(stdin),fclose(stdout);
return 0;
}


SERSUM

这道题集齐了目前为止学过的几乎所有的多项式/生成函数姿势(还有不少是临时突击的)。
式子其实很好推:
$$
\begin{align}
f(x,k)&=\sum_{i=1}^n(x+a_i)^k\\
&=\sum_{i=1}^n\sum_{j=0}^kx^ja_i^{k-j}{k\choose j}\\
&=\sum_{j=0}^kx^j{k\choose j}\sum_{i=1}^na_i^{k-j}
\end{align}
$$记 $f_k=\sum_{i=1}^na_i^k$,我们有 $f(x,k)=\sum_{j=0}^kx^j{k\choose j}f_{k-j}$。
然后继续推:
$$
\begin{align}
g(t,k)&=\sum_{i=0}^tf(i,k)\\
&=\sum_{i=0}^t\sum_{j=0}^ki^j{k\choose j}f_{k-j}\\
&=\sum_{j=0}^k{k\choose j}f_{k-j}\sum_{i=0}^ti^j
\end{align}
$$记 $S_k=\sum_{i=0}^ti^k$,我们有 $g(t,k)=\sum_{j=0}^k{k\choose j}f_{k-j}S_j$。
如果我们可以算出 $f_i$ 和 $S_i$ 的值,那么求 $g(t,0…k)$ 就是一个卷积搞定。
先来看求 $S_i$,这个是个经典问题,考虑使用 Bernoulli 数:
$$
\sum_{i=0}^{n-1}i^k=\frac1{k+1}\sum_{i=0}^k{k+1\choose i}B_in^{k+1-i}
$$要求出 $0…n-1$ 的所有自然数 $0…k$ 次幂之和,依然是一个卷积搞定。
然后比较难的是求出 $f_i$,即给定序列所有元素的次幂和。这个其实就是 THUPC2017 的 I 题 sum
定义 $g_i$ 表示从序列中选出 $i$ 个不同元素的乘积之和(当 $i>n$ 时为 $0$),这个可以使用分治 FFT 来预处理。
考虑容斥意义可以得到$$f_n=\sum_{i=1}^{n-1}(-1)^{i-1}g_if_{n-i}+(-1)^{n-1}ng_n$$考虑使用生成函数,令 $F(x)=\sum_{i=1}^nf_ix^i,G(x)=\sum_{i=1}^n(-1)^{i-1}g_ix^i,H(x)=\sum_{i=1}^n(-1)^{i-1}ig_ix^i$,于是我们就有 $F(x)=F(x)G(x)+H(x)$,即$$F(x)=\frac{H(x)}{1-G(x)}$$多项式求逆即可。
那么所有问题就圆满解决了,至于 FFT,当然是选择写毛爷爷的 4 次 DFT 式任意模数 FFT 啦!
时间复杂度 $O(n\log^2n+K\log K)$。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
typedef long long LL;
typedef long double db;
template <typename T>
inline T read()
{
T x=0,f=1;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
return x*f;
}
int buf[30];
inline void write(int x)
{
if (x<0) putchar('-'),x=-x;
for (;x;x/=10) buf[++buf[0]]=x%10;
if (!buf[0]) buf[++buf[0]]=0;
for (;buf[0];putchar('0'+buf[buf[0]--]));
}
const db pi=acos(-1);
const int P=1000000007;
const int MAXK=50005;
const int N=100005;
const int LG=18;
const int L=1<<LG;
int trs[L],f[L],Ber[L],S[L],tmp[L],g[LG][L];
int fact[MAXK],invf[MAXK],pw[MAXK];
int a[N];
int n,K,T,len;
struct Z
{
db x,y;
inline Z (db x_=0.,db y_=0.){x=x_,y=y_;}
inline Z operator+(Z const z)const{return Z(x+z.x,y+z.y);}
inline Z operator-(Z const z)const{return Z(x-z.x,y-z.y);}
inline Z operator*(Z const z)const{return Z(x*z.x-y*z.y,x*z.y+y*z.x);}
inline Z operator/(db const k)const{return Z(x/k,y/k);}
}omega[L+5],A[L+5],B[L+5],C[2][L+5],t[L+5];
inline Z conj(Z p){return Z(p.x,-p.y);}
inline int quick_power(int x,int y)
{
int ret=1;
for (;y;y>>=1,x=1ll*x*x%P) if (y&1) ret=1ll*ret*x%P;
return ret;
}
void pre()
{
fact[0]=1;
for (int i=1;i<=K+1;++i) fact[i]=1ll*fact[i-1]*i%P;
invf[K+1]=quick_power(fact[K+1],P-2);
for (int i=K+1;i>=1;--i) invf[i-1]=1ll*invf[i]*i%P;
pw[0]=1;
for (int i=1;i<=K+1;++i) pw[i]=1ll*pw[i-1]*T%P;
}
void FFT_pre(){for (int i=0;i<=L;++i) omega[i]=Z(cos(2.*pi*i/L),sin(2.*pi*i/L));}
void deg_pre(int deg)
{
for (len=1;len<deg;len<<=1);
for (int i=0,ret;i<len;++i)
{
ret=0;
for (int x=i,j=1;j<len;j<<=1,x>>=1) ret=(ret<<1)|(x&1);
trs[i]=ret;
}
}
void DFT(Z *a,int sig)
{
for (register int i=0;i<len;++i) t[trs[i]]=a[i];
for (register int l=2;l<=len;l<<=1)
for (register int h=l>>1,j=0;j<len;j+=l)
for (register int i=0;i<h;++i)
{
Z u=t[i+j],v=t[i+j+h]*omega[sig>0?L/l*i:L-L/l*i];
t[i+j]=u+v,t[i+j+h]=u-v;
}
for (register int i=0;i<len;++i) a[i]=t[i];
if (sig<0) for (register int i=0;i<len;++i) a[i]=a[i]/len;
}
void merge()
{
for (int i=0,j;i<len;++i)
{
j=(len-i)&(len-1);Z a1=(A[i]+conj(A[j]))*Z(.5,0),a0=(A[i]-conj(A[j]))*Z(0,-.5),b1=(B[i]+conj(B[j]))*Z(.5,0),b0=(B[i]-conj(B[j]))*Z(0,-.5);
Z dftc0=a0*b0,dftc1=a0*b1,dftc2=a1*b0,dftc3=a1*b1;
C[0][i]=dftc1+dftc0*Z(0,1),C[1][i]=dftc3+dftc2*Z(0,1);
}
}
void trans(int *c)
{
for (int i=0;i<len;++i)
{
int c1=(LL)(C[0][i].x+.5)%P,c0=(LL)(C[0][i].y+.5)%P,c3=(LL)(C[1][i].x+.5)%P,c2=(LL)(C[1][i].y+.5)%P;
c[i]=(c0+((LL)(c1+c2)<<15)+((LL)c3<<30))%P;
}
}
void FFT(int *a,int *b,int *c)
{
for (int i=0;i<len;++i) A[i]=Z(a[i]>>15,a[i]&32767),B[i]=Z(b[i]>>15,b[i]&32767);
DFT(A,1),DFT(B,1),merge(),DFT(C[0],-1),DFT(C[1],-1),trans(c);
}
void polynomial_inverse(int *a,int *b,int deg)
{
if (deg==1){b[0]=quick_power(a[0],P-2);return;}
int deg_=deg+1>>1;polynomial_inverse(a,b,deg_);
deg_pre((deg<<1)-1),copy(a,a+deg,tmp),fill(tmp+deg,tmp+len,0),FFT(tmp,b,tmp);
for (int i=0;i<len;++i) A[i]=Z(tmp[i]>>15,tmp[i]&32767);
DFT(A,1),merge(),DFT(C[0],-1),DFT(C[1],-1),trans(tmp);
for (int i=0;i<len;++i) b[i]=((b[i]<<1)+P-tmp[i])%P;
fill(b+deg,b+len,0);
}
void calc_Bernoulli()
{
for (int i=0;i<=K;++i) f[i]=invf[i+1];
polynomial_inverse(f,Ber,K+1);
}
void calc_S()
{
f[0]=0;
for (int i=1;i<=K+1;++i) f[i]=1ll*pw[i]*invf[i]%P;
deg_pre(K+1<<1|1),FFT(Ber,f,S);
for (int i=0;i<=K;++i) S[i]=1ll*S[i+1]*fact[i]%P;
fill(S+K+1,S+len,0);
}
void solve(int l,int r,int cur=0)
{
if (l==r){g[cur][0]=1,g[cur][1]=a[l];return;}
int mid=l+r>>1,deg=r-l+2,deg0=mid-l+2,deg1=r-mid+1;
solve(l,mid,cur+1),copy(g[cur+1],g[cur+1]+deg0,g[cur]);
solve(mid+1,r,cur+1),deg_pre(deg),fill(g[cur]+deg0,g[cur]+len,0),fill(g[cur+1]+deg1,g[cur+1]+len,0);
FFT(g[cur],g[cur+1],g[cur]);
}
inline int sig(int x){return x&1?P-1:1;}
void calc_f()
{
solve(1,n),g[1][0]=1;
for (int i=1;i<=n&&i<=K;++i) g[1][i]=1ll*g[0][i]*sig(i)%P;
for (int i=n+1;i<=K;++i) g[1][i]=0;
memset(f,0,sizeof f),polynomial_inverse(g[1],f,K+1),g[1][0]=0;
for (int i=1;i<=n&&i<=K;++i) g[1][i]=1ll*i*(P-sig(i))%P*g[0][i]%P;
for (int i=n+1;i<=K;++i) g[1][i]=0;
deg_pre(K<<1|1),fill(g[1]+K+1,g[1]+len,0),fill(f+K+1,f+len,0),FFT(g[1],f,f),f[0]=n,fill(f+K+1,f+len,0);
}
void calc()
{
for (int i=0;i<=K;++i) S[i]=1ll*S[i]*invf[i]%P,f[i]=1ll*f[i]*invf[i]%P;
deg_pre(K<<1|1),fill(f+K+1,f+len,0),FFT(f,S,f);
for (int i=0;i<=K;++i) f[i]=1ll*f[i]*fact[i]%P;
}
int main()
{
freopen("sersum.in","r",stdin),freopen("sersum.out","w",stdout);
n=read<int>(),K=read<int>(),T=(read<LL>()+1)%P;
for (int i=1;i<=n;++i) a[i]=read<int>();
pre(),FFT_pre(),calc_Bernoulli(),calc_S(),calc_f(),calc();
for (int i=0;i<=K;++i) write(f[i]),putchar("\n "[i<K]);
fclose(stdin),fclose(stdout);
return 0;
}