HNTT2018 糊做

\color{red}{11\ of\ 18\ solved.}

Day 1

Tree

Description

有一棵节点个数为 n 的树,节点 i 有权值 w_{u} ,最开始根为节点 1
现在有 3 种类型的操作:

1 root: 将根设为 root。
2 u v x: 设 u,v 的最近公共祖先为 p ,将 p 的子树中的所有点的权值加上 x
3 u: 查询节点 u 子树中所有点的权值和。

对于每个 3 操作,输出答案。

Constraints

1\le n,q\le 3\times 10^{5},-10^{7}\le w_{i},x\le 10^{7}

Analysis

比较水的数据结构题。。。讨论当前根与被操作节点的位置关系确定操作区间是否取补集。
对于操作 2 中的 lca,讨论 \operatorname{lca}(u, v),\operatorname{lca}(u,root),\operatorname{lca}(v,root) 的位置关系即可。
我一开始不信邪非要大讨论一堆位置关系于是 WA 了一天 qaq...

时间复杂度 O(n \log{n})

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
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
#include<cstdio>
#include<algorithm>

using i64=long long;
using uchar=unsigned char;

constexpr int maxn(300000);

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

constexpr int OSIZE(65536);
unsigned char obuf[OSIZE+128];
constexpr unsigned char *OT(obuf+OSIZE);

struct IOManager{

IOManager():OS(obuf-1){}
~IOManager(){fwrite(obuf,1,OS-obuf+1,stdout);fclose(stdout);}

inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc(),w=0;
for(;c<48;c=gc())
c==45&&(w=1);
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return w?-s:s;
}

unsigned char *OS;

inline void Flush(){fwrite(obuf,1,OS-obuf+1,stdout);OS=obuf-1;}

inline IOManager&operator<<(const unsigned char&c)
{if(OS>OT)Flush();return(*++OS=c,*this);}

inline IOManager&operator<<(const char&c)
{if(OS>OT)Flush();return(*++OS=c,*this);}

template<typename _Tp>
inline IOManager&operator<<(_Tp s){
static unsigned char ostk[30],*top=ostk;
static _Tp y;
if(OS>OT)Flush();
if(s){
if(s<0)*++OS='-',s=-s;
for(;s;*++top=s-y*10+48,s=y)
y=s/10;
for(;top!=ostk;)
*++OS=*top--;
}else*++OS='0';
return*this;
}
};
}IOManager::IOManager io;

struct Edge{
int v;Edge*las;

inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}*las[maxn+1];

inline void lnk(){
static Edge pool[maxn<<1],*alc=pool-1;
const int u=io,v=io;
las[u]=(++alc)->init(v,las[u]);
las[v]=(++alc)->init(u,las[v]);
}

int idx,
s[maxn+1],
t[maxn+1],
lis[maxn+1],
dep[maxn+1],
son[maxn+1],
p[maxn+1],
top[maxn+1];
int w[maxn+1];

int vec[maxn+1],
*vidx=vec,
*vs[maxn+1],
*vt[maxn+1];

void predecomp(const int&u){
t[u]=1;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=p[u]){
p[o->v]=u;
dep[o->v]=dep[u]+1;
predecomp(o->v);
t[u]+=t[o->v];
if(t[son[u]]<t[o->v])
son[u]=o->v;
}
}

void decomp(const int&u,const int&tp){
top[u]=tp;
lis[s[u]=++idx]=u;

if(son[u])
decomp(son[u],tp);

for(Edge*o=las[u];o;o=o->las)
if(o->v!=p[u]&&o->v!=son[u])
decomp(o->v,o->v);
t[u]=idx;

vs[u]=vidx+1;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=p[u])
*++vidx=s[o->v];
vt[u]=vidx+1;
}

inline bool isanc(const int&u,const int&v)
{return s[u]<=s[v]&&t[v]<=t[u];}

inline int lca(int u,int v){
for(;top[u]!=top[v];dep[top[u]]<dep[top[v]]?v=p[top[v]]:u=p[top[u]]);
return dep[u]<dep[v]?u:v;
}

int ql,qr,qd;i64 qans;
struct Node{
Node *ls,*rs;
i64 v,tag;

Node():ls(nullptr),rs(nullptr),v(0),tag(0){}

static inline Node* newnode();

inline void update()
{v=ls->v+rs->v;}
template<typename _Tp>
inline void updit(const int&l,const _Tp&d)
{v+=(i64)d*l;tag+=d;}
inline void pushdown(const int&l,const int&m,const int&r){
if(tag){
ls->updit(m-l+1,tag);
rs->updit(r-m,tag);
tag=0;
}
}

void setup(const int&l,const int&r){
if(l==r)
return(void)(v=w[lis[l]]);
const int m=(l+r)>>1;
ls=newnode();ls->setup(l,m);
rs=newnode();rs->setup(m+1,r);
update();
}

void update(const int&l,const int&r){
if(ql<=l&&r<=qr)
return updit(r-l+1,qd);
const int m=(l+r)>>1;
pushdown(l,m,r);
if(ql<=m)
ls->update(l,m);
if(m<qr)
rs->update(m+1,r);
update();
}

void query(const int&l,const int&r){
if(ql<=l&&r<=qr)
return(void)(qans+=v);
const int m=(l+r)>>1;
pushdown(l,m,r);
if(ql<=m)
ls->query(l,m);
if(m<qr)
rs->query(m+1,r);
}
};
Node ndpool[maxn<<1],*ndalc=ndpool-1;
inline Node* Node::newnode()
{return++ndalc;}

#define subsum(u) (tmp=u,ql=s[tmp],qr=t[tmp],qans=0,rt->query(1,n),qans)
#define subupd(u) (tmp=u,ql=s[tmp],qr=t[tmp],rt->update(1,n))

int main(){
const int n=io;int q=io;
for(int i=1;i<=n;++i)
w[i]=io;
for(int i=n-1;i;--i)
lnk();

predecomp(1);decomp(1,1);
Node*rt=Node::newnode();
rt->setup(1,n);
for(int i=1;i<=n;++i)
if(vs[i]<vt[i]-1)
std::sort(vs[i],vt[i]);

for(int root=1,tmp;q;--q){
const int opt=io,u=io;
if(opt==1)
root=u;
else if(opt==2){
const int mu=lca(u,root)^lca(u,v)^lca(root,v);
if(mu==root)
rt->updit(n,qd);
else if(isanc(mu,root))
rt->updit(n,qd),qd=-qd,
subupd(lis[*(std::upper_bound(vs[mu],vt[mu],s[root])-1)]);
else subupd(mu);
}else if(u==root)
io<<rt->v<<'\n';
else if(isanc(u,root))
io<<rt->v-subsum(lis[*(std::upper_bound(vs[u],vt[u],s[root])-1)])<<'\n';
else io<<subsum(u)<<'\n';
}

return 0;
}

Function

Description

给定一个长度为 n 的数组 A ,定义二元函数 f(x, y)

f(x, y)=\begin{cases} A_{y} & x=1 \\ f(x - 1, y)+A_{y} & y=1\operatorname{and} x\ne 1 \\ \min\left(f(x - 1, y - 1),f(x - 1, y)\right)+A_{y} & otherwise \end{cases}

q 个询问,每次询问给出 x,y ,求 f(x, y) 的值。

Constraints

1\le n,q\le 5\times 10^{5},0\le A_{i}\le 10^{9},1\le x\le 10^{9},1\le y\le n

