计数与期望题目选做

这些题目收集自各个奇怪的地方,因为还没有排好序,索引可能不太方便,所以查找请用Ctrl+F;建议拿来做专题,可以按顺序来做。

检查计数的正确性:方案合法、方案不重复、方案不遗漏。

TCO2016 Round 2B easy TriangleTriples

题目大意
对于给定的A,B,CA,B,C,求满足1aA1\leq a\leq A,1bB1\leq b\leq B,1cC1\leq c\leq Ca,b,ca,b,c能组成三角形的正整数三元组的个数。A,B,C109A,B,C\leq 10^9

算法讨论
如果讨论满足a+b>ca+b>c等条件的三元组的个数的话很容易有重复计数。那么考虑容斥原理,设f(A,B,C)f(A,B,C)为满足aA,bB,cCa\leq A,b\leq B,c\leq Ca+bca+b\leq c的个数,则答案为ABCf(A,B,C)f(A,C,B)f(B,A,C)ABC-f(A,B,C)-f(A,C,B)-f(B,A,C)

为什么没有重复计数?在f(A,B,C)f(A,B,C)中,有a+bca+b\leq c,很明显可以得到b+c>ab+c>a,那么就不会被f(B,C,A)f(B,C,A)计入。f(A,C,B)f(A,C,B)同理。

ff也要用容斥求。设g(A)g(A)为满足a+bcAa+b\leq c\leq A的三元组个数。

g(A)=c=2Aa=1c1(ca)g(A)=\sum_ {c=2}^A\sum_ {a=1}^{c-1}(c-a)

用一下各种前缀和公式就能求出来啦。

看一下ffgg的关系。g(C)g(C)f(A,B,C)f(A,B,C)多的部分就是a>Aa>Ab>Bb>B的部分。统计a>Aa>A的部分时,不妨令a=a+A,c=c+Aa=a'+A,c=c'+A,那么用g(CA)g(C-A)得到的就是a+bcCAa'+b\leq c'\leq C-A,即a+bcCa+b\leq c\leq Ca>Aa>A的三元组的数量。用一下简单的容斥,

f(A,B,C)=g(C)g(CA)g(CB)+g(CAB)f(A,B,C)=g(C)-g(C-A)-g(C-B)+g(C-A-B)

倒回去就行了。时间复杂度O(1)O(1)

题目还是挺精巧的,但是解法十分不对称,写起来不是很舒服。

Claris’ Contest #4 shopping

题目大意
nn个商店,前mm个有消费上限wiw_ i。已知总消费额,问有多少种不同的账单。n5×106n\leq 5\times 10^6m300m\leq 300wi300w_ i\leq 300

算法讨论
BZOJ省队十连测第一场

K Perm Counting

题目大意
这个问题是错排问题的升级版。给定N,KN,K,问有多少个排列ai{a_ i}使得aiik\left | a_ i-i\right | \neq k

算法讨论
在APIO上听clj大神讲这道题:

考虑使用容斥原理来计算有kkaia_ i不合法的方案的数量。

简单的dp就可以了。

对,我也是这么想的,只是陈老师知道怎么做,我不知道。

总体思路当然是设fif_ i为恰有ii个数不合法的排列个数。容斥一波,答案就是

N!+i=1N(1)ifiN!+\sum_ {i=1}^N(-1)^i\cdot f_ i

后来上网看了资料,发现自己的一个idea是行的通的。在计算fif_ i的过程中碰到的一个很大的问题就是ai{a_ i}们选择的值可能会冲突!但是冲突的只可能是模KK相等的数。所以把他们拆开来考虑,设g[r][i]g[r][i]为模k=rk=r那若干个数恰有ii个是不合法时的方案数,再用一个背包来把不同的rr之间的结果合并。

愚蠢的我想用组合数级复杂度(暴力复杂度)地枚举每个gg的结果对ff的贡献,一度认为该方法行不通!实践证明,要坚持~~走有中国特色的社……~~自己的思路,顺着走下去,不能放过那些一闪而过的灵光!

SRM 564 Div1 AlternateColors2

