20200609模拟-pb

pb的场

赛况大概是,xgc会B但wa,写了A的100;rose推C的n=2多拿15pt

全场会A的90pt,唯独我写挂了,原因是想着先用组合数板子过了大样例再改成递推组合数(n=1e9),后来忘了这回事

大部分写B的都是写了45pt,rose写了个65pt直接就过了100(给pb个差评),我的65pt则没调出来

目前七次胡策,就有一次看错题,一次挂题,不愧是我啊

A第一反应是化成$f(x)=\sum_{i=0}^m b_iC_x^i$或下降幂多项式形式,后者我知道有但不会,前面那个记得时可以牛顿插值的,虽然不记得复杂度了……推半天没推出来,最后还是花10min写了个斯特林数的暴力……

想了1h的B并不会,先把C的送分写了,估计一下B的65pt(复杂度与深度有关的档)1h肯定够

1h并没有新的想法,无奈还是只能暴力,写了30min写完,然后调了30min,结果竟然没调出来……明明之前估计的时候已经思考过暴力要怎么写了,然后PKUWC2020的经历也让我仔细思考过怎么写最简洁了,最后居然还是这样的结果

当时是感觉开区间处理会比较靠近正解,但边界有点烦人,赛后还是改回了闭区间,还是调了70min才搞完……

感觉完全就是复刻PKUWC2020啊

不懂啊沃日

rose的代码比我复杂多了,又是写完就过,上一场又是这样,明明也是比我复杂的东西

虽然确实写的途中会发现些问题

可能以后碰到问题,先别急着想怎么修,把所有东西重新想一遍,确认没冲突会好点

然而貌似并没有太多给我试新策略的机会了

A

题意:给定$n \le 1e9$和一个$m \le 1e5$次多项式,求$\sum_{i=0}^n {n \choose i}f(i)$,对998244353取模

请先思考后再展开

转下降幂多项式,即$f(x)=\sum_{i=0}^m b_i x^{\underline i}$,即$f(x)=\sum_{i=0}^m (i!b_i) {x \choose i}$
$$
\sum_{j=0}^m \sum_{i=0}^n (j!b_j) {n \choose i} {i \choose j}
=\sum_{j=0}^m \sum_{i=0}^n (j!b_j) {n \choose j} {n-j \choose i-j}
\\
=\sum_{j=0}^m (j!b_j) {n \choose j} \sum_{i=0}^n {n-j \choose i-j}
=\sum_{j=0}^m (j!b_j) {n \choose j} 2^{n-j}
$$
复杂度在于转下降幂多项式的$O(nlog^2)$

感觉这题太裸了啊,没懂……

不过xgc似乎推出了一次exp的做法

「codechef PKLVES Chef and Elephant Tree」 的加强版

题意:$n \le 3e5$的树,保证存在一种dfs序,使得$dfn_x=x$。q次询问区间$[l,r]$和$k \in [2,10]$,随机生成一个长为k的序列,使得元素都是在区间内的叶子,求其虚树边数的期望

这里的虚树定义为,两侧都有关键点的边集

(原题是k=2,但序列要求不重,懒得改了就没交)

请先思考后再展开

考虑每条边的贡献,记$in_x=子树内,在[l,r]内的叶子数$,那么就是$(\sum [in_x>0])-(\frac{\sum in_x^K}{in_1^K})-\sum ( 1-\frac{in_x}{in_1} )^K$

后面那个用二项式定理展开,$\sum_{i=0}^K {K \choose i} (-1)^i \frac{ \sum in_x^i }{ in_1^i }$,因此问题转化为,求出$\sum_x in_x^k$

询问区间时,记$x=最左叶子,y=最右叶子$