Analysis

可以发现 f(x, y) 就是从 y 位置往左走,每走到一个位置 i 就可以取并至少取一次 A_{i} ,总共取 x 次,问取得数的和最小是多少。
容易知道在最优策略中最后取的那个数一定是走过的数中最小的一个,并且除了最后取的数之外的数都只会取一次.
列出式子有:

f(x, y)=\min\left\{s_{y}-s_{i}+ (x-y+i) A_{i}\right\}

其中 s 为数组 A 的前缀和。

若走到点 j 比走到点 k 更优,则有:

\begin{aligned} s_{y} - s_{j} + (x - y + j) A_{j} &< s_{y} - s_{k} + (x - y + k) A_{k} \\ -s_{j} + jA_{j} + xA_{j} - (-s_{k} + kA_{k} + xA_{k}) &< (A_{j} - A_{k}) y \\ \frac{-s_{j} + jA_{j} - (-s_{k} + kA_{k})}{A_{j} - A_{k}} &< y - x \end{aligned}

使用斜率优化即可。对于每次询问在维护的下凸包上二分找到第一条斜率 \ge y - x 的线段并取其左端点作为决策点即可。
A_{i} 关于 i 不单调?不会 CDQ 怎么办啊 qaq
注意到在最优策略中,走到一个点时,若继续往左走,则必定会停在一个比当前点低的点,那么使栈中元素单调就可以了。
二分姿势各种不对调了一天半才过...qaq

时间复杂度 O(n \log{n})

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
#include<cstdio>

using i64=long long;
using ld=long double;

constexpr int maxn(500000);
constexpr int maxq(500000);

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

struct Edge{
int l,idx;Edge*las;

inline Edge* init(const int&x,const int&id,Edge*const&ls)
{return l=x,idx=id,las=ls,this;}
}*las[maxn+1],pool[maxq],*alc=pool-1;

int a[maxn+1],
stk[maxn+1];
i64 s[maxn+1],
f[maxn+1],
ans[maxn+1];

inline bool chkslope(const int&l,const int&m,const int&r)
{return(ld)(f[r]-f[m])*(a[m]-a[l])<(ld)(f[m]-f[l])*(a[r]-a[m]);}
inline i64 calc(const int&l,const int&r,const int&len)
{return s[r]-s[l]+(i64)a[l]*(len-r+l);}

int main(){
const int n=io;i64 v=0;
for(int i=1;i<=n;++i)
v+=(a[i]=io),
s[i]=v,
f[i]=(i64)a[i]*i-v;
const int q=io;
for(int i=0,x,y;i!=q;++i)
x=io,y=io,
las[y]=(++alc)->init(x,i,las[y]);

for(int i=1,*top=stk;i<=n;++i){
for(;top!=stk&&a[i]<=a[*top];--top);
for(;stk+1<top&&chkslope(*(top-1),*top,i);--top);
*++top=i;

for(Edge*o=las[i];o;o=o->las){
int l=1,r=top-stk-1;
for(int m;l<=r;)
m=(l+r+1)>>1,
calc(stk[m],i,o->l)<=calc(stk[m+1],i,o->l)?r=m-1:(l=m+1);
ans[o->idx]=calc(stk[l],i,o->l);
}
}

for(int i=0;i!=q;++i)
printf("%lld\n",ans[i]);

return 0;
}

Or

Description

对于一个长度为 n 的正整数序列 A ,定义序列 B

B_{i}=\begin{cases} A_{1} & i=1 \\ A_{i}\operatorname{or}B_{i-1} & i\in[2, n] \end{cases}

其中 \operatorname{or} 表示位或运算。

一个序列 A 是合法的,当且仅当其满足: \forall i\in[1, n]:A_{i}\in\left[1,2^{k}\right),\forall i\in\left(1,n\right]:B_{i}>B_{i-1}
求合法的序列 A 的个数。

两个序列 S,T 被认为是不同的当且仅当 \exists i\in[1, n]:S_{i}\ne T_{i}

答案对 998244353 取模。

Constraints

1\le n\le k\le 3\times 10^{4}

Analysis

显然可以设 f_{i,t} 为满足 \operatorname{popcount}(B_{i})=t 的方案数,则有:

f_{i,t}=\sum_{j=i-1}^{t-1}\binom{k-j}{t-j}2^{j}f_{i-1,j}

按照这个式子去转移时间复杂度是 O\left(n(k - n)^{2}\right) 的,考虑优化。
发现第一维可以一次加多个:

f_{i+j,t}=\sum_{s=0}^{t}\binom{t}{s}f_{i,s}\left(2^{s}\right)^{j}f_{j,t-s}

整理得:

\frac{f_{i+j,t}}{t!}=\sum_{s=0}^{t}\frac{f_{i,s}\left(2^{j}\right)^{s}}{s!}\frac{f_{j,t-s}}{(t - s)!}

发现是个卷积的形式,对第一维二进制拆分使用类似快速幂的写法即可。

时间复杂度 O\left(n\log^{2}{n}\right)

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<cstdio>
#include<algorithm>

using i64=long long;

constexpr int maxn(30000);
constexpr int mxdg(65536);
constexpr int p(998244353);
constexpr int proot(3);

inline int io(){static int _;return scanf("%d",&_),_;}

template<typename x_tp,typename y_tp>
inline void inc(x_tp&x,const y_tp&y)
{x+=y;(p<=x)&&(x-=p);}
template<typename x_tp,typename y_tp>
inline x_tp sub(const x_tp&x,const y_tp&y)
{return(x<y)?(x-y+p):(x-y);}

template<typename _Tp>
inline void swap(_Tp&x,_Tp&y)
{_Tp z=x;x=y;y=z;}
template<typename _Tp>
inline int fpow(_Tp v,int n){
int pw=1;
for(;n;n>>=1,v=(i64)v*v%p)
if(n&1)pw=(i64)pw*v%p;
return pw;
}

inline int calcpw2(const int&n){
int t=1;
for(;t<n;t<<=1);
return t;
}

using Z=int;
using mZ=i64;
using poly_t=Z[mxdg];
using poly=Z*const;

poly_t wn,iwn,cw;

inline void polyinit(){
const int wnv=fpow(proot,(p-1)/mxdg);
wn[0]=iwn[0]=1;
for(int i=1,w=1;i!=mxdg;++i)
w=(mZ)w*wnv%p,wn[i]=w;
std::reverse_copy(wn+1,wn+mxdg,iwn+1);
}

void DFT(poly&a,const int&n){
for(int i=0,j=0;i!=n;++i){
if(i<j)swap(a[i],a[j]);
for(int k=n>>1;(j^=k)<k;k>>=1);
}poly endpos=a+n,wendpos=wn+mxdg;
cw[0]=1;
for(int l=1,tp=mxdg>>1;l!=n;l<<=1,tp>>=1){
for(Z*w=cw,*i=wn+tp;i!=wendpos;i+=tp)
*++w=*i;
for(Z*i=a,z;i!=endpos;i+=l+l)
for(int j=0;j!=l;++j)
z=(mZ)i[j+l]*cw[j]%p,
i[j+l]=sub(i[j],z),
inc(i[j],z);
}
}
void IDFT(poly&a,const int&n){
for(int i=0,j=0;i!=n;++i){
if(i<j)swap(a[i],a[j]);
for(int k=n>>1;(j^=k)<k;k>>=1);
}poly endpos=a+n,wendpos=iwn+mxdg;
cw[0]=1;
for(int l=1,tp=mxdg>>1;l!=n;l<<=1,tp>>=1){
for(Z*w=cw,*i=iwn+tp;i!=wendpos;i+=tp)
*++w=*i;
for(Z*i=a,z;i!=endpos;i+=l+l)
for(int j=0;j!=l;++j)
z=(mZ)i[j+l]*cw[j]%p,
i[j+l]=sub(i[j],z),
inc(i[j],z);
}const Z invn=fpow(n,p-2);
for(Z*i=a;i!=endpos;++i)
*i=(mZ)*i*invn%p;
}

