感谢验题人Stilwell，wjh720。感谢BC管理员和验题人的耐心帮助。 ## 1001 ZYB loves Score 本题考察了选手的模拟能力，直接按照题目意思计算即可 ## 1002 ZYB loves Xor I 我们考虑，当$A$ $xor$ $B$的答案为$2^p$时，$A$和$B$表示成二进制数后末$p-1$位肯定相同 于是我们维护一颗字母树，将每个数表示成二进制数后翻转可以下，插入字母树 统计答案时，我们找出$A_i$的二进制数翻转后在字母树上的路径，对于路径上每个点$x$，设他走的边是$v$，且当前为第$k$位，则和他$xor$后lowbit为$2^k$的数的个数为trans(x,v^1)的子树大小。 trans(x,v)表示字母树上在结点x，走连出去的字母为v的边到达的结点 时间复杂度：$O(nlogA)$ ## 1003 ZYB loves Xor II 我们考虑两个数$A$，$B$。 为了描述方便，我们设[P]的值为：当表达式P的值为真时，[P]=1，否则[P]=0 我们现在考虑计算$[(A+B)and(2^i)>0]$ 首先我们将A,B都对$2^{i+1}$取模，显然这样是不会影响答案的 则有一个十分显然的等式： $[(A+B)and(2^i)>0]=[(A+B)\geq (2^i)]-[(A+B)\geq (2^{i+1})]+[(A+B)\geq (3*2^i)]$ 这个式子相当容易理解，这里不多述了 考虑每一位对答案的贡献是独立的，我们每一位分开做 于是现在问题变成了：给定数组$A,B$，求满足$A_i+B_j\geq limit$的数对个数 我们可以将$A,B$排序后，直接$O(n)$计算即可 然而排序是$O(nlogn)$的，这样总复杂度就是$O(nlognlogA)$了，无法通过此题 于是这里有个小技巧 我们从高位往低位做，现在我们要实现的是：将$A$中每个数对$P$取模后将$A$排序 我们发现$A$会被分成两段，一段小于$P$，一段大于等于$P$，只有后面一段要取模，我们可以取模后直接将这两段归并，复杂度是$O(n)$的 时间复杂度：$O(nlogA+nlogn)$ ## 1004 ZYB loves product 个人感觉这题没有上一题难 首先我们考虑$DP$思路，设$f[k][n]$为$n$的$k$分解的权值和 则有$f[k][n]=\sum_{d|n}f[k-1][d]*V(\frac{n}{d})$ 我们可以发现上述$DP$方程是个狄利克雷卷积的形式 然后我们可以发现权值函数$V(x)$是积性函数 所以易得$f[k]$也是个积性函数 于是我们把$n$质因数分解 现在把$n$的规模变成了$a^p$ 设$g[k][p]=f[k][a^p]$ 设$h[p]=V(a^p)$ 于是我们可以得到转移方程$g[k][n]=\sum_{i=0}^{n}g[k-1][i]*h[n-i]$ 这是个卷积形式，我们可以用倍增+FFT计算$g$ 时间复杂度：$O(fplog(p)log(m))$