题目大意
rr个红球,gg个绿球,bb个蓝球,机器人每次消灭一个球,按红、绿、蓝、红、绿、蓝……的顺序消灭;如果消灭到某种球的时候这种球没有了,那么就跳过。问如果第kk次消灭的是红球,且r+g+b=nr+g+b=n,问有多少中r,g,br,g,b的取值方案。1kn1000101\leq k\leq n\leq 100010r,g,br,g,b可能为0。

算法讨论
一种常见的思路,就是我们枚举点什么东西,然后用加法原理求和。但是对于这道题,在时间复杂度的限制下,我们只能枚举r,g,br,g,b中的一个的取值;我们要确定下第k次消灭的球的颜色,必须需要知道所有颜色球的个数才行。所以不能直接枚举r,g,br,g,b的值。

那就分类讨论吧。我们把红、绿、蓝依次消灭一遍叫做“一轮”,我们对第kk次消灭属于的那一轮开始前的状态进行讨论:

  1. 三种球都还有,那么第k次之前一共执行了k13\frac{k-1}{3}轮。这种情况只有当kmod3=1k\bmod 3=1时才可能出现。
  2. 只剩下两种球了,那必须要有一种是红球才行。
  3. 只剩下一种球了,这种球一定是红球。

对于第一种情况,可以直接得到r,g,bk+23r,g,b\geq\frac{k+2}{3}。注意k+23\frac{k+2}{3}是因为我们要求第kk次之前的时候三种球都还有,所以要把第k+1k+1次和第k+2k+2次消灭的也算上。第k+23\frac{k+2}{3}轮后剩余球的数量是nk2n-k-2个,用插板法(同颜色球无区别)得出有(nk)(nk1)2\frac{(n-k)(n-k-1)}{2}种情况。

第二、第三种情况真的没什么好办法可以直接判断,所以我们枚举第一种情况的长度(设为i)后令n-=i*3k-=i*3,蓝球和绿球没有本质区别,所以设剩下的是绿球,之后在计算贡献的时候乘二就好了。

接下来就是两个球的分配问题了。我们要使第kk次消灭的是红球,如果有kmod2=1k\bmod 2=1,第kk次消灭就有可能是属于第二种情况。和上面同理,第二种情况要求r,gk+12r,g\geq \frac{k+1}{2},满足这个限制后还有nk1n-k-1个可以随便分配颜色的球,同样插板法(或者不用也行)得出有nkn-k种可能。

再考虑到了情况3。到达情况3要求g<k+12g<\left\lfloor\frac{k+1}{2}\right\rfloor,除此之外没啥限制,所以有g<k+12g<\left\lfloor\frac{k+1}{2}\right\rfloor中可能。

把上面三种情况统计得到答案之后,还不是正确答案。在枚举情况1长度i再考虑情况2、3的时候,还有另外一种情况:如果第i轮之后就立刻除了红球以外没有别的球了,这只有一种可能,但是在计算ggbb的时候都考虑重复了,只要简单的在枚举每一个合法i的时候ans--就OK了。

我的代码

The Child and Binary Tree

Codeforces438E BZOJ3625
题目大意
给定m,nm,n,对于每一个1sm1\leq s\leq m,问有nn个节点且点权和为ss的二叉树有多少种。每个点的权值只能属于给定的一个正整数的子集。

算法讨论
这个是和生成函数有关的多项式计算题,之后另发表一篇文章讲。先挖坑于此。

换树边

题目大意
给定一棵有标号无根树,问经过不超过k次换边操作(删边再加边)能够得到多少种不同的树。n50n\leq 50

算法讨论
这道题没做出来说明我不会证明矩阵树定理,相当于没学。

设原有的边权为11,不存在的边权为xx,硬生生凑成完全图,然后做矩阵树。因为矩阵树算的是所有生成树边权乘积的和,所以换kk条边后的树的个数为xkx^k项的系数。

行列式+多项式不太好做,可以选择和FFT一样的思路,先点值再插值。我的实现用了高斯消元+拉格朗日。

我的代码

序列迭代

题目大意
一开始有一个11nn的序列,每次操作前无限重复该序列,然后截取前xx项。问操作完成后序列里11nn出现次数分别是多少。n105,x1018n\leq 10^5,x\leq 10^{18}

算法讨论
如果取了xix_ i后再取xjx_ jxi>xjx_ i>x_ j,那么xix_ i无效。所以用一个单调栈维护出严格递增的xx