inline void calc(poly&f,const poly&g,const int&n,const int&pw2){
static poly_t calc_t;

std::copy(g,g+n,calc_t);
for(int i=0,pw=1;i!=n;++i,pw=(mZ)pw*pw2%p)
f[i]=(mZ)f[i]*pw%p;

DFT(f,n);DFT(calc_t,n);
for(int i=0;i!=n;++i)
f[i]=(mZ)f[i]*calc_t[i]%p;
IDFT(f,n);
}

poly_t pw,ans;

int fac[maxn+1],
ifac[maxn+1];

inline int C(const int&n,const int&k)
{return(i64)fac[n]*ifac[k]%p*ifac[n-k]%p;}

int main(){
polyinit();
const int n=io(),k=io(),deg=calcpw2(k+k+1);

fac[0]=fac[1]=ifac[0]=ifac[1]=1;
for(int i=2,v=1;i<=k;++i)
v=(i64)v*i%p,fac[i]=v;
for(int i=k,v=fpow(fac[k],p-2);i!=1;--i)
ifac[i]=v,v=(i64)v*i%p;

std::copy(ifac+1,ifac+k+1,pw+1);
ans[0]=1;
for(int t=n,pw2=2;t;t>>=1,calc(pw,pw,deg,pw2),std::fill(pw+k+1,pw+deg,0),pw2=(i64)pw2*pw2%p)
if(t&1)calc(ans,pw,deg,pw2),std::fill(ans+k+1,ans+deg,0);

i64 tans=0;
for(int i=n;i<=k;++i)
tans+=(i64)ans[i]*fac[i]%p*C(k,i)%p;
printf("%d",tans%p);

return 0;
}

Day 2

走路

Description

给定一棵有 n 个节点且带点权的有根树,根为节点 1 ,节点 u 的点权为 val_{u}
如果两个节点 u,v 满足 u v 的祖先且 val_{v} | val_{u} ,则可以从 u 直接到达 v
现要求对于每一个点 u ,求出从根节点到达节点 u 的方案数。

定义两个方案是不同的当且仅当其经过的点数不同或某一步经过了不同的点。

答案对 10^{9}+7 取模。

Constraints

1\le n\le 10^{5},1\le val_{1}\le 10^{18},\forall i\in[1, n]:val_{i} | val_{1}

Analysis

显然可以 O(n^{2}) DP,尝试优化。
U:=val_{1} ,发现 \omega(u) 最大为 15 \sigma_{0}(u) 最大为 103680
容易想到以下两种维护方式:

  1. \displaystyle{f_{v}=\sum_{v | val_{u}}ans_{u}} ,修改复杂度 O\left(\sigma_{0}(u)\right) ,查询复杂度 O(1) ,总时间复杂度 O\left(n\sigma_{0}(u)\right)
  2. \displaystyle{f_{v}=\sum_{v=val_{u}}ans_{u}} ,修改复杂度 O(1) ,查询复杂度 O\left(\sigma_{0}(u)\right) ,总时间复杂度 O\left(n\sigma_{0}(u)\right)

但显然这两种方式都无法通过本题,则考虑均摊复杂度。
\displaystyle{g(n, s)=\prod_{p\in s}p^{\nu_{p}(n)}},U_{s}:=g(U, s)
将质因子集合分为两个不相交的集合 s l ,类似「CTSC2017」吉夫特,设状态 f

f_{sv,lv}=\sum_{g(val_{u},s)=sv,lv | g(val_{u},l)}val_{u}

则修改复杂度为 O\left(\sigma_{0}(U_{l})\right) ,查询复杂度为 O\left(\sigma_{0}(U_{s})\right) ,总复杂度 O\left(n\left(\sigma_{0}(U_{l})+\sigma_{0}(U_{s})\right)\right)
又容易知道 \sigma_{0}(U_{s})\sigma_{0}(U_{l})=\sigma_{0}(u) ,故划分时应使 \sigma_{0}(U_{s}) \sigma_{0}(U_{l}) 尽可能接近 \sqrt{\sigma_{0}(u)}

时间复杂度约为 O\left(U^{\frac{1}{4}}\omega(u)+\sigma_{0}(u)+n\sqrt{\sigma_{0}(u)}\right)

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
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
#include<cstdio>
#include<algorithm>

using i64=long long;
using u64=unsigned long long;
using ld=long double;

constexpr int maxn(100000);
constexpr int maxb(1000);
constexpr int maxp(20);
constexpr int p(1000000007);

template<typename x_tp,typename y_tp>
inline void inc(x_tp&x,const y_tp&y)
{x+=y;(p<=x)&&(x-=p);}
template<typename x_tp,typename y_tp>
inline void dec(x_tp&x,const y_tp&y)
{x-=y;(x<0)&&(x+=p);}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

constexpr int OSIZE(65536);
unsigned char obuf[OSIZE+128];
constexpr unsigned char *OT(obuf+OSIZE);

struct IOManager{

IOManager():OS(obuf-1){}
~IOManager(){fwrite(obuf,1,OS-obuf+1,stdout);fclose(stdout);}

inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}

unsigned char *OS;

inline void Flush(){fwrite(obuf,1,OS-obuf+1,stdout);OS=obuf-1;}

inline IOManager&operator<<(const unsigned char&c)
{if(OS>OT)Flush();return(*++OS=c,*this);}

inline IOManager&operator<<(const char&c)
{if(OS>OT)Flush();return(*++OS=c,*this);}

template<typename _Tp>
inline IOManager&operator<<(_Tp s){
static unsigned char ostk[30],*Top=ostk;
static _Tp y;
if(OS>OT)Flush();
for(;s;*++Top=s-y*10+48,s=y)
y=s/10;
for(;Top!=ostk;)
*++OS=*Top--;
return*this;
}
};
}IOManager::IOManager io;

