善变 - 王靖雯
身后公园 是第一次遇见
转角花店 见证牵手两年
这城市散落着太多纪念
总是在我们之间兜圈
如果我是 你眼里的景点
路过就好 何必留下想念
何必让故事用微笑开篇
结局眼泪悼念
只怪有你的从前
美的太过惊艳
才会当热情变浅 决裂明显
爱是谁也绕不开的抛物线
从前你穿越风雨 都会仓促见一面
后来连伞的边缘 你都懒得分一点
是我们低估了时间的善变
太轻易让浓烈的故事翻篇
从前你穿过半座城市 陪我一起失眠
后来你好像跟你的方向盘 更近一点
只是当泪水又滑落在照片
却舍不得删
只怪有你的从前
美的太过惊艳
才会当热情变浅 决裂明显
爱是谁也绕不开的抛物线
从前你穿越风雨 都会仓促见一面
后来连伞的边缘 你都懒得分一点
是我们低估了时间的善变
太轻易让浓烈的故事翻篇
从前你穿过半座城市 陪我一起失眠
后来你好像跟你的方向盘 更近一点
只是当泪水又滑落在照片
却舍不得删
从前你穿过半座城市 陪我一起失眠
后来你好像跟你的方向盘 更近一点
只是当泪水又滑落在照片
却舍不得删
好歹让这一幕幕从前
不只像谎言
[ARC150D] Removing Gacha
这个题好牛逼啊。
答案显然是把每个点的期望次数加起来。那么久转化成了怎么求每一个点的答案。
对于一个点，能影响到这个点被选的概率的一定是从根节点到这个节点之间的所有节点的状态。这样又把问题转化到一条链上了。
设这个点的深度是 \(dep\)，这条链上已经选的有 \(k\) 个点，那么选这条链上没有选过的点的概率就是 \(\dfrac{dep-k}{dep}\)，期望 \(\dfrac{dep}{dep-k}\) 步选到下一个没有选过的点。那么把所有的点选上的期望就是 \(\sum\limits_{k=0}^{dep-1}\dfrac{dep}{dep-k}=dep\times\sum\limits_{k=1}^{dep}\dfrac{1}{k}\)，相对于链上每一个点来说就是 \(\sum\limits_{k=1}^{dep}\dfrac{1}{k}\)，也就是关于深度的调和级数的前缀和，把所有的点的这些玩意加上就行了。
CF213E - Two Permutations
首先数据范围是 \(2\mathrm{e}5\)，支持枚举，问题留给了判断子序列。不简单想到了哈希，一开始想到的是树状数组，发现树状数组比较菜，就转向了线段树。
一开始先把 \(b\) 中的 \(1\sim n\) 加到线段树里，然后不断的删除最小的，加入最大的，这个过程只需要单点修改，不需要建树，也不需要 pushdown，线段树的每个节点维护出现的有效数字个数和这个区间的哈希值即可。
对于枚举的 \(a\) 的哈希值，还需要维护一个 \(base\) 的前缀和。每次统计答案直接判断 \(a\) 的哈希值和线段树维护的哈希值是否相等即可。
\(base\) 取个质数就行，模数要注意一下。
P1409 骰子
这题的式子挺好推的，就差直接给你写出来了。
数据范围支持 \(O(n^2)\)，然后就可以设 \(dp_{i,j}\) 表示还剩 \(i\) 个人，你排在第 \(j\) 位，你赢的概率。显然有边界 \(dp_{1,1}=1\)。
然后有转移方程：
\[\begin{cases} dp_{i,j}=\dfrac{1}{2}\times dp_{i,j-1}+\dfrac{1}{3}\times dp_{i-1,j-1} & (j>1) \\\\ dp_{i,j}=\dfrac{1}{2}\times dp_{i,n}+\dfrac{1}{6} & (j=1). \end{cases} \]但是发现转移是环形的，但是每个方程只有两个未知数，然后就可以代入消元即可。
Grid 2
设 \(dp_i\) 表示前 \(i\) 个点路径方案数，不考虑重复的点，从 \((1,1)\) 到 \((x,y)\) 是可以用组合数算出来的，然后考虑重复的点怎么处理。我们先把点按照横纵坐标排好序，设两个点 \(i\) 和 \(j\)，如果 \(x_i<x_j\land y_i<y_j\)，我们可以算出既经过 \(i\) 又经过 \(j\) 的然后用总的减去这部分就可以了。我们可以。
\[dp_i=\sum\limits_{j=1}^{i-1}dp_j\times\dbinom{x_i-x_j+y_i-y_j}{x_i-x_j}\times[x_j<x_i][y_j<y_i]. \]总之这样就完事了。
标签：从前,dep,dfrac,times,哈希,狗屁不通,dp From： https://www.cnblogs.com/voah/p/17825477.html