一个新的序列是怎么构成的?假设第ii次操作后的序列为AiA_ i,那么

Ai=xixi1Ai1+Ai1[1,ximodxi1]A_ i=\left\lfloor\frac{x_ i}{x_ {i-1}}\right\rfloor A_ {i-1}+A_ {i-1}[1,x_ i\bmod x_ {i-1}]

这个显然,我也想到了。还有另外一个性质我也想到了,就是从11nn,出现次数不下降。用上面这个式子能推得出来。但是这两个东西结合到一起,又该怎么做呢?

AiA_ i在最终序列中出现的次数为f[i]f[i]。我们从后往前枚举序列AiA_ i,令B=AiB=A_ i,碰到一个序列jj,因为AiA_ i出现了f[i]f[i]次,所以在BB中出现了Bxj\left\lfloor\frac{\left|B\right|}{x_ j}\right\rfloor个完整的AjA_ j,那么让f[j]+=Bxjf[i]f[j]+=\left\lfloor\frac{\left|B\right|}{x_ j}\right\rfloor\cdot f[i]。然后我们不要管前面完整的AjA_ j了(由完整的AjA_ j产生的对答案的贡献轮到它的时候再算),令B=Aj[1,BmodAj]B=A_ j[1,\left|B\right|\bmod A_ j]。如果找不到比BB短的序列,甚至比原序列还段,说明BBAiA_ i在前面所有的完整重复之后还多出来的部分,所以让BB中的元素的出现次数加上f[i]f[i]

实现细节
我们只需要记录BB的最后一个元素kk,在结束时cnt[k]+=f[i]cnt[k]+=f[i],先不处理小于kk的;所有的序列都处理完后,根据出现次数递减,知道后面出现了的前面一定会出现,因此O(n)O(n)求出cntcnt数组的后缀和就是答案。

找比BB短的序列要用二分查找,直接循环判断会达到O(n2)O(n^2)

总的时间复杂度我不是很会算,因为牵涉到xx的取值。好像是O(nlognlogx)O(n\log n\log x)

BZOJ十连测第六场 cake

题目大意
用一刀分开一个n×nn\times n的有标号正方形点阵,点不能在分割线上,直线两边必须都有点。问分配方案数。n109n\leq 10^9

算法讨论
正解用了一个很巧妙的结论,没想到的话连暴力分都水不了!

总分配方案数等于以点阵上的点为端点且不经过第三个点的线段数

证明分两步:

  • 每一条不经过其他点的线段,我们令它绕中点顺时针旋转一个极小的角度,无限延伸,这样就得到了一个方案
  • 对于每一个分割方案的直线,逆时针旋转到卡住,连接把它卡住的那两个点形成一条唯一的线段。

于是两种计数方案是一一对应的,证明完毕。如此简洁优美!为了搞出类似这样的结论,我还毕克定理都用上了,推完发现是错的。

很容易想到两个点连线不经过其他点当且仅当坐标差绝对值互质。水平和竖直方向的答案为2n(n1)2\cdot n(n-1),斜着的考虑左下-右上后贡献×2\times2即可。枚举坐标差绝对值,要求的就是

i=1nj=1n(ni)(nj)[gcd(i,j)==1]\sum_ {i=1}^n\sum_ {j=1}^n(n-i)(n-j)[gcd(i,j)==1]

为了简化问题,再分类讨论!i=j=1i=j=1只有一种情况,iji\neq j时贡献×2\times 2即可。不妨设i>ji>j

i=1nj=1i1(ni)(nj)[gcd(i,j)==1]\sum_ {i=1}^n\sum_ {j=1}^{i-1}(n-i)(n-j)[gcd(i,j)==1]

记得GDKOI2017上是怎么求比自己小的数且和自己互素的数的和的吗?用欧拉函数可以比莫比乌斯函数方便很多,当然前缀和就没那么方便了,但不失为一种办法。

=i=2n(ni)(φ(i)nφ(i)i2)=\sum_ {i=2}^n(n-i)(\varphi(i)\cdot n-\frac{\varphi(i)\cdot i}{2})

展开后本质是要求i=1nφ(i)ik\sum_ {i=1}^n\varphi(i)\cdot i^k杜教筛筛筛即可。

我的代码

变色的图