## 1001 pog loves szh I 读入一个串，第一个字符串首先将指针指向$0$，然后每次将指针$+2$输出即可。第二个字符串首先将指针指向$n-1$,然后每次将指针$-2$，输出即可。 注意题目中描述的是第二个字符串经过翻转才得到读入的字符串的。 ## 1002 pog loves szh II 由于序列中的数可能超过$P$，所以将所有的数读入后进行取模操作。之后将取模后的所有数从小到大排序。题目要求我们求不同位置的两个数的和在取模意义下的最大值，而现在所有数都是小于$P$且排好序的。因此设我任意选了两个数是$X$和$Y$，显然$0 \leq X+Y \leq 2P-2$。若$X+Y < P$,则这次选数的答案就是$X+Y$，若$X+Y \geq P$，则答案是$X+Y-P$。 那么我们可以这样做：将其中最大的两个数字相加取模，设为一个可能的答案记录在ANS中。这个答案是第二种情况的最大值。再对排序好的序列进行枚举，对每个枚举到的数，找出最大的数，使这个数与枚举到的数相加后的和最大且小于P，将之记为可能的答案并于之前找到的最大值ANS进行比较。这个答案是第一种情况中的可能的最大值。而普通的枚举是要超时的，但是我们发现如果从小到大枚举第一个数，那么另一个匹配的数显然是从大到小的，因此可以用一个NOW记录当前另一个匹配的数的位置，每次枚举时NOW递减至符合条件。可以做到$O(n)$的时间复杂度。 综上所述，时间复杂度为快速排序的$O(nlogn)$，空间复杂度为$O(n)$。注意一些特殊情况如同一个位置不能多次选。 ## 1003 pog loves szh III 做这题的方法有很多。下面给出2种解法。 1：维护一个跳表，表示编号为$i$~$i+2^j-1$的LCA，注意在这里求LCA必须用$O(1)$的做法才能通过所有数据。可以转换为RMQ，每次查询时只需查询两个数的LCA即可。 2：考虑dfs序，通过在简单的证明可知L~R的LCA为$L$~$R$中dfs序较小的那个位置与dfs序较大的那个位置的LCA。因此只要通过st表处理L~R最大dfs序与最小dfs序的编号即可。 另外本题可能会出现爆栈的问题，可以通过黑科技避免，或者用bfs来代替dfs，用bfs维护dfs序的方法比较简单不再阐述。 复杂度为$O(nlgn)$ ## 1004 pog loves szh IV 考虑每一位分开统计。 如果没有修改那么可以用点分治来进行统计。加上了修改操作那么我们用线段树来维护点分治每棵子树中到根的路径权值异或和为0、1的节点数量。具体可以弄出dfs序，修改一个点相当于修改一段区间。那么一次修改需要在logn棵树中修改，每次复杂度为$logn$，一共有15位，所以总复杂度为$O(nlognlogn*15)$。另外由于这道题常数比较大，所以时限开了12s。

## 1001 Shaking hands 这是一个简单的图论题，首先Gorwin要和所有人握手，这里贡献答案$2*n$，然后矩阵中的每一对都会贡献$2$。 所以数一下矩阵里面有几个$1$，然后再加上$2*n$就是答案了。复杂度$o(n*n)$ ## 1002 Gunner II 先对数据进行离散化，把数字转化到$0$到$n-1$的区间内。然后对每一种数字串起来按照ID从小到大。可以用链表，或者Vector。 查询的时候要注意如果没有把查询一起离散化的话要先判断一下数字是否可以找得到。 找到之后按照下标去对应的数字串中找出第一个即可。然后删除。如果数字串中没有数字了就应该输出$-1$。 空间复杂度是$O(n)$,时间复杂度是$nlogn+Qlogn$ ## 1003 Happy birthday DP题。类似于背包，$Dp[i][j][k]$表示在第$(I,j)$个格子背包容量为$k$的时候的最大值。 $Dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k], dp[i-1][j][k-w[i][j]]+w[i][j],dp[i][j-1][k-w[i][j]]+w[i][j]);$ 初值所有均为$0$。 答案取$max(dp[n][m][i])$ for $0 \leq i \leq C$, $C$为最大容量。 总状态是$n*m*k$，转移$o(1)$最后复杂度是$n*m*k$ ## 1004 Door game 题是求斐波那切数列对某一个斐波那切数列取余之后数字之和。这题可以找循环结来做。暴力打表发现对于$k \leq 1000$的时候，$F(n)$对$f(k)$取余的周期是比较小的，大概是$o(k)$. 所以可以先暴力计算出对$f(k)$取余的周期$p(k)$。 然后预处理一下前缀和。$Sum[i]$表示$f(0)$到$f(i)$数字和。 答案就是$n/p(k)*sum(p(k)-1)+sum(n\%p(k))$ 数据比较多。可以按照相同的$k$来统一处理。这样的复杂度是$TlogT+p(1)+ p(2)+ p(3)+...+ p(1000)$.大概是百万数量级的。

