##Problem A - DZY Loves Balls 考虑期望的可加性。第$i(1\leq i < n+m)$个位置上出现0，第$i+1$个位置上出现1的概率是$\frac{m}{n+m} \times \frac{n}{n+m-1}$，那么答案自然就是$\sum_{i=1}^{n+m-1}\frac{m}{n+m} \times \frac{n}{n+m-1}=\frac{nm}{n+m}$ 如果你不能马上想到上述的简便的方法，也可以选择暴力枚举所有01串，也是可以AC的。最后一步你需要再计算一下gcd，十分简便。 ##Problem B - DZY Loves Topological Sorting 因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点$i$的入度为$d_i$。假设当前还能删去$k$条边，那么我们一定会把当前还没入队的$d_i\leq k$的最大的$i$找出来，把它的$d_i$条入边都删掉，然后加入拓扑序列。可以证明，这一定是最优的。 具体实现可以用线段树维护每个位置的$d_i$，在线段树上二分可以找到当前还没入队的$d_i\leq k$的最大的$i$。于是时间复杂度就是$\text{O}((n+m) \log n)$. ##Problem C - DZY Loves Inversions 考虑如何计算一个区间中有多少个子区间的逆序对数小于等于$K$。这样做两遍就能算出恰好等于$K$的了。 对于$i(1\leq i \leq n)$，我们计算$r_i$表示$[i,r_i]$的逆序对数小于等于$K$，且$r_i$的值最大。显然$r_i$单调不降，我们可以通过用两个指针扫一遍，利用树状数组计算出$r$数组。 对于每个询问$L,R$，我们要计算的是$\sum_{i=L}^{R}[ \min(R, r_i)-i+1 ]$ 由于$r_i$具有单调性，那我们直接在上面二分即可，然后记一个前缀和。总复杂度是$\text{O}((n+q) \log n)$。离线的话的还可以做到$\text{O}(n \log n + q)$，都是非常优秀的。 UPD: 比赛中过了pretest的同学很遗憾都在$k=0$的时候挂了，导致似乎没有人过Final Test。其实只要稍微注意一下这个边界情况，就可以避免FST了。 ##Problem D - DZY Loves Orzing 因为每个人的身高都是不同的，所以我们可以每列分开来考虑。于是，问题变成了，求多少个长度为$n$的排列，满足从前往后看能看见$k$个人，令这个答案为$f(n,k)$。 最后的答案当然是 $\frac{n^2!}{(n!)^n}\prod_{i=1}^{n}f(n,a_i)$ 考虑如何递推，假设我们现在从$n-1$推到$n$。考虑枚举第$n$个数是几。 如果我们放$n$，那么因为他是当前最高的，放在前面会挡住其他任何人，所以我们把它放在最后，从$f(n-1,k-1)$转移过来。 如果我们放$i(1\leq i< n)$，那么我们先在$n-1$个数中找到$i$的位置，插入到它后面，然后把除了新加的大于等于$i$的数都加一，这样还是只能看见$k$个人。于是有$n-1$种情况从$f(n-1,k)$转移而来。 于是我们得到了$f(n,k)=f(n-1,k) \times (n - 1) + f(n-1,k-1)$。 其实这就是第一类Stirling数的递推式，更进一步地，我们有$f(n,k)=|s(n,k)|$。 关注到 $x^{n}=x(x-1)(x-2)\cdots(x-n+1)=\sum_{k=1}^n s(n,k)x^k$ 我们可以使用分治FFT计算这个多项式的系数。每次递归到两边求出多项式后，再用FFT算出他们乘起来的结果。由$T(n)=2T(n/2)+O(n \log n)$得复杂度是$O(n\log^2 n)$。 由$s(n,k)=(-1)^{n+k}|s(n,k)|$，我们可以得到$f(n,k)$。 然后关注答案前面那个系数，如何计算$(n^2)!$模$p$的值呢。注意到$n^2\geq p$时，答案一定是0！所以，$n>\sqrt{p}$我们直接输出0就好了！可是$p$也是$10^9$级别的，怎么快速求阶乘呢？我们可以使用简单粗暴的分块打表！每隔$10^6$存一个阶乘的值，这样每次计算的时候只要找到预处理的值，然后最多做$10^6$次乘法就好了。表里也就1000左右个数，代码长度轻松控制在20K以内。 综上，我们的复杂度就是$O(n\log ^2 n)$，而且$n\leq \sqrt{p}$，毫无压力AC。 UPD：本来KirinoP是过了Pretest的，而且方法都和题解里的每一步都一样。只可惜他数组只开了32768，读进100000个数的时候就RE了，很遗憾没能AC。

