题目大意：给定n个区间\([l_i , r_i]\)，\(-10^6 \leq l_i \leq r_i \leq 10^6\)且\(l_i , r_i\)都为整数，\(x_i\)为对应范围内的一个随机实数，求\(| \sum{x_i} | \)的期望。\( n \leq 15\)，答案对998244353取模。 题解：和这道题基本上是一样的，容斥方法一样。 分成\(\sum{x_i}\)小于0和大于0两部分来考虑，两部分的做法一样。以小于0的部分为例，首先将范围进行调整，将\(x_i\)的范围调整为\([0,r_i – l_i]\)，那么符合条件的范围即\( \sum{l_i} + \sum{x_i} < 0\)，即\( 0 \leq |\sum{x_i}| < |\sum{l_i}| \)，求此时\( |\sum{l_i}| – |\sum{x_i}|\)的期望。容斥的方法和上面的那个是一样的，不同之处在于这题求的不是概率，还要考虑\(\sum{x_i}\)的期望。这里可以通过积分求出，当\[0 \leq x_i \leq a\] \[0 \leq \sum{x_i} \leq a\]时，该部分\(a – \sum{x_i}\)的期望为\(\frac{a^n}{xpro \cdot n!}\)，其中\(xpro = \prod{(r_i – l_i)}\)。（不是很严谨，意会一下即可）
[ SPOJ ] RNG – Random Number Generator
题意：有n个正整数\(1 \leq x_1…x_n \leq 10\)，\(a_i\)为\([-x_i,x_i]\)范围内的一个随机的实数，求\(a \leq \sum a_i \leq b\)的概率。\( (n \leq 10) \) 题解：这题有一个n=2的版本。 首先将a和b都加上\(\sum x_i\)，那么问题中\(a_i\)范围变为\([0,2x_i]\)。和链接中的题目一样，考虑容斥。另外由于统计和在一个区间内难度比较大，所以就考虑和\( \leq b\)的概率减去和\( \leq a\)的概率。 设\(f(x)\)为\(0\leq a_1,a_2,a_3,\cdots,a_n\leq x\)时\(\sum a_i\leq x\)的概率\(*x^n\)。n=1时概率为1，n=2时概率为\(\frac{1}{2}\)，n=3时概率为\(\frac{1}{6}\)，（可以结合图形来看，如n=3时表示的是由(0,0,0),(x,0,0),(0,x,0),(0,0,x)四点构成的三棱锥的体积）由此可以类推\(f(n)=\frac{x^n}{n!}\)。\(x\leq 0\)时\(f(x)=0\)。 先讨论n=2的情形。n=2时答案为\[\frac{f(a)-f(a-2x_1)-f(a-2x_2)+f(a-2x_1-2x_2)}{\prod{2x_i}}\] 即先计算\begin{aligned}0\leq a_1\leq a \\ 0\leq a_2\leq a \\ 0\leq a_1+a_2\leq a \end{aligned}的情况，减去\begin{aligned}2x_1\leq a_1\leq a \\ 0\leq a_2\leq a \\ 2x_1\leq a_1+a_2\leq a \end{aligned}的情况和\begin{aligned}0\leq a_1\leq a \\ 2x_2\leq…
[ TCO2016 Round 2B DIV1 Easy ] TriangleTriples
题意：给出\(a,b,c,1<=a,b,c<=10^9\)，求所有的满足\(1 \leq x \leq a,1 \leq y \leq b,1 \leq z \leq c\)且由\(x,y,z\)为三边长能组成三角形的方案数。（\(a,b,c,x,y,z\)均为整数） 题解：用容斥做这道题目会比较简单。首先设\(a \leq b \leq c\)。考虑容斥，答案即\(abc\)减去所有\(x \geq y+z,y \geq x+z,z \geq x+y\)的方案数。由于\(x \geq y+z,y \geq x+z,z \geq x+y\)是独立的，所以可以分别计算。 考虑\(x \geq y+z\)，由于\(y+z \leq a\),那么显然有\begin{aligned}1 \leq x \leq a \\ 1 \leq y \leq a \\ 1 \leq z \leq a \end{aligned}答案显然为\(\sum_{i=1}^{a-1}{\frac{i(i+1)}{2}}=\frac{a(a+1)(a-1)}{6}=C_{a+1}^{3}\)，后面的组合数可以理解为在\(0…a\)中选出三个点\(x_0,x_1,x_2,0 \leq x_0<x_1<x_2 \leq…
[ HDU6308 ] Time Zone
[ HDU6305 ] RMQ Similar Sequence
题意：定义一个数列A的\(RMQ(A,l,r)\)为使得\(a_i\)为\(a_l,a_{l+1},a_{l+2}, \cdots ,a_r\)中最大数的最小的i。 对于两个数列A与B，定义它们RMQ相似当且仅当两数列元素个数相等且对于所有的\(1 \leq l \leq r \leq n\)，有\( RMQ(A,l,r)=RMQ(b,l,r)\)。 现在给你一个正整数数列\(\{a_i\}\)，其中\(1 \leq a_i \leq n\)，对于实数数列\(\{b_i\}\)，其中\(b_i\)为\([0…1]\)中随机的一个实数，当数列A与B RMQ相似时，B的权值为\(\sum{b_i}\)，否则为0,求B权值的期望。（答案对\(10^9 + 7\)取模）（\(1 \leq n \leq 10^6\)） 题解：首先要观察两个序列RMQ相似的条件。当数列A是一个1..n的全排列时，两个序列RMQ相似当且仅当B中元素的大小顺序和A相同。此时答案为\(\frac{n}{2} \cdot \frac{1}{n!}\)（其中\(\frac{n}{2}\)表示的是B中元素之和的期望，\(\frac{1}{n!}\)表示的是B中元素大小顺序满足条件的概率）。 问题主要是在于当A中含有相同元素的时候的答案。由于不同的A的全排列所对应的满足条件的B是互不相交的（元素间大小关系不同），所以我们要求出与A RMQ相似的n排列的个数，答案就是这个乘上上面所说的一个排列所对应的答案。接下来找符合条件的全排列（记为C）的个数。 考虑A的一个区间\([l..r]\)，设\(m=RMQ(A,l,r)\)，那么我构造的\(c_m\)一定是C中该区间中的最大值，\(c_m\)的值可以确定下来。可以发现，当取任意的\(l \leq l_0…
[ HDU6304 ] Chiaki Sequence Revisited
题意：有一个数列定义如下：\(a_1 = a_2 = 1, a_n = a_{n-a_{n-1}} + a_{n-1-a_{n-2}} (n \geq 3) \)，求\(\sum_{i=1}^n{a_i}\)。（\( 1 \leq n \leq 10^{18}\)，多组数据，\(T \leq 10^5\)） 题解：先打个表观察一下。数列从1开始如下：1 1 2 2 3 4 4 4 5 6 6 7 8 8 8 8 9 10 10 11 12 12 12 13 14 14…
[ HDU6301 ] Distinct Values
[ HDU6300 ] Triangle Partition
[ HDU6299 ] Balanced Sequence
题意：将n个由'(‘和’)’组成的字符串任意串接在一起，求从中能够取出的最长的满足括号匹配的子序列的长度。\(1 \leq n \leq 10^5 , 1 \leq |s_i| \leq 10^5 , \sum{|s_i|} \leq 5 \cdot 10^6\)。 题解：将每个串中最长的满足括号匹配的序列全部取出来，剩下的部分就是形如\(“)))(((“\)这样的形式的，即一些右括号与一些左括号组成。记每个串这样处理出来后右括号数为a（就是左半边的括号数），左括号数为b，每个串都能表示成\( (a,b) \)的形式，接下来就是要对这些串排序使结果最优。 考场上的做法基本上就是取多种排序方式求结果然后取最大值了。标算的排序做法是这样的：把串按照\(a < b\)和\( a \geq b\)分成两类，先取\( a < b\)的，在\( a < b\)这类中a小的先取，在\(a \geq b\)这类中b大的先取，然后扫一遍求出答案。大致证明一下： 考虑交换相邻位置的两个串。考虑位于i和i+1的两个串，其中\( a_i \geq b_i \)且\(…