我我我我更完了 QAQ
链上二次求和
有一条长度为 $n$的链（$1\leq i<n$，点 $i$与点 $i+1$之间有一条边的无向图），每个点有一个整数权值，第 $i$个点的权值是 $a_i$。现在有 $m$个操作，每个操作如下：
操作 $1$（修改）：给定链上两个节点 $u,v$和一个整数 $d$，表示将链上 $u$到 $v$唯一的简单路径上每个点权值都加上 $d$。
操作 $2$（询问）：给定两个正整数 $L,r$，表示求链上所有节点个数大于等于 $L$且小于等于 $r$的简单路径节点权值和之和。
由于答案很大，只用输出对质数 $1000000007$取模的结果即可。
一条节点个数为 $k$的简单路径节点权值和为这条上所有 $k$个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。
由于是无向图，路径也是无向的，即点 $1$到点 $2$的路径与点 $2$到点 $1$的路径是同一条，不要重复计算。
题目不是把题解告诉你了吗……
$S_k$表示 $k$阶前缀和，则：
\begin{eqnarray}
Ans &= &\sum_{i=L}^R \sum_{j = i} ^ N S_1[j] – S_1[j – i]\\
&= &\sum_{i=L}^R (\sum_{j=i}^N S_1[j] – \sum_{j=0}^{N-i} S_1[j])\\
&= &\sum_{i=L}^R (S_2[N] – S_2[i-1] – S_2[N – i])\\
&= &(R + L – 1) * S_2[N] – \sum_{i=L-1}^{R-1}S_2[i] – \sum_{i=N-R}^{N-L} S_2[N-i]
\end{eqnarray}
考虑修改：
对于 $L \leq i \leq R$，$add = \frac{(i-L+1)*(i-L+2)}{2} * v$；
对于 $R < i \leq N$，$add = \frac{(R-L+1) * (R-L+2)}{2} * v + (i-R)*(R-L+1) * v$
明明就不卡常～＼（≧▽≦）／～成功 rank7
治疗之雨
你现在有 $m+1$个数：第一个为 $p$，最小值为 $0$，最大值为 $n$；剩下 $m$个都是无穷，没有最小值或最大值。
你可以进行任意多轮操作，每轮操作如下：
在不为最大值的数中等概率随机选择一个（如果没有则不操作），把它加一；
进行 $k$次这个步骤：在不为最小值的数中等概率随机选择一个（如果没有则不操作），把它减一。
现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。
首先要看仔细题目。
用 $f[i]$表示 $k$次攻击中恰好 $i$次击中英雄的概率，$f[i] = C_k^i * (\frac{1}{m+1})^i * (\frac{m}{m+1})^{k-i}$。
$a[i][j]$表示一次从 $i$滴血掉到 $j$滴血的概率，则
\begin{eqnarray}
a[i][j] =
\begin{cases}
\frac{m}{m+1} * f[i – j] + \frac{1}{m+1} * f[i + 1 – j] &\mbox{j <= i}\\
\\
\frac{1}{m+1} * f[0] &\mbox{j == i + 1}
\end{cases}
\end{eqnarray}
然后 $x[i]$表示 $i$滴血时的期望，则:
\begin{eqnarray}
x[0] &= &0\\
x[1] &= &a[1][1] * x[1] + a[1][2] * x[2] + 1\\
x[2] &= &a[2][1] * x[1] + a[2][2] * x[2] + a[2][3] * x[3] + 1\\
x[3] &= &a[3][1] * x[1] + a[3][2] * x[2] + a[3][3] * x[3] + a[3][4] * x[4] + 1\\
&\vdots \\
x[n] &= &a[n][1] * x[1] + a[n][2] * x[2] + a[n][3] * x[3] + \cdots + a[n][n] * x[n] + 1\\
\end{eqnarray}
可以看出这是一个 $n$元的方程，并且 $a$自动构成了一个下三角，所以可以 $n^2$解出来。注意由于 $n$不能变成 $n+1$，所以 $a[n]$要特别计算。即 $a[n][i] = f[n – i]$。
为什么又是 rank7(╯‵□′)╯︵┻━┻
求和
$master$对树上的求和非常感兴趣。他生成了一棵有根树，并且希望多次询问这棵树上一段路径上所有节点深度的 $k$次方和，而且每次的 $k$可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了 $pupil$，但 $pupil$并不会这么复杂的操作，你能帮他解决吗？
大概是只有 $HNOI2018D2T3$能与之相提并论。
路径是 $1\sim 2$条链构成的，一条链上的深度是单调的，而且 $1\leq K \leq 50$，所以我们维护一下 $1\sim 50$次方的前缀和就好了。
成功 Rank21 而且 register 居然还慢了 (MMP.jpg)
二进制
$pupil$发现对于一个十进制数，无论怎么将其的数字重新排列，均不影响其是不是 $3$的倍数。他想研究对于二进制，是否也有类似的性质。于是他生成了一个长为 $n$的二进制串，希望你对于这个二进制串的一个子区间，能求出其有多少位置不同的连续子串，满足在重新排列后（可包含前导 $0$) 是一个 $3$的倍数。两个位置不同的子区间指开始位置不同或结束位置不同。由于他想尝试尽量多的情况，他有时会修改串中的一个位置，并且会进行多次询问。
经历了看错题 $\rightarrow Naive \rightarrow$看对题 $\rightarrow Naive \rightarrow$终于不 $Naive$但还是很 $Simple$的曲折过程。
首先需要自己推出一个傻逼的结论。然后维护非法的子区间个数，用总数减去它。一共只有两种是违法的：
1. 只出现了一次 $1$。
2, 出现了奇数个 $1$并且 $0$的出现数量少于 $2$。
然后就是冗长的 $update$了。
染色
$pupil$喜欢给图的顶点染颜色。有一天，$master$想刁难他，于是给了他一个无重边和自环的无向图，并且对每个点分别给了一个大小为 2 的颜色集合，$pupil$只能从这个集合中选一种颜色给这个点染色。$master$希望 $pupil$的染色方案使得没有两个有边相连的点被染了相同的颜色。现在 $pupil$想知道，是否无论 $master$的颜色集合是什么，他均有办法按照要求染色。
结论细节题。
首先奇环不行；度数为 $1$的节点可以直接忽略；偶环只有一个交点不行；偶环中出现了度数 $> 3$的不行；偶环的交中度数为 $3$的两个点的三条路径需要为 $2-2-$偶数。
详细的看代码….
0 条评论