##1001 Go to movie 直接枚举去哪个电影院，从中取花费最少的，$ans=min(\frac{n+a_i-1}{a_i}*b_i)$ ##1002 Building Blocks 枚举最终的W堆积木在哪，确定了区间，那么就需要把高于H的拿走，低于H的补上，高处的积木放到矮的上面，这样最优。因此把这个区间变成W*H的代价就是$max(\sum (H_i-H),\sum (H-H_j))(H_i > H,H_j \le H)$即在把高的变矮和把矮的变高需要的移动的积木数 取较大的。从第一个区间[1,W]到第二区间[2,W+1]只是改变了2堆积木，可以直接对这两堆积木进行删除和添加来维护$\sum (H_i-H)$和$\sum (H-H_j)$。 需要注意的是，最终选取的W堆积木中，有可能有几堆原本不存在。如 9 8 7 形成3*3，可把3堆积木变成5堆 3 3 3 8 7，最少移动6个积木。因此需要在n堆积木两端补上W个0。整个问题的复杂度是$O(n+W)$. ##1003 Building Blocks Ⅱ 跟1002一样，枚举所有的区间。对于确定的区间，假设最终的高度为h， 代价是$max(\sum (H_i-h),\sum (h-H_j))(H_i > h,H_j \le h)$ 等价于$max(\sum H_i-cnt(i)*h,cnt(j)*h-\sum H_j)$ ($cnt(i)$表示满足$H_i > h$的堆数, $cnt(j)$表示满足$H_j \le h$ 的堆数)。$\sum H_i-cnt(i)*h$关于h呈递减，$cnt(j)*h-\sum H_j$关于h呈递增。一个递减到0，一个从0开始递增，所以代价与h的函数图像是V字形的，交点处代价最小。此时 $\sum H_i-cnt(i)*h = cnt(j)*h-\sum H_j, h=\frac{\sum H_i + \sum H_j}{cnt(i)+cnt(j)}$，分母是总堆数W，分子是这个区间积木的总个数。h实际上就是这个区间的平均高度aver。考虑到四舍五入，答案是aver或者aver+1，当然还需要与题目给定的H做下比较，最终的方案是这3个数之一。确定高度之后，把高的变矮需要知道比当前高度大的个数以及高度总和，把矮的变高类似。因此添加一堆和删除一堆时，需要维护个数和总和。可以通过树状数组维护，整个问题的复杂度$O((n+W)\log n)$. ##1004 Go to movieⅡ 添加或者删除一个元素时，维护逆序对时，需要知道在它之前有多少个数比它大，在它之后有多少个数比他小。有下标和权值两个维度，可以使用两个数据结构嵌套。题目中n=20000，范围不大，外层可以使用分块维护下标，这样添加和删除元素的时候，也很方便，直接暴力。查找权值个数时，使用树状数组比较方便。内层通过树状数组维护权值。设每块的大小为S，那么删除或者添加元素时，维护逆序对数的复杂度是$O(S+\frac{P}{S}* \log n)$，S是块内直接暴力更新逆序对的代价，$\frac{n}{S}* \log n$在前面块找比它大和在后面块中找比它小的代价,P表示当前元素的个数。为了使这两部分复杂度尽量均摊让$S=\frac{P}{S}* \log n$，S取$\sqrt{P\log n}$。直接通过分块暴力添加和删除时，块的大小会退化，需要重构，下次重构的时间T取S。重构一次的复杂度是$P\log n$, 总的重构复杂度是$\frac{m}{S}*P\log n=m\sqrt{P\log n}$,与添加和删除总的复杂度一至。因此整个问题的复杂度为$O(m\sqrt{n\log n})$.

