11月做题记录

11月做题记录
最后一个11月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

好题:CF724E Goods transportation、loj6495「雅礼集训 2018 Day1」树、luogu5652 基础博弈练习题、loj2145「SHOI2017」分手是祝愿

仙题:51nod1599 有趣的游戏

CFgym100959D Merge

题意:给出两个$n \le 2e3$的排列,将一个插入到另一个中,问能组合成多少个本质不同的序列

请先思考后再展开

首先如果两个排列相同,考虑设计一个$dp(i,j)$表示用排列前i个和排列前j个拼起来,注意到$(i,j)和(j,i)$所用的字符集是相同的,只有这种时候会计重,所以我们始终让$i \le j$即可;观察一下这东西的本质(或直接打出来)会发现其实就是走带限制格路图,即卡特兰数$Cat_n$;我们称通过两相同排列合并出的串为good串,那么一个极小的good串(不存在前缀也good,即只是用排列的前缀拼出来)的方案数$g_n=Cat_n-\sum_{i=1}^{n-1} g_{n-i} Cat_i=Cat_{n-1}$,其实本质上就是极小的括号序列,把最左边的左括号和最右边的右括号去掉也能得到

于是就可以用类似上面dp的思想做任意两个排列了,枚举一段字符集相同的后缀,其中每种方案会被恰好计数2次,$f(i,j)=f(i-1,j)+f(i,j-1)-\sum_{k=1}^{最长公共后缀(A[1..i],B[1..j])} f(i-k,j-k)*g_k$,感受一下这个lcs的和应该是$O(n^2)$级别的

1
2
3
4
5
6
7
8
9
10
fo(i,0,n) f[i][0]=f[0][i]=1;
fo(i,1,n) fo(j,1,n)
{
f[i][j]=mm(f[i-1][j]+f[i][j-1]);
fo(k,1,min(i,j))
{
if(a[i-k+1]!=b[j-k+1]) break;
add(f[i][j],MOD-1ll*g[k]*f[i-k][j-k]%MOD);
}
}write(f[n][n]);

51nod1843 排列合并机

题意:计算上面那题的期望,$n \le 100$

请先思考后再展开

要计数的话,和上面类似地需要容斥,枚举lcs的长度d,发现转移涉及到两个排列前缀的字符集有多少个重叠的,所以增加一维k
$$
\\f(i+1,j,k)+=f(i,j,k)*(n-i-j+k),f(i,j+1,k)+=f(i,j,k)*(n-i-j+k)
\\f(i+1,j,k+1)+=f(i,j,k)*(j-k),f(i,j,k+1)+=f(i,j,k)*(i-k)
\\枚举d,f(i,j,k)-=\sum_{d=1}^k P_{ n-(i+j-2d-(k-d)) }^d g_d f(i-d,j-d,k-d),O(n^4)
$$
xgc有$O(n^2)$的做法,反正我不会告辞

但是强还是我强

1
2
3
4
5
6
7
8
f[0][0][0]=1;
fo(i,0,n) fo(j,0,n) fo(k,max(i+j-n,0),min(i,j))
{
fo(d,1,k) add(f[i][j][k],MOD-g[d]*C[n-(i+j-d-d-(k-d))][d]%MOD*fac[d]%MOD*f[i-d][j-d][k-d]%MOD );
if(f[i][j][k])
add(f[i+1][j][k],f[i][j][k]*(n-i-j+k)%MOD),add(f[i][j+1][k],f[i][j][k]*(n-i-j+k)%MOD),
add(f[i+1][j][k+1],f[i][j][k]*(j-k)%MOD),add(f[i][j+1][k+1],f[i][j][k]*(i-k)%MOD);
}write(f[n][n][n]);

CF1037E Trips

题意:给出n个点,依次加入m条边,每加入一条边就询问,选出最大的点集使得其中每个点都有k个相邻点在集合中

请先思考后再展开

怎样回答一组询问?如果每次找到度数小于k的删掉,直到找不到为止,这样剩下的点集就是答案

于是倒着做即可,$O(nlogn)$,code

CF724E Goods transportation

题意:有$n \le 1e4$个点的网络流,$(S \to i,p_i),(i \to T,s_i),(\forall i<j,i \to j,C)$,问其最大流

请先思考后再展开