题目大意
给一棵最多nn条边的无向联通图,每个点要么是白色,要么是黑色。初始时的颜色都是白色,每次操作可以将一条两个端点同色的边的两个端点同时变色,问最少多少步能够让所有点变黑。n105n\leq 10^5

算法讨论
图要么是树,要么是基环树。然后树形+环形DP?我在DP的时候不断地推翻自己的转移方程,最后发现贪心直接相加是有问题的,因为题目有要求“两端颜色相同”。

题解的第一步转化充分展示了出题人的大脑洞。先考虑树,因为树是二分图,染色之(注意这里是新的染色),我们要干的事情就是把整个图反色。而对比一下原图反色的条件,原图要求两边相同,对应过来就是要求两边不同。因此一个反色操作可以认为是在新图上将一条边两端的颜色交换,颜色相同(即原图颜色不同)的交换是浪费时间浪费生命的!在计算最优答案的时候会自动删掉这种操作。这一步太巧妙了。

设黑色标记的权为+1+1,白点的权为1-1,这里的白点是不能动的,一条边两端颜色交换看作是黑色标记的移动,目标就是使每一个点上的权值和均为0。更加形象地说,就是有一个nn烷分子(不考虑氢原子),上面的电子分配有问题,于是有n2\frac{n}{2}个空穴和自由电子,带空穴的碳原子是显正电(权)的,带多余电子的是显负电(权)的,这些电子和空穴可以沿着σ\sigma键移动。那么带正电的地方“电势”比较高,肯定会往”电势“低的地方跑,找一个匹配的原子安家。这一段属于胡说八道,认为没有道理可以直接忽略。

回归到黑色标记和固定白点那一套。黑色标记只能沿着树边跑,树的性质决定了匹配完成后路径唯一。所以一条边被经过的次数就至少为以其中一个端点为根,不经过该边的子树的权值和的绝对值(就是总电荷量),设这个绝对值为fif_ i,总答案就是i=1nfi\sum_{i=1}^n f_ i

但是怎么证明可以对于每一条边都取得到这个下界呢?首先,因为图是联通的,又同时存在白点和黑点,所以一定有边两端颜色不同;设一条边(A,B)(A,B),不妨AA是白点,BB是黑点,如果它在交换后更劣,即交换后两边权值和的差变大,说明BB侧的白点很多,AA侧黑点很多。找出BB所在的黑色联通块,取一条它和白色联通块的连边——一定存在白色联通块,因为白点多——而且这条边不能是(A,B)(A,B),显然这条边交换后更优。因此总存在一条用一次交换后能够使fif_ i减少一的边,而i=1nfi\sum_{i=1}^n f_ i有限,算法能够结束,说明我们总存在一种方案取得到下界。这就是树的做法。

环分奇环和偶环:

  • 奇环相当于添加了一种新边,使得新边两端的黑色标记可以同时产生或者同时消失。因为奇环的存在,总电荷量可以不为0,但是总电荷量决定了我们至少要同时产生/消失多少次,把这个数量加到这条新边两端的点权里面就可以了。
  • 偶环添加了一条普通边。设我们要通过这条边运输xx个黑色标记,只有要经过环的运输路径需要考虑是否改成通过xx来运输。对于每一条旧边,如果新边的端点在同一侧,那么不需要考虑xx对这条旧边的影响;反之,这条旧边实际需要通过的黑色标记数量为fix\left|f_ i-x\right|这种形式的,取xx为中位数就能使答案最优。

有几种不可能的方案需要特判一下。

我的代码

拓展延伸
我想了一下,如果只有偶环,但不止一个,那么应该成了费用流问题。原图每一条边的费用为11,源点向正权点、负权点向汇点连容量为1、费用为0的边,建图完成。虽然是二分图,但是好像没有办法转化成最大权匹配。

Dictionary

题目大意
给定nn个仅由小写字母和?组成的字符串,问有多少种把?换成小写字母的方法使得字符串递增。n20n\leq 20,字符串长度50\leq 50

算法讨论
clj还是什么都没讲:

考虑一位一位地确定所有串,那么就被分成了很多子问题,就可以做了。

就可以做了,就没有然后了。

我自己想了一种方法:这些串在一个一个位DP的时候的取值和是否在前面有上限限制有关系,那么把每一个串的前第ii位是否比下一个串小作为状态压起来DP就可以了。

