【题解】牛客国庆集训派对Day5
1.璀璨光华
首先固定一号点标 0，那么与一号点相邻的标 2^i，对于一个标号x，如果已经确定了 x-2^a,x-2^b，那么这个点可以被唯一确定。
接下来就相当与这些位可以随便调换，每个位关于这 2^n 个数字是个 01序列，然后排个序即可。
2.电音之王
黑科技 wiki Montgomery modular multiplication/ 现在在 32 位机上跑不过暴力，所以用 long double 试除就能过。
3.萌新拆塔
状压 dp+简单计算。注意有模仿怪所以不要无脑吃宝石即可。
4.奇迹暖婊
对偶费用流，努力卡了很久之比 LP 快了一点点，只好卡内存了。
5.风花雪月
任意不满足的状态对答案的贡献为 1，所以只需要求出每个不够的状态的概率最后加上 1。
我们认为我们总共需要 4*sum c 件衣服，每次抽如果没到达 c，那么贡献为 4，否则贡献为 1。
dp[i][j][k]表示前 i件衣服，抽了 j 件，总贡献为 k 的概率和。
6.双倍掉率
max C(n,a) C(m,b) p^a (1-p)^(n-a) (2p)^b (1-2p)^(m-b) 取对数求导之后解个二次方程或者二分即可。
7.贵族用户
枚举哪一档，然后算一下钱够不够，不够接着氪钱。
8.我不爱她
一个前缀/后缀代价为本身长度-border 长度，hash+kmp 即可。
9.人渣本愿
KM，然后求出每个点删掉之后的最大权匹配，这个只要把顶标和边权改成 0，然后跑一边 KM 中的增光即可，
然后类似一个半平面交的东西，由于范围很小可以枚举每个人跑不等式。
10.友谊巨轮
模拟，用一个 map 记录一下两两之间聊了几句和最近时间，用一个 set 当堆，
然后每次修改的时候就 p_old[x],x,p_new[x]三个点的状态会变。
11.最后战役
c 个人中，相对排名 k，这个人期望是 k(n+1)/(c+1)。
倒着 dp，看选这个人的期望与选后面人的期望，需要一个树状数组统计排名。
12.数论之神
找规律发现一定是 1, 2, 3, ..., x, n/(x-1), n/(x-2), .... x 是 sqrt(n)附近
查看13道真题和解析