考虑最大流=最小割,设$f(i,cnt)$表示前i个点,S集的大小为cnt,$f(i,cnt)=min\ f(i-1,cnt-1)+s_i,f(i-1,cnt)+cnt*C+p_i$

$O(n^2)$,code

「MtOI2019」恶魔之树

请先思考后再展开

lcm明显是考虑质因子的次幂

对于比根号小的素数有2,3,5,7,11,13,17,考虑其合法的次幂,状态数为$S=9*6*4*3^4=17496$,可以作为突破口

注意到对于比根号大的素数(55个),因为每个数最多一个,所以是可以拆开来计算的

对于大素数的部分,注意到如果存在大素数,小质因子的次幂状态数会减少很多,具体而言是$S’=4*3*2^4=192$

于是我们只考虑存在大素数的数,每种素数分层做,设次数为cnt,设$dp(i,state)$表示考虑了前i个素数的带权方案和,每种方案的权值为其大质因子的积;转移的话,每种素数内部统计$cnt(state)$表示有多少个数去掉大素数后恰为state,复杂度$55*(S’)^2$

$dp(i,state \cup state2)+=dp(i-1,state)*prime*(2^{cnt(state2)}-1),dp(i,state \cup state2)+=dp(i,state)(2^{cnt(state2)}-1)$

另外处理出没有大素数的数的dp,$f(state)=这些数的子集,lcm恰为state$的方案数,因为本质不同的数只有300个,设每种数的出现次数为cnt,则$f(state2)+=f(state)*(2^{cnt}-1)$,复杂度为$300*S$;然后把有无大素数的两个数组合并,$S*S’$

总复杂度为$O(55*(S’)^2+300*S+S*S’)$,code

51nod1599 有趣的游戏

题意:$n \le 1e6$个无标号人玩游戏,规则是每次「随机选一个未出局的人出局并攻击其他未出局的人」直到所有人出局,被攻击者有$1-p$的概率受伤并出局;q次询问某个人(显然每个人答案相等)不曾受伤且恰被攻击$k_i$次的概率,$\sum k_i \le 1e6$

请先思考后再展开

为了不需要考虑每次出局多个人且统一轮数,考虑转化一下题意:

当一个人受伤的时候不直接出局,做n轮每轮选一个未出局的人出局,如果这个人没受伤就攻击别人;

然后每次允许攻击已受伤但为出局的人,显然对答案没有影响;不考虑具体某人,直接计算所有人的答案/n
$$
\\设dp_{i,k}表示第i轮且以前的人共发动了k次攻击,枚举是第i轮被选出,ans(k)=\frac{1}{n} \sum_{i=1}^{n} dp_{i-1,k}*p^k
\\dp_{0,0}=1,转移考虑第i轮被选出的人之前是否受伤,
dp_{i,k}=dp_{i-1,k-1}*p^{k-1}+dp_{i-1,k}*(1-p^k)
\\设g_{i,k}=dp_{i,k}*p^k,g_{i,k}=dp_{i-1,k-1}*p^k+dp_{i-1,k}*(1-p^k)
\\G_k=\sum_{i=0}^{\infty} g_{i,k}x^i,
ans(k)=\frac{p^k}{n} \sum_{i=0}^{n-1} G_k[x^i],
G_k=G_{k-1}*x*p^{k-1}+G_k*x*(1-p^k)
\\G_0=1,G_k
=\prod_{i=1}^k \frac{xp^{i-1}}{1-(1-p^i)x}
=x^kp^{k(k-1)/2} \prod_{i=1}^k \frac{1}{1-(1-p^i)x}
\\然后我们认为\prod_{i=1}^k \frac{1}{1-(1-p^i)x}可以被表示为\sum_{i=1}^k \frac{A_i}{1-(1-p^i)x},稍后说明
\\ans(k)
=\frac{p^{k(k+1)/2}}{n} \sum_{i=0}^{n-k-1} [x^i] (\sum_{j=1}^k \frac{1}{1-(1-p^j)x})
=\frac{p^{k(k+1)/2}}{n} \sum_{i=1}^k A_i*\frac{1-(1-p^i)^{n-k}}{1-(1-p^i)}
$$

至于那玩意为啥能这样表示,我并没有搞懂,谁会的话还请教教蒟蒻