namespace math{
constexpr int fpri[]={2,3,5,7,11,13,17,19};

template<typename _tp>
inline _tp Abs(const _tp&v)
{return v<0?-v:v;}

template<typename x_tp,typename y_tp,typename _tp>
inline void inc(x_tp&x,const y_tp&y,const _tp&p)
{x+=y;(p<=x)&&(x-=p);}
template<typename x_tp,typename y_tp,typename _tp>
inline _tp pls(const x_tp&x,const y_tp&y,const _tp&p)
{return(p<=x+y)?(x-p+y):(x+y);}

template<typename x_tp,typename y_tp>
inline x_tp gcd(const x_tp&x,const y_tp&y)
{return y?gcd(y,x%y):x;}

template<typename x_tp,typename y_tp,typename _tp>
inline _tp mul(const x_tp&x,const y_tp&y,const _tp&p)
{return(x*y-(i64)(((ld)x*y+.5)/p)*p)%p;}

template<typename v_tp,typename n_tp,typename _tp>
inline v_tp fpow(v_tp v,n_tp n,const _tp&p){
v_tp pw=1;
for(;n;n>>=1,v=mul(v,v,p))
if(n&1)pw=mul(pw,v,p);
return pw;
}

inline u64 rand(){
static u64 v=(u64)"tommyr7";
v^=v>>12;v^=v<<25;v^=v>>27;
return v*(u64)"cyand1317";
}

inline bool witness(const i64&v,const i64&r,const i64&n,const int&_s){
i64 x=fpow(v,r,n);
if(x==1||x==n-1)
return false;
for(int s=_s;s;--s)
if((x=mul(x,x,n))==n-1)
return false;
return true;
}

inline bool MR(const i64&n){
if(n==2)
return true;
if(!(n&1)||n<2)
return false;
i64 r=n-1;
int s=0;
for(;~r&1;r>>=1)
++s;
for(int i=0;i!=8;++i){
if(n==fpri[i])
return true;
if(witness(fpri[i],r,n,s))
return false;
}return true;
}

inline i64 PR(const i64&n,const i64&c){
i64 k=2,x=rand()%n,y=x,d=1;
for(i64 i=1;d==1;++i){
x=pls(mul(x,x,n),c,n);
d=gcd(n,Abs(y-x));
if(i==k)
y=x,k<<=1;
}return d;
}

template<typename v_tp,typename d_tp>
inline void divide(const v_tp&n,d_tp*&p){
if(n==1)
return;
if(MR(n))
return(void)(*++p=n);
v_tp d;
do d=PR(n,rand()%(n-1));while(d==n);
divide(d,p);divide(n/d,p);
}
}

struct Edge{
int v;Edge*las;

inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}pool[(maxn<<1)+maxb*maxb*2],*alc=pool-1;
Edge*las[maxn+1],
*tlas[maxb+1];

struct PrimeFactor{i64 v;int a;}pf[maxp+1];
int divpos;

struct E{
i64 v;Edge*las;

E():v(0),las(nullptr){}
E(const i64&iv)
:v(iv){}

inline bool operator<(const E&rhs)
const{return v<rhs.v;}

inline void lnk(const int&to)
{las=(++alc)->init(to,las);}
}sf[maxb],lf[maxb];

int dp[maxb][maxb],
ans[maxn+1];
i64 w[maxn+1];

void calc(const int&u,const int&fa){
i64 cw=w[u];
for(int i=1;i<=divpos;++i)
if(cw%pf[i].v==0)
for(cw/=pf[i].v;cw%pf[i].v==0;cw/=pf[i].v);

const int s=std::lower_bound(sf+1,sf+sf->v+1,E(w[u]/cw))-sf,
l=std::lower_bound(lf+1,lf+lf->v+1,E(cw))-lf;

i64 v=(u==1);
for(Edge*o=sf[s].las;o;o=o->las)
v+=dp[o->v][l];

const i64 del=ans[u]=v%p;
for(Edge*o=lf[l].las;o;o=o->las)
inc(dp[s][o->v],del);

for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa)
calc(o->v,u);

for(Edge*o=lf[l].las;o;o=o->las)
dec(dp[s][o->v],del);
}

i64 d[maxb+1];

int main(){
const int n=io;
for(int i=n-1,u,v;i;--i)
u=io,v=io,
las[u]=(++alc)->init(v,las[u]),
las[v]=(++alc)->init(u,las[v]);
for(int i=1;i<=n;++i)
w[i]=io;

i64*cd=d;
math::divide(w[1],cd);
std::sort(d+1,cd+1);

int cnt=1;
PrimeFactor*cpf=pf;
for(i64*i=d+1;i<=cd;++i)
if(++cnt,*i!=*(i+1))
(++cpf)->v=*i,cpf->a=cnt,cnt=1;
const int cntp=cpf-pf;

int sigma=1;
for(PrimeFactor*i=pf+1;i<=cpf;++i)
sigma*=i->a;
for(int t=1;t*t<sigma;)
t*=pf[++divpos].a;

for(int pos=1,csz=cnt=sf[1].v=1;pos<=divpos;++pos,csz=cnt){
const i64 cp=pf[pos].v;
for(int nu=1;nu!=pf[pos].a;++nu)
for(int i=1;i<=csz;++i)
++cnt,sf[cnt].v=sf[cnt-csz].v*cp;
}sf->v=cnt;

for(int pos=divpos+1,csz=cnt=lf[1].v=1;pos<=cntp;++pos,csz=cnt){
const i64 cp=pf[pos].v;
for(int nu=1;nu!=pf[pos].a;++nu)
for(int i=1;i<=csz;++i)
++cnt,lf[cnt].v=lf[cnt-csz].v*cp;
}lf->v=cnt;

std::sort(sf+1,sf+sf->v+1);
std::sort(lf+1,lf+lf->v+1);

for(int u=1;u<=sf->v;++u){
sf[u].lnk(u);
for(int v=u+1;v<=sf->v;++v)
if(sf[v].v%sf[u].v==0)
sf[u].lnk(v);
}
for(int u=1;u<=lf->v;++u){
lf[u].lnk(u);
for(int v=u+1;v<=lf->v;++v)
if(lf[v].v%lf[u].v==0)
lf[v].lnk(u);
}

calc(1,0);
for(int i=1;i<=n;++i)
io<<ans[i]<<'\n';

return 0;
}

游戏

Description

给定一个 n\times n 的棋盘,现要求你摆放 n 个车,满足每行每列都有且只有一个车。
每次移动只能移动到当前格的四个相邻格之一。
定义一个摆放方案是合法的当且仅当可以在不经过车所在格的情况下从 \left(1,1\right) 移动到 \left(n,n\right)
求合法的摆放方案数,共 T 组询问。

答案对 10^{9}+7 取模。

Constraints

1\le T\le 500,1\le n\le 10^{9}

Analysis

容斥一下可以发现答案即为:

\begin{aligned} &n! - 2\sum_{i = 1}^{n}(n - i)! + \sum_{i = 1}^{n - 1}\sum_{j = 1}^{n - i}(n - i - j)!\\ &= n! - 2\sum_{i = 0}^{n - 1}i! + \sum_{i = 2}^{n}(n - i)!(i - 1) + 1\\ &= n! - 2\sum_{i = 0}^{n - 1}i! + \sum_{i = 0}^{n - 2}i!(n - i - 1) + 1\\ &= n! - 2\sum_{i = 0}^{n - 1}i! + n\sum_{i = 0}^{n - 2}i! - \sum_{i = 0}^{n - 2}(i + 1)! + 1\\ &= n! - 3\sum_{i = 0}^{n - 1}i! + n\sum_{i = 0}^{n - 2}i! + 2\\ &= (n - 3)\sum_{i = 0}^{n - 1}i! + 2 \end{aligned}

但是发现 n 10^{9} 级别的。。。什么毒瘤出题人
考虑分块打表。
设块大小为 B ,则时间复杂度为 O\left(TB\right) ,空间复杂度为 O\left(\displaystyle\frac{n}{B}\right)
按道理来讲块大小应该设为 \sqrt{Tn}\approx 710000 ,但是。。。

辣鸡 BZOJ

于是只能把码长限制在 5k 左右。。。
我能想到的最优秀的压缩方法大概是采用 64 进制,每个数占用 5 Byte...算一下块大小 B\approx 200000
虽然理论上能过但是。。。