我好像也没讲什么。

SDOI 2009 HH去散步

BZOJ1875
题目大意
给一个有重边无自环的无向图。求从sstt有多少种长度为kk的不连续经过同一条边的路径。边数点数100\leq 100

算法讨论
考虑没有不能连续经过同一条边的限制,那么用无向图的边构造转移矩阵,快速幂即可。

为了保证不走同一条边,把用点DP改成用边DP即可,反正无向边拆成两条有向边之后边的终点是确定的。

Claris’s Contest #4 sailing

题目大意
在一个格子图上有一些障碍,有一些选定点可以同时上下左右移动,只要有一个会撞到障碍则这种方案不合法。问从当前局面开始移动有多少种合法位置。边界长度700\leq 700

算法讨论
BZOJ省队十连测第一场

SRM MAZE

题目大意
给一个有障碍的n×mn\times m的格子图,选两个格子,同时上下左右移动,碰到障碍的那个格子保持不动(和上一题不一样!)。问有多少种选格子方案能够只让一个格子跑出边界。n,m100n,m\leq 100

算法讨论
两个格子只能同时存在或者同时出去的这种关系是具有传递性的,所以可以用是否存在这种关系来划分等价类,所以用记忆化搜索+并查集加速。答案为任意放方案数减去放在一个等价类里的方案数。

Counting on a Tree

CodeChefTREECNT2
题目大意
给一棵树,有可以修改的边权,问每次修改前后路径边权gcd为1的有多少条。n105,q100n\leq 10^5,q\leq 100,边权w1000000w\leq1000000

算法讨论
考虑容斥。设f(i)f(i)为路径gcd为ii的倍数的路径的条数,那么答案等于i=1+f(i)μ(i)\sum_ {i=1}^{+\infty}f(i)\mu(i)

然后把边用这个ii拆开来,拆出来的边数应该是O(logn)O(\log n)级的。一个联通块内的所有n(n+1)2\frac{n(n+1)}{2}个路径的权值都是ii的倍数,所以维护连通块即可。因为还可能要拆开,用并查集的话会被修改的边(离线找出来)不能路径压缩,只能按秩合并。也可以用无关的边建出了初始并查集之后储存一下,恢复的时候直接拷贝就好了。有 O(q)O(q)条有关系的边,每次计算一个边要重建所有有关系的边的并查集,加上建立无关边的并查集,时间复杂度应该是O((n+q2)logwlogn)O((n+q^2)\log w\log n)

格子染色

题目大意 nn个格子排成一行,每次随机选择一个区间染色,问将所有格子都染色的期望操作次数。

算法讨论 设计2n2^n的状态,列出方程,递推。

思路归纳 有一些状态不一定能达到,但是最终的答案应该是对的。那些达不到的状态的期望应该是被乘上了出现它的概率。

算法讨论 考虑操作了xx步之后全黑(在第xx步之前全黑也可以)的概率P(x)P(x),如果操作完这么多步还没有被染色,那就还至少要再走一步,这一步对答案的贡献就为E(x)=P(x)0+[1P(x)]1=1P(x)E(x)=P(x)\cdot0+[1-P(x)]\cdot1=1-P(x)

那么答案就是

i=0+E(i)\sum_{i=0}^{+\infty}E(i)

=i=0+(1P(i))=\sum_{i=0}^{+\infty}(1-P(i))

选出一些格子,设这些格子组成的集合为SS,钦定SS不能染色的合法区间数量为F(S)F(S),容斥一波得到

=i=0+(1S(1)S(F(S)n(n+1)2)i)=\sum_{i=0}^{+\infty}(1-\sum_S(-1)^{\left|S\right|}(\frac{F(S)}{\frac{n(n+1)}{2}})^i)

=i=0+S(1)S+1(F(S)n(n+1)2)i=\sum_{i=0}^{+\infty}\sum_{S\neq\varnothing}(-1)^{\left|S\right|+1}(\frac{F(S)}{\frac{n(n+1)}{2}})^i

=S(1)S+1i=0+(F(S)n(n+1)2)i=\sum_{S\neq\varnothing}(-1)^{\left|S\right|+1}\sum_{i=0}^{+\infty}(\frac{F(S)}{\frac{n(n+1)}{2}})^i