总之我们装作这样的对所有x都成立的A总是存在,那么x怎么带入都没有问题,于是我们推推式子来求出这个A
$$
\\ \frac{1}{\prod_{i=1}^k1-(1-p^i)x}=\sum_{i=1}^k \frac{A_i}{1-(1-p^i)x},
1=A_i*(\prod_{j=1,j \ne i}^k 1-(1-p^j)x)+\sum_{oth \ne i} A_j*(something*(1-(1-p^i)x))
\\ 然后让我们带入x=\frac{1}{1-p^i}(有点CRT、插值之类的感觉,但好像也有点两边乘0的感觉啊其实)
\\ A_i
=\frac{1}{\prod_{j=1,j \ne i}^k 1-(1-p^j)x}
=\prod_{j=1,j \ne i}^k \frac{1-p^i}{p^j-p^i}
=(\frac{1}{p^i}-1)^{k-1} * \prod_{j=1,j \ne i}^k \frac{1}{p^{j-i}-1},
后面那个预处理个 \prod_{i=1}^{t} \frac{1}{p^{i}-1}就行了
$$
特判k=0,单组询问$O(klogn)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll pp[N],pi[N],pre[N];
void main()
{
int n=qread(),P=qread();
P=P*invm(qread())%MOD;pp[0]=1;fo(i,1,N-1) pp[i]=pp[i-1]*P%MOD;
ll Pi=invm(P);pi[0]=1;fo(i,1,N-1) pi[i]=pi[i-1]*Pi%MOD;
pre[0]=1;fo(i,1,N-1) pre[i]=pre[i-1]*invm(pp[i]-1)%MOD;
int q=qread();
while(q--)
{
int k=qread();ll ans=0;
if(k==0){write2(invm(n));continue;}
fo(i,1,k)
{
ll A=qpower(pi[i]-1,k-1);
A=A*pre[i-1]%MOD*pre[k-i]%MOD;
A=A*(i&1?1:-1)%MOD*qpower(P,ll(i-1)*i/2%(MOD-1))%MOD;
ans+=A*(1-qpower(1-pp[i],n-k))%MOD*pi[i],ans%=MOD;
}write2((ans+MOD)%MOD*qpower(P,ll(k+1)*k/2%(MOD-1))%MOD*invm(n)%MOD);
}
}

loj6495「雅礼集训 2018 Day1」树

请先思考后再展开

将1到n依次加入,动态维护排序后每个节点dep的差分状态,$O(n*(\sum_{t=0}^n 2^t))=O(n2^n)$

然后跟我一起喊——mldnb,然后来看看$O(n^3)$做法:设$f(siz,dep)$,然后转移的话,你发现节点2非常特殊,它只能连1而剩下点都能连它,所以枚举节点2的子树大小

$f(siz,dep)=\sum_{i=1}^{siz-1} f(i,d2<dep)*f(siz-i,dep)*C_{siz-2}^{i-1}+f(i,dep-1)*f(siz-i,\le dep)*C_{siz-2}^{i-1}$

code

loj6680 henry_y 的函数

请先思考后再展开

这种求多次前缀和,而且有个向下取整,很明显差分考虑贡献,即$f(n)-f(n-1)=2(\sum_{d|n} g_i * \frac{n}{i})-\sum_{d|n} g_d$

直接线性筛即可,$O(n)$,code

51nod1947 栈的代价和

请先思考后再展开

$$
\\设dp_{l,r}表示[l,r]的数的贡献,dp_{l,r}=\sum_{m=l}^r [l*(m-l+1)*Cat_{m-l}+dp_{l+r,m}]*Cat_{r-m}+Cat_{m-l}*dp_{m+1,r},O(n^3)
\\发现通过位移可以优化,设f_n表示权值都是1的n个数的答案,g_n则表示权值从1开始的答案,降低至O(n^2):
\\f_n
=\sum_{i=1}^n (iCat_{i-1}+f_{i-1})Cat_{n-i}+Cat_{i-1}f_{n-i}
=\sum_{i=1}^n iCat_{i-1}Cat_{n-i}+2Cat_{i-1}f_{n-i}
\\g_n
=\sum_{i=1}^n (iCat_{i-1}+g_{i-1}+f_{i-1})Cat_{n-i}+Cat_{i-1}*(g_{n-i}+if_{n-i})
=\sum_{i=1}^n iCat_{i-1}(Cat_{n-i}+f_{n-i})+2Cat_{i-1}g_{n-i}+Cat_{i-1}f_{n-i}
\\发现都是卷积的形式,大力设生成函数,为方便设C(x)=\sum_{i=0}^{\infty} Cat_ix^{i+1}(不然会死人的),F和G则是正常OGF
\\C=C^2+x,F=C’C+2CF,G=C’(C+F)+2CG+CF
$$