辣鸡 BZOJ

辣鸡 BZOJ!!!/ 掀桌

于是去请教了下 cls...cls 告诉我要预处理 n\le 10^{7} 因为数据最多只有两组 10^{7}<n 。。。
然后就 AC 了。。。
据 cls 本人说他的块大小是 350000 而且还是 16 进制压缩...不知道咋写的跑的飞快 qwq

时间复杂度 O\left(TB\right)

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
#include<cstdio>

using i64=long long;

constexpr int p(1000000007);
constexpr int maxn(1000000000);
constexpr int maxc(10000000);
constexpr int B(200000);

namespace Encode{
constexpr char c[]="0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ,.";

char s[(maxn/B+1)*10],*t=s;

#define p64(n) (*t++=c[(n>>24)&63],*t++=c[(n>>18)&63],*t++=c[(n>>12)&63],*t++=c[(n>>6)&63],*t++=c[n&63])

inline void table(){
int fac=1;i64 sum=1;
p64(1);p64(1);
for(int i=B;i<=maxn;i+=B,sum%=p,p64(fac),p64(sum))
for(int j=i-B+1;j<=i;++j)
fac=(i64)fac*j%p,sum+=fac;
fwrite(s,1,t-s,stdout);
}
}

namespace Decode{
constexpr int idx[]={
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,62,0,63,0,
0,1,2,3,4,5,6,7,
8,9,0,0,0,0,0,0,
0,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,0,0,0,0,0,
0,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,0,0,0,0,0
};

#define g64(s) ((idx[*(s)]<<24)|(idx[*(s+1)]<<18)|(idx[*(s+2)]<<12)|(idx[*(s+3)]<<6)|idx[*(s+4)])
}

constexpr char s[]=""; /*打出来的表*/

inline int io(){static int _;return scanf("%d",&_),_;}

i64 sfac[maxc+1];

inline void precalc(){
sfac[0]=1;sfac[1]=2;
for(int i=2,fac=1;i<=maxc;++i)
fac=(i64)fac*i%p,
sfac[i]=sfac[i-1]+fac;
}

inline int calc(const int&n){
if(n<=maxc)
return sfac[n]%p;
using namespace Decode;
const int pos=n/B*10;
int fac=g64(s+pos);
i64 sum=g64(s+pos+5);
for(int i=(n/B)*B+1;i<=n;++i)
fac=(i64)fac*i%p,sum+=fac;
return sum%p;
}

int main(){
// Encode::table();
precalc();
for(int T=io(),n;T;--T)
n=io(),printf("%d\n",n<3?0:((i64)(calc(n-1)*(n-3ll)+2ll+p)%p));

return 0;
}

有趣的字符串题

Description

给定一个长度为 n 的字符串,有 m 个询问,每次询问一个区间 s[l, r] 内的本质不同回文子串个数。

Constraints

1\le n\le 3\times 10^{5},0\le m\le 10^{6},1\le l\le r\le n

Analysis

首先要证明一个很喵的东西:

一个字符串 s 的所有回文后缀的长度可以形成 O\left(\log{|S|}\right) 个等差数列.

证明了这个东西以后再来看就很简单了...

考虑移动右端点并逐个加入字符,记录每个左端点对应的答案。
在右端点从 r-1 移动到 r 时,对于一组长度为等差数列的回文后缀 s[u:r],s[u+d:r],\dots,s[u+xd:r] ,记 s[u:r] 上一次出现的位置为 s[w:w+r-u] ,则 \forall l\in(w,u+xd]:ans_{l,r}:=ans_{l,r-1}+1

因为对于所有 l\in(w,u] s[l:r] 内新出现了回文串 s[u:r] ;
而对于所有 i\in[0,x),l\in(u+id,u+(i+1)d] s[l:r] 内新出现了回文串 s[u+(i+1)d:r]
按 fail 树上 DFS 序建线段树维护每个回文子串上一次出现的位置,树状数组维护答案即可。

时间复杂度 O\left(n\log^{2}{n}\right)

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
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
#include<cstdio>

using i64=long long;

constexpr int maxn(300000);
constexpr int maxm(1000000);
constexpr int p(1000000007);

template<typename _Tp>
inline _Tp Max(const _Tp&x,const _Tp&y)
{return x>y?x:y;}
template<typename _Tp>
inline void chkMax(_Tp&x,const _Tp&y)
{x<y&&(x=y);}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;
inline int tgi(){static int _;return scanf("%d",&_),_;}

struct Edge{
int v;Edge*las;

inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}*las[maxn+1],epool[maxn+2],*ealc=epool-1;

struct Query{
int idx,l;Query*las;

inline Query* init(const int&qid,const int&ql,Query*const&ls)
{return idx=qid,l=ql,las=ls,this;}
}*qlas[maxn+1],qpool[maxm],*qalc=qpool-1;

namespace PAM{
struct state_t{
static constexpr int sigma=26;

int len,las,nxt,del,trans[sigma];
state_t():len(0),las(0),nxt(0),del(0){}
}pam_node[maxn+3];

#define len(o) pam_node[o].len
#define las(o) pam_node[o].las
#define nxt(o) pam_node[o].nxt
#define del(o) pam_node[o].del
#define trans(o,c) pam_node[o].trans[c]

int pnalc=1;
char str[maxn+1];

inline int extend(const int&c,const int&n){
static int las=0;
int p=las;
for(;str[n]!=str[n-len(p)-1];p=las(p));
if(!trans(p,c)){
const int u=++pnalc;int t=las(p);
for(;str[n]!=str[n-len(t)-1];t=las(t));

len(u)=len(p)+2;
las(u)=trans(t,c);
trans(p,c)=u;
del(u)=len(u)-len(las(u));
nxt(u)=(del(u)==del(las(u))?nxt(las(u)):u);
}return las=trans(p,c);
}

inline void init(const int&n,int*const&idx){
scanf("\n");fread(str+1,1,n,stdin);
len(1)=-1;
las(0)=las(1)=1;
for(int i=1;i<=n;++i)
idx[i]=extend(str[i]-'a',i);

las[1]=(++ealc)->init(0,las[1]);
for(int u=2;u<=pnalc;++u)
las[las(u)]=(++ealc)->init(u,las[las(u)]);
}
}

int ql,qr,qpos,qv,qans;
struct Node{
int v;
Node *ls,*rs;

Node():v(0),ls(nullptr),rs(nullptr){}

static inline Node* newnode();

inline void update()
{v=Max(ls->v,rs->v);}

void setup(const int&l,const int&r){
if(l==r)
return;
const int m=(l+r)>>1;
ls=newnode();ls->setup(l,m);
rs=newnode();rs->setup(m+1,r);
}

void update(const int&l,const int&r){
if(l==r)
return(void)(v=qv);
const int m=(l+r)>>1;
if(qpos<=m)
ls->update(l,m);
else
rs->update(m+1,r);
update();
}

void query(const int&l,const int&r){
if(ql<=l&&r<=qr)
return chkMax(qans,v);
const int m=(l+r)>>1;
if(ql<=m)
ls->query(l,m);
if(m<qr)
rs->query(m+1,r);
}
};
Node ndpool[(maxn+3)<<1],*ndalc=ndpool-1;
inline Node* Node::newnode()
{return++ndalc;}

int s[maxn+3],
t[maxn+3],
cnt;

