1031总结

T1

考虑概率=合法方案数/所有方案数
所有方案数\(n^n\)
合法方案数:\(f_n = f_{n-1} + (n-1) f_{n-2}\)
打表就可以发现这个规律
然后就没了

T2

考虑分治,每次预处理mid向左向右的背包
然后每次处理跨中点的询问
\(O((NM+Q)\log N+QM)\)

T3

满分做法:
考虑错位排列的方案数定义
\[ \text{subfactorial}_n = n! \sum _{k=0}^n \frac{(-1)^k}{k!}\]
概率就是除掉n!
显然\(\displaystyle \sum _{k=0}^n \frac{(-1)^k}{k!} \) 收敛于 \( \dfrac{1}{e}\)
树链剖分维护(大到一定值(大概25左右)就不用修改了),均摊线段树

0

1101总结

T1

共有\( n \)种竞赛,对于其中任意\( i \)种竞赛,\(1≤i≤n\),有\(a_i\)个人同时参加,问有多
少个人参加了至少一门竞赛?

傻逼容斥。系数即为组合数。加个大模数。没了

T2

有一棵\( n \)个点的树,每个叶子节点上都有一个人,他们按照每秒钟走一条边的
速度向树根(节点\( 1\))前进。
你可以运用\( k \)次瞬移,让某一个节点(除了根节点)上的所有人瞬间(耗时为\( 0\))
转移到这个节点的父亲上。
你想知道最少需要多少时间,所有人可以到达根节点。

\( k \leq 5 \times 10^5\)
贪心,搞个优先队列

T3

有一个\( n \)面的骰子,第\( i \)面的数是\( v_i\),朝上的概率是\( p_i\)。
不停地抛这个骰子,直到某一面朝上了两次,就停止抛骰子,求所有朝上的面
的数字的和的期望\( E \)是多少. \( n \leq 500\)

想了一个\(n^2\)做法
看pdf

0

玄学排序

Problem

有一种排序叫做玄学排序,大概是这样的,每次随机选两个数进行交换,直到原数组有序

玄学排序的交换次数被定义为交换过程的执行次数(也就是随机两个数算一次交换)。

小 S 开始专注于研究长度为\( n \)的排列,他想知道,在你运气足够好的情况下(即每次冒泡排序的交换次数都是可能的最少交换次数,仿佛有上帝之手在操控),对于一个等概率随机的长度为\(n \)的排列,进行这样的玄学排序的期望交换次数是多少?\( n ≤ 10^7, T \leq 10^5, mod = 998244353 \)

继续阅读 玄学排序

0

计蒜客 – 手拉手【调和级数】

Problem

小 P 是个幼儿园老师。有一天,他组织 \(n \)个小朋友玩游戏。游戏开始时,每个小朋友伸出两只手,没有手相互拉在一起。
每次,小 P 等概率随机挑选两只空着的手,让这两只手拉在一起。小 P 一直重复这个操作,直到所有的手都拉在一起。
小 P 在成为幼儿园老师之前是个数学专业的博士。因此,他想知道,当所有的手都拉在一起之后,
小朋友们拉成的圈个数的期望是多少?其中,我们规定,一个小朋友左手拉右手的情况也形成一个圈。

由于小 P 忙着和小朋友们玩游戏,他找到了聪明的你,希望你能帮他解决这个问题。

对于 100% 的数据:\(1≤n≤10^{18}\)

Solution

考虑期望的线性性,我们发现只有第i个小朋友自己牵自己的手才会产生新的环,这样的概率是\( \dfrac{1}{2i-1}\)
于是答案为\( \sum_{i=1}^n \dfrac{1}{2i-1}\)
暴力有70pts的吼成绩
考虑调和级数,求其中的奇数项就用总的减去偶数项,而偶数项就是总的一半/2
当然如果你会多伽马函数求值的话你也可以直接用公式\(\displaystyle \frac{1}{2} \left(\psi ^{(0)}\left(n+\frac{1}{2}\right)+\gamma + \log 4 \right)\)
于是就\(O(1)\)了
代码不写了

0

NOIP2014模拟10.22 – 搞笑的代码 【调和级数】

Problem

在OI界存在着一位传奇选手——QQ,他总是以风格迥异的搞笑代码受世人围观
某次某道题目的输入是一个排列,他使用了以下伪代码来生成数据


聪明的同学一定发现了,这样生成数据是很慢的,那么请你告诉QQ,生成一个n排列的期望随机次数

Solution

定义\(f_i\) 表示序列长度为\( i \)时的期望随机次数,不难根据题目的定义列出递推式,
\[ f_i = \frac{i}{n} (f_i+1) + \frac{n-i}{n} (f_{i-1} + 1) \]
化简可得
\[ f_i = f_{i-1} + \frac{n}{n-i}\]
于是答案就是
\[ \sum_{i=1}^{n}\frac{n}{i} = n \sum_{i=1}^{n}\frac{1}{i} \]
出现了人尽皆知的调和级数求和。我们考虑这里要乘上一个\( n\),\(n\)较小的时候精度要求较高,可以直接递推,\(n\)较大的时候用近似公式\(H_n \sim \ln(n)+\gamma\)即可
没有代码,懒得写

0

[JZOJ4756]幻象

Problem

这题挺短的就不概括题意了…

phantom是一位爱思考的哲♂学家。
最近phantom得到了森の妖精的真传。在他练功的时候, 每秒他的思绪中都有一定的概率浮现出奇♂异的幻象,持续\(x\)秒的幻象将产生\(x^2\) 的幻象值。
phantom练功发自真心,他想知道,在\(N\)秒内他期望产生的幻象值是多少。

继续阅读 [JZOJ4756]幻象

0