=S(1)S+111F(S)n(n+1)2=\sum_{S\neq\varnothing}(-1)^{\left|S\right|+1}\frac{1}{1-\frac{F(S)}{\frac{n(n+1)}{2}}}

接下来对格子从左到有右DP就好啦。有后效性的状态就是已经选择的不能染色的格子数量,以及合法区间数量。

思路归纳 这种方式考虑的是每一步的贡献。

算法讨论 记格子ii第一次被染上色是在第xix_i步之后。答案就是

E[max{xii[1,n]}]\mathbb{E}\left[max\{x_i|i\in[1,n]\}\right]

如果把xix_i看作是一个{1,2,3,...,xi}\{1,2,3,...,x_i\}的集合,那么max{xii[1,n]}max\{x_i|i\in[1,n]\}就是一个集合并操作。然而集合并是可以用集合交容斥的:

E[maxi[1,n]xi]=S(1)S+1E[miniSxi]\mathbb{E}\left[\max_{i\in[1,n]}x_i\right]=\sum_{S\neq\varnothing}(-1)^{\left|S\right|+1}\mathbb{E}\left[\min_{i\in S}x_i\right]

后面那个期望的意义是,某一些格子第一次被染色的时间,实际上就是前面那么多次没有染上,最后一次染上了。

E[miniSxi]=i=1+(F(S)n(n+1)2)i1(1F(S)n(n+1)2)\mathbb{E}\left[\min_{i\in S}x_i\right]=\sum_{i=1}^{+\infty}(\frac{F(S)}{\frac{n(n+1)}{2}})^{i-1}(1-\frac{F(S)}{\frac{n(n+1)}{2}})

可以证明这个在数学上是等价于i=0+(F(S)n(n+1)2)i\sum_{i=0}^{+\infty}(\frac{F(S)}{\frac{n(n+1)}{2}})^i的。

思路归纳 深刻理解容斥,理解期望线性性!

概率论

BZOJ4001
题目大意
nn个节点的二叉树的期望叶子节点个数。n109n\leq10^9

算法讨论
首先nn个节点的二叉树个数,即卡特兰数的生成函数:

C(x)=xC2(x)+1C(x)=xC^2(x)+1

C(x)=114x2xC(x)=\frac{1-\sqrt{1-4x}}{2x}

另一个根因为x0x\rightarrow0处不符合条件所以舍去。

G(x)G(x)为所有nn个节点的树叶子个数的总和的生成函数。对于nn个节点树,考虑枚举左右儿子的贡献。得

G(x)=2xG(x)C(x)+xG(x)=2xG(x)C(x)+x

G(x)=x12xC(x)G(x)=\frac{x}{1-2xC(x)}

=x14x=\frac{x}{\sqrt{1-4x}}

因为nn很大,所以不能多项式开根、求逆元,只能展开来看怎么算。牛顿二项式/泰勒展开:

G(x)=x(14x)12G(x)=x(1-4x)^{-\frac{1}{2}}

=xi=0+(4x)i(12i)=x\sum_{i=0}^{+\infty}(-4x)^i\binom{\frac{1}{2}}{i}

=xi=0+(4x)ij=1i(12j)i!=x\sum_{i=0}^{+\infty}(-4x)^i\frac{\prod_{j=1}^{i}(\frac{1}{2}-j)}{i!}

=xi=0+(2x)ij=1i(2j1)i!=x\sum_{i=0}^{+\infty}(2x)^i\frac{\prod_{j=1}^{i}(2j-1)}{i!}

=xi=0+(2x)i(2i)!i!j=1i2j=x\sum_{i=0}^{+\infty}(2x)^i\frac{(2i)!}{i!\prod_{j=1}^{i}2j}

=xi=0+(2ii)xi=x\sum_{i=0}^{+\infty}\binom{2i}{i}x^i

然后又知道第nn项卡特兰数为(2nn)n+1\frac{\binom{2n}{n}}{n+1},所以期望为

(2(n1)n1)(2nn)n+1=n(n+1)2(2n1)\frac{\binom{2(n-1)}{n-1}}{\frac{\binom{2n}{n}}{n+1}}=\frac{n(n+1)}{2(2n-1)}

O(1)\mathrm{O}(1)

avatar
Kerry Su