void precalc(const int&u){
s[u]=++cnt;
for(Edge*o=las[u];o;o=o->las)
precalc(o->v);
t[u]=cnt;
}

int idx[maxn+1],
bit[maxn+1];

int main(){
const int n=tgi(),m=tgi();
PAM::init(n,idx);
precalc(1);
Node*root=Node::newnode();
root->setup(1,cnt);

for(int i=1,l,r;i<=m;++i)
l=io,r=io,
qlas[r]=(++qalc)->init(i,l,qlas[r]);
using PAM::pam_node;

i64 ans=0;
for(int r=1;r<=n;++r){
for(int u=idx[r];u;u=las(nxt(u))){
ql=s[u];qr=t[u];qans=0;
root->query(1,cnt);
for(int i=Max(1,qans-len(u)+2);i<=n;i+=i&-i)
++bit[i];
for(int i=r-len(nxt(u))+2;i<=n;i+=i&-i)
--bit[i];
}

qpos=s[idx[r]];qv=r;
root->update(1,cnt);

for(Query*o=qlas[r];o;o=o->las){
int sum=0;
for(int i=o->l;i;i-=i&-i)
sum+=bit[i];
ans+=(i64)sum*o->idx%p;
}
}printf("%d",ans%p);

return 0;
}

Day 3

circular

Description

给定一个长度为 m 的环,环上有 m 个等距分布的点,顺时针标号为 0,1,2,...,m-1
给定环上的 n 个线段,第 i 条线段从 l_{i} 顺时针延伸到 r_{i} (不包括 l_{i} r_{i} )。
问最多能选多少条互不相交的线段。

Constraints

1\le n\le 10^{5},1\le m\le 10^{8},\forall i\in[1, n]:0\le l_{i},r_{i}<m,l_{i}\ne r_{i}

Analysis

显然如果破环成链则可贪心选取线段,即每次选取左端点在当前右端点右侧的所有线段中右端点最小的一个。
预处理第 i 条线段向右跳 2^{j} 步后在哪个位置,枚举在哪个点断开环后倍增跳即可。

时间复杂度 O(n \log{n})

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
#include<cstdio>
#include<algorithm>

constexpr int maxn(200000);
constexpr int mxlg(18);

template<typename _Tp>
inline void chkMax(_Tp&x,const _Tp&y)
{x<y&&(x=y);}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

struct sgt{
int l,r;
inline void init(const int&ll,const int&rr)
{l=ll;r=rr;}
inline bool operator<(const sgt&rhs)
const{return l<rhs.l||(l==rhs.l&&r<rhs.r);}
}seg[maxn+1];

int l[maxn+1],
mnr[maxn+1],
r[maxn+1][mxlg];

int main(){
const int m=io;
sgt*cur=seg;
for(int i=io,u,v;i;--i)
if(u=io,v=io,u<v)
(++cur)->init(u,v),
(++cur)->init(u+m,v+m);
else
(++cur)->init(u,v+m);
std::sort(seg+1,cur+1);

const int n=cur-seg;
for(int i=1;i<=n;++i)
l[i]=seg[i].l;
mnr[n]=n;
for(int i=n-1;i;--i)
mnr[i]=(seg[i].r<seg[mnr[i+1]].r?i:mnr[i+1]);
for(int i=n-1;i;--i){
r[i][0]=mnr[std::lower_bound(l+i+1,l+n+1,seg[i].r)-l];
for(int lg=1;lg!=mxlg;++lg)
if(!(r[i][lg]=r[r[i][lg-1]][lg-1]))
break;
}

int ans=0;
for(int i=1;i<=n;++i){
int cnt=1;
for(int cpos=i,lg=mxlg-1;~lg;--lg)
if(r[cpos][lg]&&seg[r[cpos][lg]].r<=l[i]+m)
cpos=r[cpos][lg],cnt+=1<<lg;
chkMax(ans,cnt);
}printf("%d",ans);

return 0;
}

admirable

Description

给定一棵 n 个点的树 T 和一个数 k ,求在树上选出 k 条路径使得其交非空且不在其交上的边至多被一条路径覆盖的方案数。
k 条路径间是有序的,亦即 \left\{(u_{1},v_{1}),(u_{2},v_{2})\right\} \left\{(u_{2},v_{2}),(u_{1},v_{1})\right\} 是不同的两种方案。

答案对 10^{9}+9 取模。

Constraints

1\le n,k\le 10^{5}

Analysis

「Avito Code Challenge 2018」H. K Paths.
刚学完 MTT 把板子搬过来结果模数忘了改。。。调了一个下午

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
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
#include<cmath>
#include<cstdio>
#include<algorithm>

using i64=long long;

constexpr int maxn(100000);
constexpr int mxdg(262144);
constexpr int p(1000000009);

template<typename _Tp>
inline void swap(_Tp&x,_Tp&y)
{_Tp z=x;x=y;y=z;}
template<typename _Tp>
inline void inc(_Tp&x,const _Tp&y)
{x+=y;(p<=x)&&(x-=p);}
template<typename x_tp,typename y_tp>
inline int sub(const x_tp&x,const y_tp&y)
{return(x<y)?(x-y+p):(x-y);}

namespace IOManager{
constexpr int FILESZ(131072);
char buf[FILESZ];
const char*ibuf=buf,*tbuf=buf;

struct IOManager{
inline char gc()
{return(ibuf==tbuf)&&(tbuf=(ibuf=buf)+fread(buf,1,FILESZ,stdin),ibuf==tbuf)?EOF:*ibuf++;}

template<typename _Tp>
inline operator _Tp(){
_Tp s=0u;char c=gc();
for(;c<48;c=gc());
for(;c>47;c=gc())
s=(_Tp)(s*10u+c-48u);
return s;
}
};
}IOManager::IOManager io;

struct Edge{
int v;Edge*las;

inline Edge* init(const int&to,Edge*const&ls)
{return v=to,las=ls,this;}
}*las[maxn+1];

inline void lnk(){
static Edge pool[maxn<<1],*alc=pool-1;
const int u=io,v=io;
las[u]=(++alc)->init(v,las[u]);
las[v]=(++alc)->init(u,las[v]);
}

