Codeforces Round #146 (Div. 1) (cf235X)

陈老师经典场。

B. Let’s Play Osu!

题意:n个连续的位置,每个位置可能是O或X,一段最长的连续的O对得分的贡献是l^2,l为长度。给你每个位置是O的概率,问期望得分。

g[i]表示以i结尾的连续O的期望长度,则g[i]=(g[i-1]+1)*p[i]
f[i]表示以i结尾的期望答案,则f[i]=f[i-1] * (1-p[i])+(f[i-1]+2 * g[i-1]+1) * p[i]

C. Cyclical Quest

题意:给串S和T,问S中有多少字串和T是循环同构的。
对S建立后缀自动机,然后把T复制一遍接在自己后面构成T’,用T’在后缀自动机里匹配。
具体方法:
我们设T[i]是T以位置i结尾的前缀与S的最长公共字串,包含两个值:p(最长公共字串在SAM里的状态)和len(长度),然后我们要由T[i]得到T[i+1],设c为下一个字符,考虑两种情况:
1. trans[i][c]存在:p=trans[i][c], len = len + 1即可。
2. trans[i][c]不存在:我们沿着fa指针往上走直到trans[i][c]存在即可。每走一步更新len=maxlen[p](因为len表示最长的匹配长度,而p状态表示的所有串都可以匹配,所以自然应该令len=maxlen[p])。如果走到了根节点还不存在那么令p=root, len=0
然后如果某个时刻len\geq n那么答案加上siz[p]。然后注意,可能有多个位置i都满足len\geq n且p相同,但是我们只能算一次,所以要记录SAM的每一个位置是否被统计过。
还有一种特殊情况,即当满足len\geq n时,p并不是以i结尾的T的循环字串所在的状态,真正的状态可能在p的fa链上。即,T'[i-len+1\ldots i]一定在状态p中,但T'[i-n+1\ldots i]不一定在状态p中,它是T'[i-len+1\ldots i]的一个后缀,根据SAM的性质,它可能出现在p的fa链上。要处理这种情况,只需要一直沿着p的fa指针向上,找到最“上”的状态p’满足maxlen[p']\geq n,则T'[i-n+1\ldots i]一定在p’中。

D. Graph Game

题意:一个基环树T,定义函数solve(T):

  1. totCost+=size(T)
  2. 以均等的概率选择T中的一个点x
  3. 删去x,此时T被分成若干联通块
  4. 对每个联通块执行solve

问totCost的期望。

先考虑T是一棵树:
设事件E(a, b)表示当a被删去时,b与a联通。则E发生会对答案贡献1。
于是我们只要求出对于每个点对(a,b),E(a,b)发生的概率就行了。
设n等于a到b的路径上的点的个数,则这个概率就是1/n
这个可以用数学归纳法证明:

  • 如果当前的联通块只有n个节点,那么显然P=1/n
  • 如果当前联通块有x个节点(x>n),那么选择一个点删去有两种情况:
    1. 该点为n个点之一:P_1=\frac nx\frac 1n=\frac 1x
    2. 该点为其他点:P_2=\frac {x-n}x\cdot P',其中P'是删去该点后在包含路径(a,b)的联通块中发生事件的概率,显然该联通块的大小小于x,且包含了完整的n个点,所以P'=1/n

两个概率加起来便等于1/n
这个问题便解决了,接下来考虑基环树的情况:
当a到b只有一条路径时贡献仍是1/n
当a到b有两条路径时:第一条贡献1/n(删掉a时第一条路径存在),第二条贡献1/m(删掉a时第二条路径存在),然后还要减去两条路径的并的贡献1/{(n\cap m)}(删掉a时两条路径都存在)。

E. Number Challenge

题意:定义d(n)为n的因子的个数,求:
$$\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c d(i\cdot j\cdot k)$$
首先我们要知道一个结论:
$$d(i\cdot j\cdot k)=\sum_{i’\mid i}\sum_{j’\mid j}\sum_{k’\mid k}[gcd(i’,j’)=gcd(j’,k’)=gcd(i’,k’)=1]$$
因此
$$\sum_{i=1}^a\sum_{j=1}^b\sum_{k=1}^c d(i\cdot j\cdot k)=\sum_{gcd(i,j)=gcd(j,k)=gcd(i,k)=1}\lfloor\frac ai\rfloor\lfloor\frac bj\rfloor\lfloor\frac ck\rfloor$$
证明:http://rng.gozaru.jp/b.pdf

然后就可以莫比乌斯函数搞一搞了。

发表评论