## 1001 zhx's submissions 送分题。唯一的意义在于比手速。首先读进来的时候把字母和数字都转换成0到35的数字，加起来直接取模，算出答案。 坑点是只有1个数的情况，还有答案等于0的时候也要输出一行一个0。 hint: 这道题本来想出b进制高精度加法的，然后某君告诉我java里的BigInteger可自定义进制。汗 ##1002 zhx and contest 如果$n=1$，答案是$1$，否则答案是$2^n-2$。 证明：$a_i$肯定是最小的或者最大的。考虑另外的数，如果它们的位置定了的话，那么整个序列是唯一的。 那么$a_i$是最小或者最大分别有$2^{n-1}$种情况，而整个序列单调增或者单调减的情况被算了2次，所以要减2。 要注意的一点是因为$p>2^{31}$，所以要用快速乘法。用法与快速幂相同。如果直接乘会超过long long范围，从而wa掉。 ##1003 zhx and contest 一个简单的想法是状态压缩dp。但是$30$的数据范围存不下来。 首先发现如果选定了做哪些题的话，按题的$l$值递增的顺序做一定不会更劣。 然后我们把所有题按$l-t$排序，分成大小相同（或者相差$1$）的两部分。对于前一部分，枚举出所有可能的取法的得分和结束时间。然后把它们按照得分排序。可以算出得分不少于某个值的时候完成时间最早是多少。 然后对于后一部分也是相同的枚举，然后在得分符合条件的里面找完成时间最早的，用和上面相同的办法就可以处理出答案。 ##1004 zhx's tree 我们会发现分式没有办法分离。于是把式子变形。设答案为$ans$，那么有 $\frac{wb*hb+wg*hg}{wb+wg} \geq ans$ 这个式子可以用来二分答案。化简这个式子得到 $wb*hb+wg*hg \geq ans*wb+ans*wg$ $-ans*wb+wb*hb-ans*wg+wg*hg \geq 0$ 如果把$ans$视为$x$的话，那么题目就变成了求当$x$等于某个值时，求一堆直线里最大的$y$值。那就是在一个凸壳上二分。 另外考虑到询问是在树上，那么使用树链剖分+线段树来解决这个问题就好了。线段树的每一个结点存一个凸壳。空间复杂度是$O(n*logn)$，时间复杂度是$O(m*log^{3}n)$。 另：特别感谢帮我检查数据的某不愿透露姓名的队友，以及负责bestcoder验题的各位学长。

[title]1001 PM2.5[/title] 对于输入的每一行一两个整数作差，按照差值从大到小排序，如果差值一样，按照后面的整数从小到大排序，如果还是一样按照ID从小到大排序。 [title]1002 Positive and Negative[/title] 维护前缀和sum[i]=a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i] 枚举结尾i，然后在hash表中查询是否存在sum[i]-K的值。 如果当前i为奇数，则将sum[i]插入到hash表中。 上面考虑的是从i为偶数为开头的情况。 然后再考虑以奇数开头的情况，按照上述方法再做一次即可。 不同的是这次要维护的前缀和是sum[i]=-（a[0]-a[1]+a[2]-a[3]+…+(-1)^i*a[i]） I为偶数的时候将sum[i]插入到hash表。 总复杂度o(n) [title]1003 Brackets[/title] 当n为奇数的时候答案是0。 先判断字符串的前面是否符合括号匹配，即对于任何前缀左括号个数>=右括号个数。 设左括号个数为a右括号个数为b, m=n/2，问题可以转化为在平面中从座标(a,b)沿网格走到(m,m) 且不跨过x=y这一条直线的方法数。数据太大，普通DP和搜索都不行的。 问题可以进一步转化为从(a-n,b-n)到(0,0)且不跨过x=y的方法数。再对称一下，转化到(0,0)到(n-b,n-a)不跨过x=y的方法数。 对于从(0,0)点走到(p,q)点不跨过x=y的方法数是\[\frac{{p - q + 1}}{{p + 1}}C_{p + q}^q\] 证明如下： 我们可以通过总的数目来减掉非法的数目即可。 把(0,0)和(p,q)都往下移一格，非法数目即为(0,-1)到(p,q-1)且路径中至少有一点和x=y相交的方法数。记(d,d)为从(0,-1)到(p,q-1)路径中最先和x=y相交的点。则由于对称性(-1,0)到(d,d)的方法数和(0,-1)到(d,d)的方法数是相同的。所以(0,-1)到(p,q-1)且与x=y相交的方法数和(-1,0)到(p,q-1)的方法数是相同的。 所以答案是\[C_{p + q}^q - C_{p + q}^{q - 1} = \frac{{p - q + 1}}{{p + 1}}C_{p + q}^q\] 然后对100W以内的数字进行一个阶乘处理，就可以O(1)得出答案了。 [title]1004 Equation[/title] 这可以看成是一个完全背包问题，但是由于数字比较多直接DP会超时。其实可以发现数字的种类最多是sqrt(n)级别的。那么就可以把复杂度降到nsqrt(n)； Dp[i][j]代表前i个数字放好之后能组成j的和数是多少。 递推方程是Dp[i][j]=dp[i][j-i]+dp[i-1][j-i]; 表示第i种数字放的时候，前面要么放了i，要么放了i-1 边界条件是dp[i][j]=0 for i < j Dp[0][0]=1; 所以最后总的复杂度是n*sqrt(n)