namespace poly{
const double pi(acos(-1.));

template<typename _Tp>
struct Complex{
_Tp r,i;

Complex()
:r(0),i(0){}
Complex(const _Tp&rb,const _Tp&ib=0)
:r(rb),i(ib){}

inline Complex operator+(const Complex&rhs)
const{return Complex(r+rhs.r,i+rhs.i);}
inline Complex operator-(const Complex&rhs)
const{return Complex(r-rhs.r,i-rhs.i);}
inline Complex operator*(const Complex&rhs)
const{return Complex(r*rhs.r-i*rhs.i,r*rhs.i+i*rhs.r);}
inline Complex operator/(const Complex&rhs)const{
_Tp fm=rhs.r*rhs.r+rhs.i*rhs.i;
return Complex((r*rhs.r+i*rhs.i)/fm,(i*rhs.r-r*rhs.i)/fm);
}

inline Complex&operator+=(const Complex&rhs)
{return r+=rhs.r,i+=rhs.i,*this;}
inline Complex&operator-=(const Complex&rhs)
{return r-=rhs.r,i-=rhs.i,*this;}
inline Complex&operator*=(const Complex&rhs)
{return*this=*this*rhs;}
inline Complex&operator/=(const Complex&rhs)
{return*this=*this/rhs;}

template<typename r_tp>
inline Complex operator/(const r_tp&rhs)
const{return Complex(r/rhs,i/rhs);}
template<typename r_tp>
inline Complex&operator/=(const r_tp&rhs)
{return r/=rhs,i/=rhs,*this;}

inline Complex conj()
const{return Complex(r,-i);}
};
using C=Complex<double>;

using Z=int;
using MZ=i64;
using poly_t=Z[mxdg];
using poly=Z*const;
using cpoly_t=C[mxdg];
using cpoly=C*const;

inline int calcpw2(const int&n){
int t=1;
for(;t<n;t<<=1);
return t;
}

cpoly_t wn,cw;

inline void polyinit(){
const double pi2(pi*2);
wn[0]=C(1,0);
for(int i=1;i!=mxdg;++i)
wn[i]=C(cos(pi2*i/mxdg),sin(pi2*i/mxdg));
}

void DFT(cpoly&a,const int&n){
for(int i=0,j=0;i!=n;++i){
if(i<j)swap(a[i],a[j]);
for(int l=n>>1;(j^=l)<l;l>>=1);
}
cw[0]=C(1,0);
cpoly endpos=a+n,wendpos=wn+mxdg;
for(int l=1,tp=mxdg>>1;l!=n;l<<=1,tp>>=1){
for(C*i=wn+tp,*w=cw;i!=wendpos;i+=tp)
*++w=*i;
for(C*i=a,z;i!=endpos;i+=l+l)
for(int j=0;j!=l;++j)
z=i[j+l]*cw[j],
i[j+l]=i[j]-z,
i[j]+=z;
}
}
inline void mul(const poly&f,const int&df,const poly&g,const int&dg,poly&ans){
static cpoly_t F,G,P,Q;
static C ta,tb,tc,td;

if(df+dg<=150){
static MZ mul_r[200];
std::fill(mul_r,mul_r+df+dg+1,0);

for(int i=0;i<=df;++i)
for(int j=0;j<=dg;++j)
mul_r[i+j]+=(MZ)f[i]*g[j]%p;

for(int i=0;i<=df+dg;++i)
ans[i]=mul_r[i]%p;
}else{
const int n=calcpw2(df+dg+1);

for(int i=0;i<=df;++i)
F[i]=C(f[i]&32767,f[i]>>15);
std::fill(F+df+1,F+n,0);
for(int i=0;i<=dg;++i)
G[i]=C(g[i]&32767,g[i]>>15);
std::fill(G+dg+1,G+n,0);

DFT(F,n);DFT(G,n);

ta=(F[0]+F[0].conj())*C(.5,0);
tb=(F[0]-F[0].conj())*C(0,-.5);
tc=(G[0]+G[0].conj())*C(.5,0);
td=(G[0]-G[0].conj())*C(0,-.5);

P[0]=(ta*tc)+(ta*td*C(0,1));
Q[0]=(tb*tc)+(tb*td*C(0,1));

for(int i=1;i!=n;++i){
const int j=n-i;
ta=(F[i]+F[j].conj())*C(.5,0);
tb=(F[i]-F[j].conj())*C(0,-.5);
tc=(G[i]+G[j].conj())*C(.5,0);
td=(G[i]-G[j].conj())*C(0,-.5);

P[j]=(ta*tc)+(ta*td*C(0,1));
Q[j]=(tb*tc)+(tb*td*C(0,1));
}

const int da=df+dg+1;

DFT(P,n);DFT(Q,n);
for(int i=0,a,b,c,d;i!=da;++i)
ans[i]=(
(MZ)(P[i].r/n+.5)%p
+(((MZ)(P[i].i/n+.5)%p+(MZ)(Q[i].r/n+.5)%p)<<15)
+(((MZ)(Q[i].i/n+.5)%p)<<30)
)%p;
}
}
}

poly::poly_t cp_t[18];
poly::poly cp=cp_t[0];
int idx,
mem[maxn+1],
lasi[maxn+1],
expF[maxn+1],
sz[maxn+1],
sum[maxn+1],
lis[maxn+1];

void calc(const int&d,const int&l,const int&r){
if(l==r)
return(void)(cp_t[d][l+l]=1,cp_t[d][l+l+1]=lis[l]);
const int m=(l+r)>>1;
calc(d+1,l,m);calc(d+1,m+1,r);
poly::mul(cp_t[d+1]+l+l,m-l+1,cp_t[d+1]+m+m+2,r-m,cp_t[d]+l+l);
}

const int n=io,k=io;

int ans;
void calc(const int&u,const int&fa){
sz[u]=1;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa)
calc(o->v,u),
ans=((i64)sum[u]*sum[o->v]+ans)%p,
inc(sum[u],sum[o->v]),
sz[u]+=sz[o->v];

int cur=0;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa)
lis[++cur]=sz[o->v];
if(cur)
lis[0]=lis[cur],
calc(0,0,cur-1);
else cp[0]=1;

const int usz=cur+1;

int tsum=0;
for(int i=0;i<=k&&i!=usz;++i)
tsum=((i64)cp[i]*expF[i]+tsum)%p;
inc(sum[u],tsum);

if(fa){
const int osz=n-sz[u];
cp[cur+1]=0;
for(int i=cur;~i;--i)
cp[i+1]=((i64)cp[i]*osz+cp[i+1])%p;
}

const int cn=cur+(fa!=0);

++idx;
for(Edge*o=las[u];o;o=o->las)
if(o->v!=fa){
const int vsz=sz[o->v];
if(lasi[vsz]!=idx){
int val=0;
for(int i=0,res=0;i<=k&&i!=cn;++i)
res=sub(cp[i],(i64)res*vsz%p),
val=((i64)expF[i]*res+val)%p;

lasi[vsz]=idx;
mem[vsz]=val;
}ans=((i64)mem[vsz]*sum[o->v]+ans)%p;
}
}

int main(){
if(k==1)
return printf("%lld",(1ll*(n-1ll)*n/2ll)%p),0;

expF[0]=1;
for(int i=0;i!=k;++i)
expF[i+1]=(i64)expF[i]*(k-i)%p;
for(int i=n-1;i;--i)
lnk();

poly::polyinit();
calc(1,0);
printf("%d",ans);

return 0;
}

illustrious

Description

定义函数 f(n),g(n),h(n)

\begin{aligned} f(1) &= 1 \\ f(n) &= f(n - f(f(n - 1))) + 1 \\ g(n) &= \sum_{i = 1}^{n}f(i) \\ h(n) &= h(g(f(n)) - f(f(n))) + g(g(n)) \end{aligned}

T 次询问,每次给出 n ,求 h(n)

答案对 998244353 取模。

Constraints

1\le T\le 5,1\le n\le 10^{9}

Anslysis

手算前二十项 f(x) 可以发现其单调不降且:

f(x) = \sum_{n\ge 0}[f(n)=x]

那么就有:

\begin{aligned} g(x) &=\max_{f(n) = x}{n} \\ \forall x\in(g(v - 1), g(v)] &: f(x) = v \\ g(g(x)) &= \sum_{i = 1}^{g(x)} f(i) \\ &= \sum_{v = 1}^{x} \sum_{i = g(v - 1) + 1}^{g(v)} f(i) \\ &= \sum_{v = 1}^{x} \sum_{i = g(v - 1) + 1}^{g(v)} v \\ &= \sum_{v = 1}^{x} vf(v) \\ \end{aligned}