## Problem A. ZCC loves straight flush 同花顺的情况不多，不妨枚举所有同花顺的情况，看五张牌中有几张已经在给出的牌中出现了，剩下的牌就是必须要换掉的。枚举同花顺时，可以先枚举花色，再枚举顺子中最小的牌。 ## Problem B. ZCC loves strings 结论：对于串a和b，游戏中先手必胜当且仅当$|a|+|b|$为奇数或$a=b$. 我们按$|a|+|b|$的大小从小到大考虑所有的情况。 当$|a|+|b|=0$时，显然先手必败，符合结论。 假设已经证明了$|a|+|b|=k(k<p)$的所有情况满足结论，现在考虑$|a|+|b|=p$的情况。 若$p$是奇数，先手只需要选择长度较短的不为空的串，并使用A操作，就可以转移到$|a|+|b|$为偶数并且两个串不相等或者两个串均为空的情况，这种情况先手必败，故此时先手必胜。 若$p$是偶数，如果两个串相等，显然先手只需要选择使用B操作就能获得胜利了。否则，无论先手如何操作，都只能转移到$|a|+|b|$为奇数的先手必胜的情况。故此时先手必败。 因此，按顺序考虑每一个串，求得在其之前出现的串中，长度奇偶性与其不同的串共有x个，与其完全相同的串有y个，则对答案有$x+y$的贡献。累加即可。 ## Problem C. ZCC loves hacking 因为第N个人的作用仅仅是丰富题面，可以直接把N减1。C的作用仅仅是为了使情景更逼真，可以直接把L和R减去C。 显然选的人的个数最多是$O(\sqrt{n})$的。 题目中有个条件，保证了想要选的数的总和不会超过N。考虑类似于背包的dp。令dp[i][j]表示现在已经选了最大的i个想选的数，和为j时的方案数。转移的时候，要么把之前选择的每一个数增加一，要么在把之前选择的每一个数都增加一个基础上，再新加入一个当前大小为1的数。 若最后选的个数为i，那么就对答案产生$\sum_{j=L}^R dp[i][j]$的贡献。累加即可。注意一个都不选也是合法的。 复杂度$O(n\sqrt{n})$. ## Problem D. ZCC loves math 要求: $$\sum_{i\geq 0} \sum_{j\geq 0} (-1)^{s+t+i+j} {{s}\choose{i}} {{t}\choose{j}} {{N+pi+qj}\choose{m}}$$ 将$i$用$s-i$替代，将$j$用$t-j$替代，得： $$\sum_{i\geq 0} \sum_{j\geq 0} (-1)^{i+j} {{s}\choose{i}} {{t}\choose{j}} {{N+ps+qt-pi-qj} \choose {m}}$$ 设$r=N+ps+qt$，则也就是要求: $$\sum_{i\geq 0} \sum_{j\geq 0} (-1)^{i+j} {{s}\choose{i}} {{t}\choose{j}} {{r-pi-qj} \choose {m}}$$ 设生成函数$F(x),G(x),H(x)$. $$F(x)=(1-x^p)^s=\sum_{i\geq 0} (-1)^i {{s}\choose{i}} x^{pi}$$ $$G(x)=(1-x^q)^t=\sum_{j\geq 0} (-1)^j {{t}\choose{j}} x^{qj}$$ $$H(x)=\frac{1}{(1-x)^{m+1}}=\sum_{k\geq 0} {{k+m}\choose{m}} x^k$$ 那么也就是要求$F(x)G(x)H(x)$中$x^{r-m}$的系数。 $$F(x)G(x)H(x)=\frac {(1-x^p)^s(1-x^q)^t}{(1-x)^{m+1}}$$ $$(\frac{1-x^p}{1-x})^s (\frac{1-x^q}{1-x})^t \frac{1}{(1-x)^{m-s-t+1}}$$ 设$ (\frac{1-x^p}{1-x})^s (\frac{1-x^q}{1-x})^t = \sum_{k\geq 0} a_k x^k$. 那么也就是要求$\sum_{k\geq 0} a_k {{r-k-s-t} \choose {m-s-t}}$. 其中${{r-k-s-t} \choose {m-s-t}}$是关于$k$的次数不超过$m-s-t$的多项式。暴力展开即可得到这个多项式。用矩阵乘法可以求出$\sum_{k\geq 0} a_kk^i (0\leq i\leq m-s-t)$，代入即可。 复杂度为$O((m-s-t)^3(\log s + \log t))$.