复杂度为$O(q*dep*k)$的65pt暴力:就是预处理出,每个点作为左右端点,向上跳时,同父亲的两侧子树,边数和、叶子数和、贡献和

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
ll pw[12][N];
vc<int> lef;
int ff[N],dep[N],left[N],right[N],siz[N];vc<int> son[N];
int lsum[12][N],rsum[12][N],sum[12][N];
int lsiz[N],rsiz[N];//叶子个数
int le[N],re[N],ee[N];//边数
void pre(int x,int fa)
{
dep[x]=dep[fa]+1;ff[x]=fa;right[x]=x,left[x]=INF;
if(!sz(son[x])) siz[x]=1,left[x]=x,lef.PB(x);
for(auto y:son[x])
{
pre(y,x),chmax(right[x],right[y]),chmin(left[x],left[y]);
lsiz[y]=siz[x],siz[x]+=siz[y];
fo(k,0,10) lsum[k][y]=sum[k][x],add(sum[k][x],sum[k][y]);
le[y]=ee[x],ee[x]+=ee[y]+1;
}
if(sz(son[x])) siz[x]=0,ee[x]=0;fo(k,0,10) sum[k][x]=0;
fd(t,sz(son[x])-1,0)
{
int y=son[x][t];rsiz[y]=siz[x],siz[x]+=siz[y];
fo(k,0,10) rsum[k][y]=sum[k][x],add(sum[k][x],sum[k][y]);
re[y]=ee[x],ee[x]+=ee[y]+1;
}
fo(k,0,10) add(sum[k][x], pw[k][siz[x]] );
}
int ans[12];
void main()
{
PRE();
int type=qread(),n=qread(),q=qread();fo(x,2,n) son[qread()].PB(x);//有序
fo(i,0,n){ pw[0][i]=(i==0?0:1);fo(k,1,10) pw[k][i]=pw[k-1][i]*i%MOD; }
pre(1,0);
for(int lst=0,tim=1;tim<=q;tim++)
{
int x=qread()^(type*lst),y=qread()^(type*lst),K=qread();assert(x<=y);
int id1=lower_bound(all(lef),x)-lef.begin();
int id2=upper_bound(all(lef),y)-lef.begin()-1;
if(id1>id2){ write2(lst=0);continue; } x=lef[id1],y=lef[id2];
mem(ans,0);int ANS=0;
int cnt=0,nowx=siz[x],nowy=siz[y];//叶子总数、子树内叶子数
while(x!=y)
{
if(ff[x]==ff[y])
{
cnt=nowx+nowy+lsiz[y]-lsiz[x]-siz[x];
ANS+=le[y]-le[x]-(ee[x]+1)+2;
fo(k,0,10) add(ans[k], (1ll*lsum[k][y]+MOD-lsum[k][x]+MOD-sum[k][x]+pw[k][nowx]+pw[k][nowy])%MOD );
break;
}
else if(dep[x]>dep[y])
{ fo(k,0,10) add(ans[k],rsum[k][x]),add(ans[k],pw[k][nowx]);nowx+=rsiz[x],ANS+=re[x]+1,x=ff[x]; }
else
{ fo(k,0,10) add(ans[k],lsum[k][y]),add(ans[k],pw[k][nowy]);nowy+=lsiz[y],ANS+=le[y]+1,y=ff[y]; }
}
int iv=invm(cnt),S=ans[K]*invm(pw[K][cnt])%MOD;
for(ll now=1,i=0;i<=K;i++,now=now*iv%MOD) add(S, ans[i]*C(K,i)%MOD*(i&1?MOD-1:1)%MOD*now%MOD );
write2(lst=mm(ANS+MOD-S));
}
}

为了简洁:$in_1$其实应该在叶子节点集合上二分求

写成$(\sum [in_x>0])-\frac{ (\sum in_x^k)+(\sum (in_1-in_x)^k ) }{in_1^k}$

预处理每个点作为左端点、右端点向上跳的权值和这个还是要的,之前那个$\sum_{i=0}^K {K \choose i} (-1)^i \frac{ \sum in_x^i }{ in_1^i }$可以继续用,不过我写的时候选择了$\sum_{i=0}^K {K \choose i} in_1^i (-1)^{K-i} (\sum in_x^i)$,区别不大

不过这些都是无关紧要的,关键还是l和r祖先那些边的贡献怎么算

其实这步我当时真没想到,就很基础的一步——给第i个叶子编号$id_x=i$,然后把上面的left和right(子树内最左和最右的叶子节点)也用这种编号方式存储

对于l的祖先x,贡献就是$(right_x-l+1)^k=\sum_{i=0}^k (1-l)^i*{k \choose i}*right_x^{k-i}$

以及$(in_1-right_x+l-1)^k=\sum_{i=0}^k (in_1+l-1)^i*{k \choose i}*(-1)^{k-i}*right_x^{k-i}$

对于r的祖先x,贡献就是$(r-left_x+1)^k=\sum_{i=0}^k (r+1)^i*{k \choose i}*(-1)^{k-i}*left_x^{k-i}$

以及$(in_1-r+left_x-1)^k=\sum_{i=0}^k (in_1-r-1)^i*{k \choose i}*left_x^{k-i}$

则只需要询问链上$\sum left_x^{i}、\sum right_x^{i}$,树上前缀和就好了

$O((n+q)(k+log))$,正解比暴力简洁+好写很多系列,但依然挺毒瘤的