观察 h(x) 的转移点 g(f(x)) - f(f(x)) = g(f(x) - 1) ,可以发现转移点即为 x 左侧的第一个 g(n) ,即:

h(x) = g(g(x)) + \sum_{g(v)<x} g(g(g(v)))

打表发现 f(10^{9}) = 438744 ,故预处理出前 k = 438744 g(x) \displaystyle\sum_{g(v)<x} g(g(g(v))) 即可 O\left(\log{k}\right) 回答每次询问。

时间复杂度 O\left(k+T\log{k}\right)

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
#include<cstdio>
#include<algorithm>

using i64=long long;

constexpr int maxn(438744);
constexpr int p(998244353);

template<typename _tp>
inline _tp div2(const _tp&v)
{return((v&1)?v+p:v)>>1;}

inline int io(){static int _;return scanf("%d" &_),_;}

int f[maxn+1],
g[maxn+1];
i64 g2[maxn+1];

int main(){
f[1]=g[1]=g2[1]=1;
for(int i=2,s=1;i<=maxn;++i)
g[i]=g[i-1]+(f[i]=f[i-f[f[i-1]]]+1),
s=(s+div2((i64)(g[i-1]+g[i]+1ll)*f[i])%p*i)%p,
g2[i]=g2[i-1]+s;

for(int T=io();T;--T){
const int n=io(),v=std::lower_bound(g+1,g+maxn+1,n)-g;
if(g[v]==n)
printf("%d\n",g2[v]%p);
else
printf("%d\n",(g2[v]-div2((i64)(g[v]+n+1)*(g[v]-n))%p*v%p)%p);
}

return 0;
}

Day 4

y

Description

一棵有 n 个叶子结点的二叉树,每个非叶子节点都有两个儿子,连接其与其儿子的两条边有一条是黑边,有一条是白边。
每个叶子节点 u 有三个属性 a_{u},b_{u},c_{u} ,现要在所有 2n-1 条边中选 n-1 条标记。
定义一种标记方案的权值为 \displaystyle\sum_{u\ is\ a\ leaf}(a_{u}+x)(b_{u}+y)c_{u} ,其中 x/y 为从根节点到 u 路径上未被标记的黑/白边数量。

求一种标记方案使得其权值最小。

Constraints

1\le n\le 2\times 10^{4},\forall u:depth_{u}\le 40,1\le a_{u},b_{u}\le 60,1\le c_{u}\le 10^{9}

Analysis

一开始以为是 「HNOI/AHOI2018」道路...WA 了一发才发现去掉了每个点出发的两条边只标记一条的限制...
不会写,咕咕咕。

s

Description

给定一个 n\times n 的带权方阵, n 为奇数。
m=\frac{n+1}{2} ,每次可以选择一个边长为 m 的子方阵并对其中的每个格子权值取反。
求经过若干次翻转后能获得的最大权值和。

Constraints

1\le n\le 33,n\equiv 1\pmod{2},|v_{i,j}|\le 1000

Analysis

一道有趣的题。
r_{i,j} (i, j) 格中的数是否取反,观察可以发现:

\begin{aligned} \forall i\le n,j<m:& r_{i,j}\operatorname{xor}r_{i,m}\operatorname{xor}r_{i,j+m}=0 \\ \forall i<m,j\le n:& r_{i,j}\operatorname{xor}r_{m,j}\operatorname{xor}r_{i+m,j}=0 \end{aligned}

因为对于这三个格子,一次操作不可能同时将其覆盖,且若一次操作覆盖了其中的一个格子,则必定会覆盖到其中的另一格子。
发现这个性质以后就可以枚举中线上的值来取 \max ,但是这样复杂度是 O\left(2^{n}n^{2}\right) 的,无法通过本题。
又发现当 r_{m,1},r_{m,2},\ldots,r_{m,m} 的值确定后,行与行之间的决策即 r_{i,m} 是相互独立的,所以只需要枚举 r_{m,1},r_{m,2},\ldots,r_{m,m} 即可。

时间复杂度 O\left(2^{m}m^{2}\right)

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
#include<cstdio>
#include<bitset>

constexpr int maxn = 33;
constexpr int inf = 2147483647;

template <typename _Tp>
inline _Tp Max(const _Tp &x, const _Tp &y)
{return x > y ? x : y;}
template <typename _Tp>
inline void chkMax(_Tp &x, const _Tp &y)
{(x < y) && (x = y);}

namespace IOManager {
constexpr int FILESZ(131072);
char buf[FILESZ];
const char *ibuf = buf, *tbuf = buf;

struct IOManager {
inline char gc()
{return (ibuf == tbuf) && (tbuf = (ibuf = buf) + fread(buf, 1, FILESZ, stdin), ibuf == tbuf) ? EOF : *ibuf++;}

template <typename _Tp>
inline operator _Tp() {
_Tp s = 0u; char c = gc(), w = 0;
for (; c < 48; c = gc())
(c == 45) && (w = 1);
for (; c > 47; c = gc())
s = (_Tp)(s * 10u + c - 48u);
return w ? -s : s;
}
};
}IOManager::IOManager io;

int v[maxn + 1][maxn + 1];
std::bitset<maxn + 1> r[maxn + 1];
const int n = io, m = (n + 1) >> 1;

inline int calc(const int &x, const int &y)
{return r[x][y] ? -v[x][y] : v[x][y];}

inline int calc(const int &x, const int &y, const bool &c) {
return (c ? -v[x][y] : v[x][y])
+ ((c ^ r[x][m]) ? -v[x][y + m] : v[x][y + m])
+ ((c ^ r[m][y]) ? -v[x + m][y] : v[x + m][y])
+ ((c ^ r[x][m] ^ r[m][y + m]) ? -v[x + m][y + m] : v[x + m][y + m]);
}

inline int calc(const int &x, const bool &c) {
r[x][m] = c;
r[x + m][m] = (c ^ r[m][m]);

int ans = calc(x, m) + calc(x + m, m);
for(int i = 1; i != m; ++i)
ans += Max(calc(x, i, false), calc(x, i, true));
return ans;
}

inline int calc(const int &st) {
const bool c = (st & 1);
r[m][m] = c;
for (int i = 1; i != m; ++i)
r[m][i] = ((st >> i) & 1),
r[m][i + m] = (r[m][i] ^ c);

int ans = 0;
for (int i = 1; i <= n; ++i)
ans += calc(m, i);
for (int i = 1; i != m; ++i)
ans += Max(calc(i, false), calc(i, true));

return ans;
}

int main() {
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
v[i][j] = io;

int ans = -inf;
for (int st = (1 << m) - 1; ~st; --st)
chkMax(ans, calc(st));
printf("%d", ans);

return 0;
}

f

Description

毒瘤 0AC 题,不会做,咕咕咕.

Constraints

Analysis

Code

Day 5

marshland

Description

给定一个 n\times n 的带权方阵,满足 \forall i+j\equiv 0\pmod{2}:v_{i,j}=0
现在你可以在方阵中选择至多 m 个互不重叠的 L 型三个格子的区域,并使每个 L 型区域角上的格子权值变为 0
方阵中有 k 个危险位置,L 型区域不能与危险位置有交.保证危险位置的权值为 0
求所有选择方案下最小的方阵权值和。

Constraints

1\le n\le 50,0\le m\le\frac{n^{2}}{3},0\le k\le n^{2},0\le v_{i,j}\le 10^{6}

Analysis

i+j 为偶数的格子 (i, j)