考虑到卡特兰数的生成函数已知,下面的东西的通项都是能解的,结果见这里

luogu5652 基础博弈练习题

请先思考后再展开

设$f(r)$表示r右边全都是必胜点下,有哪些左端点是必败点,那么$ans(l,r)=f(r).count(l)$

转移:$f(r)=[a_r偶]f(r-1) \cup a_r奇+r)$

将每个偶点根左边的点缩起来,缩完的点建成一棵树,那么你问题就是l是否是r的某个祖先

然后我睿智地不知道怎么线性做……

其实dfs序不就好了么……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int A,B,C,P;inline int rnd(){return A=(A*B+C)%P;}
int a[N],left[N];vc<int> son[N];int dfnid,dfn[N],siz[N];
void dfs(int x)
{
dfn[x]=++dfnid;siz[x]=1;
for(auto y:son[x]) dfs(y),siz[x]+=siz[y];
}
void main()
{
int n=qread(),m=qread()+1,q=qread(),type=qread();
fo(i,1,n) {a[i]=qread();left[i]=i;if(a[i]%2==0)left[i]=left[i-1];else if(i>=m) son[left[i-m]].PB(i);}
fo(i,0,m) if(left[i]==i) dfs(i);
if(type) A=qread(),B=qread(),C=qread(),P=qread();
unsigned int ans=0;
fo(tim,1,q)
{
int l,r;if(type==0) l=qread(),r=qread();else l=rnd()%n+1,r=rnd()%n+1;if(l>r)swap(l,r);
if(left[l]==l and dfn[l]<=dfn[left[r]] and dfn[left[r]]<=dfn[l]+siz[l]-1) ; else ans+=(unsigned int)tim*tim;
}
write(ans);
}

CF1043F Make It One

题意:给出一个n个数的序列a,求最短的子序列满足GCD=1,$n,a_i \le 3e5$

请先思考后再展开

我的做法:设$f(ln)=长度为ln的互质子序列个数,莫反得\sum_{d=1}^m \mu(d)C_{d的倍数个数}^{ln}$,预处理出倍数个数并处理出那些行组合数的前缀和(总量为$a*ln(a)$),二分判断在长度前缀是否存在即可,$O(aln(a)+aln(a)+alog_2n)$

正常人做法:考虑到每个数最多6个不同质因子,答案不会超过6;于是枚举答案做就行了,然后check的时候可能选择不前缀和的莫反,即直接求$f(ln)$,这样是6aloga,同时可见上面的做法组合数前缀和部分、求答案部分都可以变成6a

code

XSY2472 string KMP、[CTSC2006]歌唱王国

题意:给出一个01串S,现有一个空串T,每次随机在末尾添加0或1,出现S为T后缀时结束,问此时T的期望长度

复杂度要求:线性

请先思考后再展开

先kmp之类的求出每个位置下一个失配会跳到$to_i$

设$g_i=目前kmp匹配位置i,到结束的期望次数=1+\frac{1}{2}*(g_{i+1}+g_{to_i})$

方向比较恶心,但发现向右最多到i+1,考虑差分

设$f_i=kmp匹配位置从i到i+1的期望次数=\frac{1}{2}*1+\frac{1}{2}(1+\sum_{j=to_i}^i f_j )=2+\sum_{j=to_i}^{i-1} f_j$

歌唱王国的话应该差不多,to只会改$O(1)$个地方,维护每种字符对应和

loj2145「SHOI2017」分手是祝愿

请先思考后再展开

k=n的部分分很显然,从后往前按下不得不按的,这样一定是次数wt最小的,可以获得80pt(数据缘故)