难顶啊,在上面那份代码的基础上改,都改了30min,调了80min

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
ll pw[12][N];
vc<int> lef;//叶子
int ff[N][20],dep[N],left[N],right[N],siz[N];vc<int> son[N];
ll lsum[12][N],rsum[12][N],sum[12][N];
ll upL[12][N],upR[12][N];//树上前缀和,其中upR存right,upL存left
void pre(int x,int fa)
{
dep[x]=dep[fa]+1;right[x]=0,left[x]=INF;
ff[x][0]=fa;fo(t,1,19) ff[x][t]=ff[ff[x][t-1]][t-1];
if(!sz(son[x])) siz[x]=1,left[x]=right[x]=sz(lef),lef.PB(x);
else
{
for(auto y:son[x])
{
pre(y,x),siz[x]+=siz[y];chmax(right[x],right[y]),chmin(left[x],left[y]);
fo(k,0,10) lsum[k][y]=sum[k][x],add(sum[k][x],sum[k][y]);
}
fo(k,0,10) sum[k][x]=0;
fd(t,sz(son[x])-1,0)
{
int y=son[x][t];
fo(k,0,10) rsum[k][y]=sum[k][x],add(sum[k][x],sum[k][y]);
}
}
fo(k,0,10) add(sum[k][x], pw[k][siz[x]] );
}
void pushdown(int x)//求树上前缀和
{
fo(k,0,10) add(upL[k][x],pw[k][left[x]]),add(upR[k][x],pw[k][right[x]]);
for(auto y:son[x]) {
fo(k,0,10)
add(upL[k][y],upL[k][x]),add(upR[k][y],upR[k][x]),
add(lsum[k][y],lsum[k][x]),add(rsum[k][y],rsum[k][x]);
pushdown(y);
}
}
int getlca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);fd(t,19,0) if(bin(t)<=dep[x]-dep[y]) x=ff[x][t];
if(x==y) return x;fd(t,19,0) if(ff[x][t]!=ff[y][t]) x=ff[x][t],y=ff[y][t];return ff[x][0];
}
int jump(int x,int len){ fd(t,19,0) if(len&bin(t)) x=ff[x][t];return x; }
void main()
{
PRE();fo(i,0,N-1){ pw[0][i]=1;fo(k,1,10) pw[k][i]=pw[k-1][i]*i%MOD; }
int type=qread(),n=qread(),q=qread();fo(x,2,n) son[qread()].PB(x);//有序
pre(1,0);pushdown(1);
for(int lst=0,tim=1;tim<=q;tim++)
{
int x=qread()^(type*lst),y=qread()^(type*lst),K=qread();ass(x<=y);
int id1=lower_bound(all(lef),x)-lef.begin();
int id2=upper_bound(all(lef),y)-lef.begin()-1;
if(id1>=id2){ write2(lst=0);continue; } x=lef[id1],y=lef[id2];
int lca=getlca(x,y),in1=id2-id1+1;ll ans=0;
//计算链上
for(ll base=1-id1,now=1,i=0;i<=K;i++,now=now*base%MOD) ( ans+=now*C(K,i)%MOD*(upR[K-i][x]-upR[K-i][lca]) )%=MOD;
for(ll base=in1+id1-1,now=1,i=0;i<=K;i++,now=now*base%MOD) ( ans+=now*C(K,i)%MOD*(upR[K-i][x]-upR[K-i][lca])%MOD*((K-i)&1?-1:1) )%=MOD;
for(ll base=id2+1,now=1,i=0;i<=K;i++,now=now*base%MOD) ( ans+=now*C(K,i)%MOD*(upL[K-i][y]-upL[K-i][lca])%MOD*((K-i)&1?-1:1) )%=MOD;
for(ll base=in1-id2-1,now=1,i=0;i<=K;i++,now=now*base%MOD) ( ans+=now*C(K,i)%MOD*(upL[K-i][y]-upL[K-i][lca]) )%=MOD;
int upx=jump(x,dep[x]-dep[lca]-1),upy=jump(y,dep[y]-dep[lca]-1);//lca的两个孩子
//计算被完全覆盖,式子中后者
for(ll base=in1,now=1,i=0;i<=K;i++,now=now*base%MOD)
{
ll A=rsum[K-i][x]-rsum[K-i][upx]+
lsum[K-i][y]-lsum[K-i][upy]+
(lsum[K-i][upy]-lsum[K-i][lca])-(lsum[K-i][upx]-lsum[K-i][lca])-sum[K-i][upx];
( ans+=A%MOD*now%MOD*C(K,i)%MOD*((K-i)&1?-1:1) )%=MOD;
}
//计算被完全覆盖,式子中前者
ans+=
rsum[K][x]-rsum[K][upx]+
lsum[K][y]-lsum[K][upy]+
(lsum[K][upy]-lsum[K][lca])-(lsum[K][upx]-lsum[K][lca])-sum[K][upx];
ans=-ans*invm(pw[K][in1])%MOD;
ans+=(y-x)+(dep[x]-dep[lca]);//边数
ans=(ans+MOD)%MOD;write2(lst=ans);
}
}

C

$n \le 20$个球的体积并,保留三位小数

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d469bf92.html
转载请注明出处,谢谢!