12.20的zyy辣鸡模拟赛

下一场要开始了上场还没个总结也不太好。

那就总结一下吧:辣鸡比赛。

t1:http://www.lydsy.com/JudgeOnline/problem.php?id=3286

一眼矩阵快速幂啊。

两眼高精度。

三眼十进制快速幂。

然鹅我是瞎了所以只看了两眼。看看时限然后非常自信的。。获得了70分。

满分程序:

1
日后再放(没带回家我也很绝望啊喂

t2:维护一颗树,支持链加斐波那契序列,子树求和,链求和,返回第k次操作后的状态,强制在线。

我记得很久以前杰尼龟给我讲过一个区间加斐波那契的题。大概就是可以lazy出每个区间开头的两个元素。。

反着怎么办?反着再搞一遍。

日后这题只要套个树剖套个主席树就可以了。

比赛结束之后码了足足两天。代码6k左右

不过标算可能和我的不太一样啊。

zyy直接搞斐波那契通项公式的啊。

cc的题。

r爷:下次出题能不能不要找cc的题啊,至少不要找我做过的。我才不想把一坨我吃过的屎再吃一边!(全场 笑

满分程序:

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
#include<bits/stdc++.h>
#define int long long
int n,q,zyy,ans,ff[1000000][2],sum[20000000],l[20000000],r[20000000],kk,x,y,c,tt[1000000],sum1,faq[1000000],ffk[1000000][21];
int a[1000000][2],last[1000000],fh[1000000],d[1000000],ma[1000000],dee[1000000],fhh[1000000],dfn[1000000],low[1000000],kkk;
struct lsg{int a[2][2];}fk[1000000];
struct lsg1{int a0,a1;}lazyl[20000000],lazyr[20000000],zero,need;
inline int read(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return kk*k;
}inline int read1(){
char c=getchar();while (c!='-'&&(c<'0'||c>'9'))c=getchar();
int k=0,kk=1;if (c=='-')c=getchar(),kk=-1;
while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();return (kk*k+ans)%n+1;
}using namespace std;
void write(int x){if (x)write(x/10),putchar(x%10+'0');}
void writeln(int x){write(x);if (x==0)putchar('0');puts("");}
inline lsg1 chen(lsg1 x,lsg y){
lsg1 kkk;kkk.a0=(x.a0*y.a[0][0]+x.a1*y.a[1][0])%zyy;
kkk.a1=(x.a0*y.a[0][1]+x.a1*y.a[1][1])%zyy;
return kkk;
}inline lsg1 jia(lsg1 x,lsg1 y){lsg1 kkk;kkk.a0=(x.a0+y.a0)%zyy;kkk.a1=(x.a1+y.a1)%zyy;return kkk;}
inline int suan(lsg1 x,int y){return (x.a0*ff[y][0]%zyy+x.a1*ff[y][1]%zyy)%zyy;}
int findit(int x,int y,int d,int ll,int rr){
if (x>y||d==0)return 0;if (x<=ll&&y>=rr)return sum[d];
int ans,m=(ll+rr)/2,kk=min(rr,y)-max(ll,x)+1;
lsg1 ddd=jia(chen(lazyl[d],fk[max(0ll,x-ll)]),chen(lazyr[d],fk[max(0ll,rr-y)]));
ans=suan(ddd,kk);
if (x<=m)ans+=findit(x,y,l[d],ll,m);
if (y>m)ans+=findit(x,y,r[d],m+1,rr);return ans%zyy;
}void putit1(int x,int y,int d,int dd,int ll,int rr){
l[d]=l[dd];r[d]=r[dd];sum[d]=sum[dd];lazyl[d]=lazyl[dd];lazyr[d]=lazyr[dd];
if (x<=ll&&y>=rr){
lazyl[d]=jia(lazyl[d],need);sum1+=rr-ll+1;need=chen(need,fk[rr-ll+1]);
sum[d]=(sum[l[d]]+sum[r[d]]+suan(jia(lazyl[d],lazyr[d]),rr-ll+1))%zyy;return;
}int m=(ll+rr)/2;if (x<=m){
l[d]=++kk;putit1(x,y,l[d],l[dd],ll,m);
}if (y>m){
r[d]=++kk;putit1(x,y,r[d],r[dd],m+1,rr);
}sum[d]=(sum[l[d]]+sum[r[d]]+suan(jia(lazyl[d],lazyr[d]),rr-ll+1))%zyy;
}void putit2(int x,int y,int d,int dd,int ll,int rr){
l[d]=l[dd];r[d]=r[dd];sum[d]=sum[dd];lazyl[d]=lazyl[dd];lazyr[d]=lazyr[dd];
if (x<=ll&&y>=rr){
lazyr[d]=jia(lazyr[d],need);need=chen(need,fk[rr-ll+1]);
sum[d]=(sum[l[d]]+sum[r[d]]+suan(jia(lazyl[d],lazyr[d]),rr-ll+1))%zyy;return;
}int m=(ll+rr)/2;if (y>m){
r[d]=++kk;putit2(x,y,r[d],r[dd],m+1,rr);
}if (x<=m){
l[d]=++kk;putit2(x,y,l[d],l[dd],ll,m);
}sum[d]=(sum[l[d]]+sum[r[d]]+suan(jia(lazyl[d],lazyr[d]),rr-ll+1))%zyy;
}inline lsg chem(lsg x,lsg y){
lsg kkk;for (int i=0;i<2;i++)for (int j=0;j<2;j++)kkk.a[i][j]=0;
for (int k=0;k<2;k++)
for (int i=0;i<2;i++)
for (int j=0;j<2;j++)(kkk.a[i][j]+=x.a[i][k]*y.a[k][j]%zyy)%=zyy;
return kkk;
}void dfs1(int x,int fa,int de){
dee[x]=de;fh[x]=fa;d[x]=1;ffk[x][0]=fa;
for (int i=last[x];i;i=a[i][0])if (a[i][1]!=fa){
dfs1(a[i][1],x,de+1);d[x]+=d[a[i][1]];ma[x]=d[ma[x]]>d[a[i][1]]?ma[x]:a[i][1];
}
}void dfs2(int x,int fa){
if (ma[fa]==x)fhh[x]=fhh[fa];else fhh[x]=x;dfn[x]=++kkk;
if (ma[x])dfs2(ma[x],x);for (int i=last[x];i;i=a[i][0])
if (a[i][1]!=fa&&a[i][1]!=ma[x])dfs2(a[i][1],x);
low[x]=kkk;
}int lca(int x,int y){
while (x!=y){
if (dee[fhh[x]]<dee[fhh[y]]||dee[fhh[x]]==dee[fhh[y]]&&dee[x]<dee[y])swap(x,y);
if (fhh[x]==fhh[y])x=y;
else if (fhh[x]==x)x=fh[x];
else x=fhh[x];
}return x;
}void findl(int x,int y,int t){
ans=0;tt[t]=tt[t-1];while (1){
if (dee[fhh[x]]<dee[fhh[y]]||dee[fhh[x]]==dee[fhh[y]]&&dee[x]<dee[y])swap(x,y);
if (fhh[x]==fhh[y]){(ans+=findit(dfn[y],dfn[x],tt[t],1,n))%=zyy;break;}
else if (fhh[x]==x)(ans+=findit(dfn[x],dfn[x],tt[t],1,n))%=zyy,x=fh[x];
else {(ans+=findit(dfn[fhh[x]],dfn[x],tt[t],1,n))%=zyy;x=fh[fhh[x]];}
}writeln(ans);
}void putl(int x,int y,int t){
int dd=tt[t-1],z=lca(x,y),l=1,r=dee[x]+dee[y]-2*dee[z]+1,ddd=dd;
int xx=0,yy=l-1;while (1){
dd=++kk;if (fhh[x]==fhh[y]){
need=chen(zero,fk[l-1]);
if (dfn[x]<=dfn[y])putit1(dfn[x],dfn[y],dd,ddd,1,n);
else putit2(dfn[y],dfn[x],dd,ddd,1,n);break;
}if (dee[fhh[x]]<dee[fhh[y]]||dee[fhh[x]]==dee[fhh[y]]&&dee[x]<dee[y]){//y向上
if (fhh[y]==y){
r--;need=chen(zero,fk[r]);putit1(dfn[y],dfn[y],dd,ddd,1,n);y=fh[y];
}else{
r-=dee[y]-dee[fhh[y]]+1;need=chen(zero,fk[r]);putit1(dfn[fhh[y]],dfn[y],dd,ddd,1,n);y=fh[fhh[y]];
}
}else{//x向上
if (fhh[x]==x){
need=chen(zero,fk[l-1]);l++;putit2(dfn[x],dfn[x],dd,ddd,1,n);x=fh[x];
}else{
need=chen(zero,fk[l-1]);l+=dee[x]-dee[fhh[x]]+1;putit2(dfn[fhh[x]],dfn[x],dd,ddd,1,n);x=fh[fhh[x]];
}
}ddd=dd;
}tt[t]=dd;
}void doit(int x,int y){a[++kk][0]=last[x];a[kk][1]=y;last[x]=kk;}
int doit233(int x,int y){for (int i=20;i>=0;i--)if (dee[ffk[x][i]]>dee[y])x=ffk[x][i];return x;}
signed main(){
freopen("gay.in","r",stdin);freopen("gay.out","w",stdout);
n=read();q=read();zyy=1e9+9;
for (int i=1;i<n;i++)x=read(),y=read(),doit(x,y);kk=0;dfs1(1,0,1);dfs2(1,0);
fk[0].a[0][0]=fk[0].a[1][1]=1;fk[1].a[0][0]=fk[1].a[1][0]=fk[1].a[0][1]=1;faq[0]=faq[1]=1;
for (int i=2;i<=n;i++)fk[i]=chem(fk[i-1],fk[1]);zero.a0=1;ff[1][0]=1;
for (int i=1;i<=20;i++)for (int j=1;j<=n;j++)ffk[j][i]=ffk[ffk[j][i-1]][i-1];
for (int i=2;i<=n;i++){
ff[i][0]=(1+ff[i-1][0]+ff[i-2][0])%zyy;
ff[i][1]=ff[i-1][0];faq[i]=(faq[i-1]+faq[i-2])%zyy;
}for (int i=1;i<=q;i++){
c=read();if (c==1){
x=read1();y=read1();tt[i]=tt[i-1];
if (x==y)ans=sum[tt[i]];
else if (!(dfn[y]<=dfn[x]&&low[y]>=low[x]))ans=findit(dfn[y],low[y],tt[i],1,n);
else x=doit233(x,y),ans=(sum[tt[i]]-findit(dfn[x],low[x],tt[i],1,n)+zyy)%zyy;
writeln(ans);
}else if (c==2){
x=read1();y=read1();findl(x,y,i);
}else if (c==3){
x=read1();y=read1();putl(x,y,i);
}else tt[i]=tt[read()];
}
}
/*
5 5
1 2
2 3
3 4
4 5
3 1 5
2 2 4
3 5 1
2 1 5
1 5 4
*/

t3是个辣鸡提答

据说是因为zyy把原题标算叉掉了然后有个绝妙的做法被原题卡t了才选择用提答的方式的。

数据对最后10分钟开始打暴力的人非常不友好。

因为有个点暴力要跑5分钟。

大概就是随机图的最小生成树,每个点向前5个点随机连5条边。因为随机的方式非常萎所以是有性质的。

bzoj月赛题我懒得找了请自己翻。

标算好像是前50个点后50个点搞一下kus,然后中间的直接根据性质矩阵快速幂。

有人总结,三个矩阵快速幂,两个斐波那契,一个毒瘤数据结构,一场辣鸡题啊。

他说的很有道理我就不做补充了。

分享到