然后万万没想到,正解居然跟这玩意有关:显然顺序是没有意义的,只考虑集合;将每个位置看做一个bit,表示其影响的位置,然后相当于选若干个异或起来等于现在给出的状态,现在通过上面的贪心我们已经获得一个bit集合S了

然后一个关键的性质:无法选出两个没有公共元素的bit集合A和B,使得两个集合异或出相同的状态,简单来说就是n个位置代表n个线性无关的状态

设目前操作集合为T,如果某次往里面加入$pos \notin S$,迟早需要将它从里面取出(也就是再按一次),然后你发现这个约数已经没啥用了,n个位置也就本质相同了
$$
\\g_i=想要取的bit个数=i的期望步数,g_i=i(i \le K)
\\g_i=1+\frac{i}{n}g_{i-1}+\frac{n-i}{n}g_{i+1},暴力解方程据说因为系数问题是95pt
\\方向不是很舒适,发现向右最多到i+1,考虑差分
\\\frac{i}{n}g_i+\frac{n-i}{n}g_{i}=1+\frac{i}{n}g_{i-1}+\frac{n-i}{n}g_{i+1},
\\f_i=想要取的bit个数从i到i-1的期望步数,f_i=1(i \le K),f_n=1
\\f_i=\frac{i}{n}*1+\frac{n-i}{n}(1+f_{i+1}+f_i)=\frac{n+(n-i)f_{i+1}}{i} (i >K)
\\ans=n!*\sum_{i=1}^{wt} f_k,O(nlogn)
$$
code

CSGRound2 开拓者的卓识

请先思考后再展开

搞不懂为啥luogu题解都这么复杂

首先显然可以隔板法得出式子:$f(1,r,k)=\sum_{i=1}^r C_{i-1+k-1}^{k-1}*C_{r-i+k-1}^{k-1}*a_i=\sum_{i=1}^r val_i*C_{r-i+k-1}^{r-i}$

直接FFT起来就行了,$O(nlogn)$

1
2
3
4
5
6
7
8
9
using namespace PP;//多项式板子
P V,A;
void main()
{
int n=qread(),K=qread();M=n+1;
V.rs(n+2);for(int i=1,now=1;i<=n;i++,now=1ll*now*(i+K-2)%MOD*inv[i-1]%MOD) V[i]=1ll*now*qread()%MOD;
A.rs(n+2);for(int i=0,now=1;i<=n;i++,now=1ll*now*(i+K-1)%MOD*inv[i]%MOD) A[i]=now;
A=A*V;fo(i,1,n) write1(A[i]);
}

「WC2010」重建计划

请先思考后再展开

01分数规划先二分,边权-=T,转化为判断是否存在长度在$[L,R]$内的非负边权和路径

跟链长也就是说深度有关,优先考虑长剖,得出新的$f(x,ln)$很容易,主要是怎么合并链更新答案

从长儿子继承后,遍历所有短儿子,$能与「f(y,ln-1)+e(x \to y)」组合的链长为[L-ln,R-ln]$

每次在这个链长范围内取最大值,无脑上线段树支持区间加、区间询问max是$O(nlog^2n)$

「LR11」Misaka Network与Accelerator

请先思考后再展开

明显是2-sat然后用数据结构优化建图,设$LN=R-L+1$

先说链的部分,直接上线段树优化太繁琐,一个精妙的方法是对序列按LN分块,于是每个限制对应的区间都是一段后缀+一段前缀,可以对每个块用前后缀优化建图,会好写很多,且为$O(m)$

放到树上就是对每个距离为$[L,R]$的路径,对两个端点分别搞事情

我们尝试点分,那么当两个子树合并的时候,枚举一侧向另一侧连边,发现连边的限制就是深度序列上长为LN的连续段

只要能维护好前后缀优化建图,连关键边部分的复杂度是$O(dep_a+dep_b)$,这部分还好

然后是将之间做完的两个子树合并,且维护前后缀优化:建立$O(max\ dep_a,dep_b)$个点,连向两侧即可

于是连边、合并两个子树的复杂度为$O(dep_a+dep_b)$,对于一层点分这东西无脑做肯定炸(一个扫把?),仔细思考发现其实可以看做$O(max\ dep_a,dep_b)$,每次按深度排序从小到大合并,复杂度就是$O(n)$的,总复杂度为$O(nlogn)$

代码写不来,告辞

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