PKUWC2019爆0记
访问量该骗的还是要骗。
1.20
坐了一天的高铁到jz了，热的一批
1.21
上午开营仪式
下午day1
打开发现有个地主斗
然后开T1
出题人你™搞笑吧放一道sb都能切的题
然后开T2
发现非常的可做就写了（题解在后面）
然后写了3h+的T3
成功爆0
sb出题人
告辞
1.22
上午考数学
然后炸了咕咕咕
下午day2
先看完题感觉全都不会qwq
然后把T1的48分大暴力写了
又把T2的21分大暴力写了
然后分析了一波T2发现可以写67分
就rush了一波(O(m^2))成功被卡常
69分GG
题目大意+题解：
d1t1
题意：
一个有向图，每一条边可能存在也可能不存在，求拓扑序列数量的期望乘(2^m)。
没有重边自环，(nleq 20)
显然状压dp
d1t2
题意：
定义虚树(T(S))表示一些点的集合，(x)存在于(T(S))中当且仅当(xin S)或者在树上删除(x)后(S)集合存在两个点不连通
树上每个点都有一个颜色(a_i)，(A_i)是满足(a_x=i)的(x)的集合，对每个(k(kin[1, m]))求一个序列(x_1,x_2,cdots,x_k)满足(x_1<cdots<x_k)而且存在一个(y)满足对于所有的(i)都有(yin T(A_{x_i}))
(1leq mleq nleq 10^5)
显然这个存在(y)的限制就是这些虚树有交，题目定义的虚树显然也是联通块，所以交也是联通块，枚举这个联通块最上面的点(x)
现在的限制是(x)是这个联通块最上面的点，先算出(x)是(a)个虚树最上面的点，剩下的有(b)个虚树经过(x)
那么显然只要选到了一个(a)中的虚树，就能满足(x)是这个联通块最上面的点，否则不能满足
所以计算答案，(ans_i+=C_{a+b}^{i}-C_{b}^{i})
显然就是所有方案数减掉重复的部分
把所有点的(a)和(b)都求出来，最后的答案就是
(ans_i=sum_{j=1}^nC_{a_j+b_j}^{i}-sum_{j=1}^nC_{b_j}^{i})
(ans_icdot i!=sum_{j=1}^nfrac{(a_j+b_j)!}{(a_j+b_j-i)!}-sum_{j=1}^nfrac{b_j!}{(b_j-i)!})
突然发现更博的时候误删了题解一小部分？
记录每一个数的贡献，每一个(a_j+b_j)的贡献为1，(b_j)的贡献为-1，数(i)的贡献记为(c_i)
最后结果是
(ans_icdot i!=sum_{j=1}^nfrac{c_jcdot j}{(j-i)!})
记(A(i)=c_icdot i,B(i)=frac{1}{i!})
(ans_icdot i!=sum_{j=1}^nA(j)B(j-i))
显然ntt一波即可
d1t3
题意：
两个地主打牌，每个地主有20张牌
定义两副牌不相等为，任意出一手牌，两副牌有一副能接上，有一副不能接上。否则这两副牌相等
规定两个地主的牌必须包含一些牌，剩下的可以任意选（但是必须可以从一副扑克中选出），问方案数
题解：
你觉得我会？
d2t1
题意：
求满足以下条件的序列(x_1,x_2,cdots,x_n)数量：
- (x_i)是非负整数，而且(x_i mathbb{and} a_i=a_i)
- (x_iin [l_i,r_i])
其中(a,l,r)是给定的。
(nleq 100,l_i,r_i,a_i< 2^{60})
题解：
屎猫用(O(60 imes n^4))过了此题（呲牙）然后屎猫口胡了一番
先离散化，然后设(f[i][l][r])表示([l,r])区间里从大到小选到第(i)位的方案数
枚举中间点，因为要满足递增，所以中间点向左这一位都是0，向右这一位都是1
然后就分开了这两个区间（这只是口胡）
d2t2
题意：
有一张有向图，建一个新图，对这个有向图的每个环（环要满足没有重复的点）在新图中建一个点，如果两个环有公共边就在新图中给这两个环对应的点连一条无向边。问新图的联通块数。
题解：
答案为所有SCC的基图的点双数量和。
证明？没有
d2t3
题意：
有一堆点(a_i)，每次选一个新点(O)，对原来的每个点(a_i)做一个圆，半径为(a_i)到(O)的距离
问最多可以删掉多少个圆满足删圆后圆的面积并不变
题解：
不会