##Problem A 枚举这张纸可能的长宽。因为面积为n的矩形必定存在一条边的边长不超过$\sqrt{n}$，所以只需枚举较短的边长，判断较长的边长是否是整数就可以了。 因为面积确定的矩形，长宽差越小，周长越小，所以可以从$\sqrt{n}$开始递减地枚举较短的边长，第一个合法的矩形就是答案。 时间复杂度：O（$\sqrt{n}$） ##Problem B 从1到n枚举k，表示当前要计算的排列与读入的排列前k-1项相同，而第k项不同。对于每一个k，再枚举一个t，表示当前要计算的排列的第k项是t，所以t要比读入的排列的第k项小，并且不与前k-1个数中的任意一个数相等。 那么，剩下的n-k个数任意排列，都满足字典序小于读入的排列。所以要计算它们的逆序对数之和。可以分情况计算： 1. 逆序对中的两个数都在前k-1个位置，可以对于每一个k都暴力计算。 2. 逆序对中的一个数在前k-1个位置，另一个数不在，同样可以对于每一个k都暴力计算。 3. 逆序对中的一个数在第k个位置，另一个数在后n-k个位置。也可以暴力计算。 4. 逆序对中的两个数都在后n-k个位置。这个值可以DP预处理，也可以推出一个式子直接计算。 可以这样考虑：在后n-k个位置中，有一半的排列方式中，第i小的数在第j小的数(i>j)的前面。共有(n-k)!种排列方式，所以对于一对数，有$\frac{(n-k)!}{2}$种排列方式中是逆序对。共$\frac{(n-k)\cdot(n-k-1)}{2}$对数，所以这类逆序对共$\frac{(n-k)\cdot(n-k-1)\cdot(n-k)!}{4}$对。 时间复杂度：O（${n}^{3}$） ##Problem C 因为$\sum_{i=a}^{b}C_{i}^{k}=C_{b+1}^{k+1}-C_{a}^{k+1}$ 所以求同一列的数的和可以变成求两个组合数的差。 因为要模p，p还可能很小，所以可以用lucas定理： $C_{n}^{m}\equiv C_{n/p}^{m/p}\cdot C_{n\%p}^{m\%p}(mod\ p)$ 可以预处理阶乘。 设$n=max({x}_{1},{y}_{1},{x}_{2},{y}_{2})$，那么 时间复杂度：O（$n\cdot logn$） ##Problem D 概率就是(必胜的点对数/总点对数)，总点对数是${n}^{2}$，我们需要考虑如何求必胜点对数。 这个游戏就像是Nim游戏，一个四元组就相当于一堆石头，石头的数量就是字典序比它小的合法四元组的个数，同时也是这个四元组的SG值。 考虑如何求字典序比(a,b,c,d)小的合法四元组(p,q,s,t)的数量： 1. p<a。可以预处理。所有第一个元素为n的合法四元组数量是 $\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)$ 预处理前缀和就行了。 2. p=a,q<b。满足这个条件的合法四元组数量是 $\sum_{i=1}^{b-1}\sum_{j=1}^{a}gcd(i,j)$ 3. p=a,q=b,s<c。满足这个条件的合法四元组数量是 $\sum_{i=1}^{c-1}gcd(i,b)$ 4. p=a,q=b,s=c,t<d。满足这个条件的合法四元组数量是(d-1)。 上面的一些式子可以这样计算： $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j) =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|i\&d|j}\phi (d) =\sum_{d=1}^{min(n,m)}\phi (d)\cdot\frac{n}{d}\cdot\frac{m}{d}$ （除法为整除） $\frac{n}{d}, \frac{m}{d}$只会有O($\sqrt{n}$)种不同的值，相同的值需要一起计算，所以要预处理$\phi (d)$及其前缀和。这样，一次计算的时间复杂度是O($\sqrt{n}$)的。 $\sum_{i=1}^{n}gcd(i,m) =\sum_{i=1}^{n}\sum_{d|i\&d|m}\phi (d) =\sum_{d|m}\phi (d)\cdot\frac{n}{d}$ （除法为整除） m的约数不会太多，所以可以直接枚举d进行计算。为了快速找出m的约数，可以对m分解质因数。可以先预处理出10000以内所有数分解质因数的结果，为便于存储，可以只记录它的一个质因子，m除一下这个质因子，递归下去就能得到它的所有质因子。 这样，就能求出每个四元组的SG值了。 先手必胜当且仅当所有四元组SG值的异或和不为零。那么问题就变成了求树上有多少对点，满足连接它们的路径上所有点的SG值异或和不为零。可以通过点分治求解。 设$m=max(a,b,c,d)$，那么 时间复杂度：O（$n\cdot{log}^{2}n+(n+m)\sqrt{m}$）