[title]1001:pairs[/title] 我们将所有位置按从小到大排序，题目的本质上是对于每个a，找到在其右边最远的b使得$|x[b]-x[a]| \leq k$，累计b-a的和就行了，由于b有单调性，因此对于每个a增加，将b直接扫过去找到符合上述不等式的最远的b，再累加答案即可，当然也对于所有的a，二分出最远的b，累加答案,记得要开long long。 [title]1002:beautiful number[/title] 这题的正解是暴力出1~1000000000内所有符合情况的解。由于题目的苛刻的条件，符合条件的解实际上是极少数！实测是1299个数。这1299个数我们可以离线暴力1~1e9内的所有数判断是否符合条件，或者在线通过DFS搞出来。然后我们对于每个询问L,R，枚举1299个数看有多少数存在，当然也可以二分，复杂度变为$lg(1299)T$。 UPD：这题可以用数位DP来做，即L~R转化成(1~R)-(1~L-1)，dp[i][j][k]表示到从低到高第i位，该位为j，k是一个二进制的状态，表示是否含有2，3，5，7这4个质因子，转移即从前一位的dp[i-1][l][p]中转移过来，其中l为1~9，p为被包含在k中的一个二进制，复杂度为$9*{9}^{2}*{3}^{4}*T$，大约是590W，可以通过本题。 [title]1003:chess[/title] 我们先通过dp1[i][j][k]求出在i行j列的情况下放置若干国王的方案总数，由于国王之间不能相邻，因此同一行的{2}^{j}的状态数可以变成第j项fib的状态数，因此我们可以在较快的时间内预处理出这个数组。 我们发现一辆车的作用，实际上是将整个棋盘分割开来。 接下来我们再预处理出dp2[i][j][k]，表示i行j列，其中k这个状态的行不能放置国王的方案总数，这里的时/空复杂度为$15*15*{2}^{15}$。 然后我们对于每组询问，枚举哪些行放了车，再枚举哪些列被放了车，再通过dp2数组将这些方案数乘起来累加进答案即可。这里的时间复杂度为{C(15,7)}^{2}。 由于有各种乘法操作，是无法在规定时间内通过本题，考虑到读入的仅有两个数，可以打表。 注意到枚举哪些行放了车后实际上是可以dp的，令dp3[i][j]表示到第i列，当前已经有j列放了车，且第i列必然放了车，转移显然，这样复杂度是$C(15,7)*{n}^{2}*k$，可以通过本题。 [title]1004:numbers[/title] 我们令dp[i][j]表示只考虑i~j的数进栈，我们不考虑m个限制，那么令k为i~j中最后出栈的,则i~k-1肯定比k+1~j先出栈，根据乘法定理与加法定理，$dp[i][j]=\sum dp[i][k-1]*dp[k+1][j]$，初始条件为对于任意i,dp[i][i-1]=1,我们再考虑对于每个限制ai,bi,当ai<bi时，ai不能作为最后一个出栈的，即k不等于ai，当ai>bi时，bi+1~ai不能作为最后一个出栈的，即k不能等于bi+1~ai中的任何一个，（这里注意，只针对ai>=i,ai<=j,bi>=i,bi<=j这样的限制），最后dp[1][n]即为答案。 接下来我们考虑对于对于每个i和j，k能否取到，一个暴力的思路是枚举所有m，判断是否能取到，这样复杂度变为$O({n}^{3}*m)$，注意到如果限制存在一个环，方案总数显然为0，若存在形如A->B,B->C,A->C,（在这里,X->Y指X比Y先出栈），那么A->C显然是冗余的，我们可以从最远的DAG向最近的DAG做一次递推，若存在上述这样的情况，舍去A->C这条边(然而实际上若是一个二分图，左边n/2个点，右边n/2个点，这种优化起不到实质性的变化，只是优化常数而已)。 我们换一个思路，考虑预处理的数组V[i][j][k]表示dp[i][j]中k能否，对于每一个限制ai,bi，我们枚举i=1~min(ai,bi),j=max(ai,bi)~n,这样若ai>bi 则V[i][j][k](bi<k<=ai)表示为不能取，若ai<bi，则V[i][j][ai]表示为不能取，这样我们通过枚举I,j,k,仍然是$O({n}^{3}*m)$，注意到k一定是连续的，我们可以用并查集维护，复杂度降为$O({n}^{2}*m*α)$，其中α是一个很小的常数。我们再观察它的性质，i与j本质上是构成了n*n这个矩阵中的其中一块，我们只需记录4个端点，再枚举k，最后判断前缀和（即包括该点的左上方的矩阵）是否为0，就可以知道dp[i][j]能否从k转移到了，时间复杂度为$O({n}^{3}+nm)$