23.3.18 考试小记

发布于 2018-03-23  2.54k 次阅读


T1

其实这玩意可以直接把期望去掉,换成所有MST的和,最后除一下方案数即可。

f[n][m]:n个点,最高位为m的MST权值之和。

g[a][b][i]:最高位为第i位的情况下,0的个数为a,1的个数为b的最小边权和。

p[a][b][i][s]:最高位为第i位的情况下,0的个数为a,1的个数为b,最小边权大于等于s的方案数。

$$f_{n,m}=2f_{n,m-1}+\sum _{i=1} ^{n-1} C_{n}^{i} (f_{i,m-1}2^{(n-i)(m-1)}+f_{n-i,m-1}2^{i*(m-1)}+g_{i,n-i,m-1}+2^{n(m-1)}\,2^{m-1})$$

考虑两个集合S,T,其中S中的点权的最高位为1,T的为0,那么我们枚举集合的大小,用m-1位的左边随便填的方案数乘上右边的权值和加上反过来的,再加上两个集合m-1位的最小边权和,再加上当前位的贡献(=单个贡献2^(m-1)*方案数2^(n*(m-1)))即可。

直接算g不好搞,那么就可以用p之和表示g,因为p比较好算,对于一个合法状态,还是枚举两个集合S、T(最高位不确定),枚举S、T中1的个数,那么最优的方案就是让S0与T0连边,S1与T1连边,

 

 

T2

题意略。

首先,考虑满足这个规定的数字的性质,这是迈向多项式算法的第一步。如果一个数字有大于1个循环节,那么不论如何一定会出现不合法的情况。因此,首先要满足的是整个数字不循环。其次,对于每种不循环的数,从每个位置“循环”拆开会得到n个串,这n个串只有字典序最小的一个是合法的,其他任意的循环移位均会创造不合法的条件。

那么,我们可以用mu做容斥系数来搞一搞:

$$f(n)= \frac {\sum _{d|n} 10^{\frac{n}{d}} \mu (d) } {n} $$

接着,我们来一步一步向答案靠近:

$$ans=\sum _{i=1} ^{n} i^{2} f(i)$$

$$=\sum_{i=1}^{n} i \sum _{d|i} 10^{\frac{i}{d}} \mu(d) $$

$$=\sum _{d=1} ^{n} \mu(d) \, d \sum_{t=1} ^{\frac{n}{d}} t *10^{t}$$
设S(n)为前一半,g(n)为后一半。

$$S(n)=\sum _{i=1}^{n} 10^{i} i =\sum_{i=1}^{n} \sum _{j=i}^{n} 10^{j}$$

有了这个转化,就可以用高考数学的知识O(logn)搞掉了,或者可以用类似分治的方法搞掉(多一个log)。

g(n)可以杜教筛。

$$1=\sum_{i=1}^{n}i \sum _{d|i} \mu (d) = \sum _{d=1} ^{n} \mu(d) d \sum _{t=1} ^{\frac{n}{d}} t  \\ = \sum _{t=1}^{n}t \, g(\frac{n}{t})$$

$$g(n)=1-\sum_{t=2}^{n} t\,g(\frac{n}{t})$$

然后就做完了,然而考场上第一个转化都想不到,如果想到了的话应该就有60了吧。

 

T3

考场上先写了70分暴力(实际能有80分),看在前两题都不太会的份上,我就去写了这题的正解。

首先,我们O(n)枚举出向上下左右的步数abcd,然后转化一下:

$$\sum _{a,b,c,d} C_{n}^{a}C_{n-a}^{b}C_{n-a-b}^{c}=\frac{n!}{a!b!c!d!}$$

之后,最恶心的就是模数出现相同质因子的情况。我们设模数可以拆成pi^ai的乘积,那么每个pi都是互质的,我们可以算出关于pi^ai的答案之后CRT合并一下。考虑我们在p^k下进行a/b的运算,其中a=n*p^x,b=m*p^y,那么n和m都不含p这个因子,在模p^k意义下一定存在逆元,我们可以存p的指数,之后给n乘上m的逆元,最后要还原回原数就好了。

我的程序好像还有点bug?在一个大质数的时候算逆元比较慢,可以判一下然后线性推逆元,就少了一个log。

下面的是我的考试程序,里面的分段暴力可以避免这种特判。

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974