大年初二。
今天是 ynycoding 讲抽象代数（这篇不是这玩意），感觉难度一下就上来了，不过感觉他每次留的思考时间还是太长了，速度其实比前几天都要慢。
唉，一些留在剪切板里不敢说的话。
补题的时候发现这个trick，貌似挺常见的，遂拿出来讲讲。
先介绍一下这个 trick，暂且叫它计数转概率。也就是把一个计数问题转化为概率问题，然后发现某一些类似的事件不交，且概率相同，是古典概型，于是简化了计算。
一架飞机有 \(n\) 个座位排成一列，有 \(m\) 名乘客依次上飞机。乘客会选择一个目标座位，然后选择从前门或者后门上飞机走到目标座位，如果目标座位已经有人坐了，他们会继续往前走，在走到第一个空位后坐下，没有就不坐。
求有多少种方案使得每个人都坐下了。
我们发现不好描述两边走，也不好描述走不了。考虑增加一个位置 \(n+1\)，连成一个环，这样两边走可以刻画成顺时针/逆时针，而没地方坐就是走到了 \(n+1\)。。那么问题转化为顺时针或者逆时针走，随机一个目标位置降落，走到目标位置之后的第一个空位，\(n+1\) 号点没有被占据的概率。显然最后 \(n+1\) 个位置会被占据 \(m\) 个，如果 \(n+1\) 这个位置也可以降落，那其实这 \(n+1\) 个位置每个位置被占据的概率是一样的。所以 \(n+1\)，没被占据的概率是 \(\frac{n+1-m}{n+1}\)，方案数即为 \(\frac{n+1-m}{n+1}(2(n+1))^{m}\)。
给定 \(n,k(1\le n\le 10^9,1\le k\le 10^5)\) 求长度为 \(n\) 的序列 \(\{a\}\) 的贡献和，对于 \(i\in [1,n],\sum [a_j\ge i]\le n\)。其贡献定义为每种颜色的出现次数的 \(k\) 次幂之和。
\(n(1\le n\le 500)\) 个人，一开始每个人有一个宝石，每个宝石每天有相同的概率分成两半。求 \(d(1\le d\le 500)\) 天后拥有前 \(r\) 大的宝石数量的人的宝石数量和的期望。
试试看！
[THUPC2018]淘米神的树
[ZJOI2019]线段树
标签：le,宝石,23,2023.01,位置,目标,概率,座位 From： https://www.cnblogs.com/zcr-blog/p/17065417.html