关于方程

模拟赛的时候遇到一道所谓签到的期望题(,列出来式子不会处理只会高消,最后才发现有一个常规做法。之后接连回忆起了别的一些东西集合在这里,其实也没什么意思。

代码不在现在的机子上,找时间搬上来。

0x00 一些无聊的内容

CS Academy Amusment Park

题面

列出来式子期望等于

$$
\begin{split}
f(i, j)&=1+p(i, j)\times f(i,(j+1)\bmod A) \\
&+ (1−p(i, j))\times f(i - 1, (j+1)\bmod A)
\end{split}
$$

发现对于每一个i,这其实是一个简单环,那么我们可以随便拉出来一个f[j]设为x,每次记一下这一项的系数与常数,最后转移到自己的时候把x解出来代回去就行了。

Hello My Friend

给一棵树,每个点有黑白两种颜色之一,从根节点(度数大于1)开始随机游走。 你有一个计数器,初始为0,然后反复执行一下过程:
1. 如果当前点为黑色或者第一次经过,则计数器值加1。
2. 如果当前所在点度数为1,结束这个过程。
3. 等概率选取一个和当前所在点直接相连的点走过去。
求计数器最后数字的期望,对998244353取模

这个题就是我说的模拟赛里遇到的那个。

分黑白点算贡献就好了。

对于白点,肯定是算从1到它的概率,那么这个算出来走一步的概率一路乘下来就行了。

设x到fa的概率为$up_x$,一个点x从fa到x的概率为$dwn_x$ ,那么式子就是

$$
\begin{split}
up_x &= \frac{1}{deg_x} + \frac{1}{deg_x}\times \left(\sum_{v \in E_x}up_v\times up_x \right) \\
dwn_x=\frac{1}{deg_x} + \frac{1}{deg_x} &\times \left( \sum_{v\in E_{fa} \cup v\neq grand{}\cup v\neq x} up_v \times dwn_x + dwn_{fa} \times dwn_x\right)
\end{split}
$$

白点比较好处理,只需要化一下就可以直接在树上递推了。

对于黑点,设$f_x$ 为从x开始走到叶子的期望收益,那么方程就是

$$
f_x = col_x + \frac{1}{deg_x}\times \left( \sum_{v \in E_x}f_v+f_{fa}\right)
$$

貌似看起来只能高消了,但其实还是不用,貌似是一个很常见的技巧。仔细观察发现这个转移的整体图其实是若干个2元环嵌套在一块,那么我们从叶子开始,每次利用类似上一题的方法,比如设$f_{fa}$为x,然后将每次记录x的系数和常数项,每向上回溯一次我们就破掉了一个环,这样不停破环,就可以解出$f_1$(显然根节点的x项系数为0)。更具体点的话就是,在$f_x$先只统计$f_v$ 的贡献,由于$f_v$ 现在的样子是$k_vf_x+b_x$,对于x是一个常数,那么我们继续维护对于fa来说的$k_v$即可,每次在x处得到一个只和x与$fa_x$相关的方程。

其实只要转移图是由若干个只有点相交的环组成就可以这么做。

0x01 有点意思的东西

异或就比较有意思。
先从杜老师的题开始说起。

BJWC T2 Cross Sum

BJWC的时候一上来看到Apia四个字母吓傻了,一整场都是杜老师题可还行。

题面

问题转化成解异或方程组,解的元素不能为0且元素大小不超过$2^{60} -1$,解的元素值不能重复。

直接高消的话貌似复杂度不太可观,到了这一步,貌似我们陷入了瓶颈。

换个思路,考虑数形结合。

将限制看成点建立一个二分图,那么此时图里的方格就与这些可能存在的边一一对应。现在问题就变成了,有一个图,点有点权,我们希望求一个边权的解使得每个点的点权异或它出边的边权为0。

假设我们现在的方程是一棵树,那么我们可以从叶子慢慢merge上来,现在它是一个图。来仔细看看我们的异或操作会发现——这些非树边的加入对方程的可解性没有影响。所以实际上这里的非树边其实就相当于原方程组里的自由元。

那自由元怎么处理呢?事实证明rand就可以了。由于边权的范围是$2^{60}$级别的,冲突的概率差不多是和$1 - (1 - \frac{1}{2^{60}})^{|E|}<10^{-13}$ 一个级别的,看起来很靠谱。

如果dfs完毕之后还有非0的点权,那么一定不合法了。倘若这个图有解,那么我们随便拿一棵生成树出来都应该存在解,非树边的加入并不影响可解性。

这样的话我们的复杂度就是格子数目级别的了。$O(nm)$(那么问题来了为什么这题数据范围有点诡异),至此,这道题就被我们解决了。

话说BJ题在oj上这么冷的么QAQ。不过貌似杜老师在BJ出的题一向被人A的很少,BJOI2017的那道同构到现在bzoj 0 AC,1 submit。感觉这题的解法已经成了历史遗留问题……

BJOI Camp Practice Contest #2

有一个$n \times m $ 的01矩阵,矩阵中k 个格子的数已经确定,你需要求出有多少种方案使得矩阵每行每列的异或和均为1。对998244353取模。$n\leqslant 10^5, m\leqslant2\times 10^5,k \leqslant 2\times 10^6$

出题人在课件里面写的std是一个$O(\frac{k^2}{nm} \times 2^{\frac{k}{m}})$的dp,但如果我们沿着上一题的思路去想,其实可以$O(n+m)$。

沿着上一道题的思路建出来一个二分图,设$num$为图中的非树边条数,那么$2^{num}$就是最后的答案。

然后我们惊奇地发现,这个东西其实和它每个位置填的数具体是啥根本没关系,只和这个数填的位置有关,interesting。

现在问题来了,如何求非树边条数呢,可以通过连通块数求得。设连通块数为$s$,那么非树边条数就是$M -( N - s)$,在这里N是总点数,M是总边数。至于求连通块数,由于它可能很稠,在遍历边的时候有许多边是没有用的,可以按顺序将节点加入一个链表,每次只选没访问过的当前点可访问的点访问。由于每个点只会被访问一次,这道题就在$O(n+m)$的时间做完了,嘻嘻 φ(>ω<*)

· EOF ·

Comments
Write a Comment