[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)

题目链接

题意:

给定一个长度为 $n$ 的序列 $a$ ,$n \le 10^6$ ,每个数字 $a_i$ ,满足 $0 \le a_i \le 10^6$ .

可以对这个序列进行一种操作,把第 $i$ 个数字中的一份移动到 $i-1$ 或者 $i+1$ .即操作过后 $i$ 处变为 $a_i-1 , a_{i+1}$ 或者 $a_{i-1}$变为 原来的数字+1.

问最少需要多少次操作使得存在某个数字 $k>1$ 满足所有的 $a_i$ 都可以被k整除($0$可以被任何数整除),操作过程要满足所有的 $0\le a_i$ 。

题解:

考虑操作完成之后的结果,如果每一个数字都能被 $k$ 整除,那么显然 $S = \sum_{i=1}^{n} a_i$ 也可以被k整除。所以 $k$ 一定是 $S$ 的一个因数。

然后显然 $k$ 为合数时的情况,要么被 $k=其质因子$ 的情况包括,要么就劣于这种情况。所以我们只需要考虑 $k$ 为质数的情况,也就是 $S$ 的所有质因子。

由 $S$ 最大为 $10^{12}$ 可知,其质因子最多应该只有$10-20$种,而且分解出质因子可以用时间复杂度 $O(\sqrt{n})$ 的算法,也就是约 $10^6$ 。

继续阅读“[思维][贪心][贡献拆分] codeforces 1255 E2 Send Boxes to Alice (Hard Version)”

[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M

题目链接

题意:

求 $$\sum_{k=1}^{N}((kM)\& M)mod(10^9+7)$$

其中 $1 \le N \le 10^{18}$ , $1 \le M \le 10^{11}$

题解:

按位来做,考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算,比如当前处理的是第i位 ,就可以写成 $$\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^i} \rfloor)-2*\sum_{k=1}^{N}(\lfloor \frac{k*M}{2^{i+1}} \rfloor)$$
这显然是一个类欧几里得的模板式子,我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M”

[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree

题目链接

题意:

给定一棵树,每个节点上有 $a_i$ 个苹果,两个人轮流操作,每次把一个节点的一部分(或全部)苹果移到他的某个儿子中(如果是叶子节点没有儿子那么就吃掉这些苹果),最后不能走的人输。现在在游戏开始前先手可以选取两个不同的节点交换他们之间的苹果数,问有多少种交换方式可以使得先手必胜。
数据范围: $1\le n \le 10^5,\;1\le a_i \le 10^7$

题解:

博弈本身是很简单的阶梯博弈。由阶梯博弈的知识,求胜负只需要计算奇数位上的SG函数异或和即可,这题只不过把阶梯转移到了树上,但是略微分析就可以发现和链状的阶梯是没有区别的,都是奇数往偶数转移当作拿走,偶数往奇数转移就对称操作。

  • 然后考虑计数:
    • 假设初始状态是必胜态,那么可以先计入奇数层自己内部交换和偶数层自己内部交换的对数,分别为 $C_{num\;of\;odd\;level}^2$ 和 $C_{num\;of\;even\;level}^2$;
    • 然后计算奇偶层之间互换的对数,设异或和结果为 $ans$ ,假设一对数 $a_u$ $a_v$ 交换之后可以使得 $ans=0$ ,那么由亦或的性质可得 $a_v=ans\oplus a_u$,那么我们就可以枚举 $a_u$ 的值,找 $a_v$ 有多少个,而后者利用 $map$ 可以很容易的预处理出来。
      继续阅读“[博弈论][组合游戏][组合计数] codeforces 812E Sagheer and Apple Tree”

[线性基][线段树][模板] 牛客多校第四场 B xor

题目链接

题意:

$n$ 个集合,每个集合最多32个unsigned int范围的整数, $m$ 个询问,每次问下标在 $[l,r]$ 之间的集合能否表示出 $x$ 。数据范围 $1\le n,m\le 50000$,每个数字都在 unsigned int 以内。

题解:

线段树维护线性基即可。学习了一发板子。
继续阅读“[线性基][线段树][模板] 牛客多校第四场 B xor”

[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish

题目链接

题意:

给定一段代码,让模仿出来他的代码缩进风格。缩进风格由三个数字 $R C S$ 确定,分别代表到当前位置有多少个未封闭的圆括号/花括号/方括号 ,然后每多一个 $R/C/S$ 的话,多出来的缩进数是确定的。现在要求用学习到的代码风格对新的一段没有缩进的代码进行缩进,输出每行缩进的空格数。数据范围行数 $N\le 80$ , 每行最多80个字符。

题解:

显然难点在于能不能用已经学到的经验来推断出来现在该缩进多少。把所有 $(r,c,s)$ 的三元组看成一组向量,等于说新的向量能不能被之前出现过的表示出来,也就是是否线性相关。那么我们只需要用高斯消元去解就行了,如果有唯一解那么一定是可以被表示出来的,这是后这个就能解出来了,如果不是的话就把这个新的向量插进去作为一个新的基。

这个题当时的问题就在于没有一个好的高斯消元板子。。。于是很正经的去找了一个好的板子TAT

wa点:没注意到题目说RCS最多只有20个最少至少有1个。。。这个限制导致了在某些情况下方程解不出来但是仍然可以确定RCS的数值。

继续阅读“[高斯消元][模拟][比赛补题][×] codeforces gym 101412 B Stylish”

[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query

题目链接

题意:

给定 $N$ 个数字, $Q$ 次询问,每次询问为查询下标在 $[l,r]$ 之间的所有数字中所有可能的子段的 $gcd$ 有多少种。$N,Q < 10^5 , a_i < 10^6$

题解:

首先一个重要的结论:以固定点为结尾的子段的 $gcd$ 种数不超过 $max(n,log(max(a_i)))$ 证明:每次往原有的序列里加入一个数字的话, $gcd$ 要么不变,要么至少变为原来的1/2,因此为指数级减小。

有了这个结论,我们可以试着来枚举一个端点考虑本题,不妨枚举每个段的右端点$r_j$ , 假设集合$S$表示以$r_{j-1}$ 为结尾的所有 $gcd$ ,那么要求出以$r_j$为结尾的所有 $gcd$ ,只需遍历S中的每个数字$d_k$,计算其与$a_j$ 的 $gcd$ ,放入新集合$S^{‘}$即可。这样的话我们可以得到一个空间为$O(nlogn)$的结果,表示以每个点为结尾的所有段的 $gcd$ 都是哪些数字。

现在来考虑查询。每次查询的话是要求出来$[l,r]$之间所有可能的 $gcd$ 。直接暴力不可取,由上面的结果可以试着考虑能否转化为前缀问题。可以发现,如果我们对所有的$[l,r]$离线处理,按$r$从小到大排序,并且按照这个顺序来调整已经遇到过的 $gcd$ 的信息的话,每次的查询只需要考虑有多少个 $gcd$ 出现的最右左端点大于等于l,这句话具体的意思是,一个 $gcd$ 可能出现过了很多次,不同的段都可以得到这个 $gcd$ ,但是我们只考虑这些段中左端点l_j最大的那个点$p_j$,这样的话如果$l<=p_j$那么可以确定$[l,r]$中一定有这个 $gcd$ (种类+1),这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”

[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅

2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅

题目链接

网络赛最难的一个题,也是我唯一一个不会做的。

看了大大的题解发现我其实已经推到了倒数第二步T_T

但是眼拙没看出来可以写成卷积形式。。。所以按照那个推法无论如何都是O(n^2)的复杂度,变成卷积形式就可以用fft加速直接O(nlogn)一次性求出所有点的值了。。。
继续阅读“[比赛补题][FFT][组合数学][母函数][×]2019 xdu网络赛F XDOJ 1409: 背包弹夹平底锅”

[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR

2019 ICPC南昌邀请赛网络赛 K MORE XOR

题目链接

(⊙﹏⊙)不知道为什么比赛时候这个题和D题死推不出来,比赛完了5分钟ac,我大概脑子坏掉了。真的是超超超超级简单的一个题,但是我光顾着用数学公式推了所以推出来结果巨复杂(⊙﹏⊙)服了自己了。

题解:先说怎么求g(l,r): 首先f(l,r)很好求,利用异或的性质,预处理出来前缀异或和就可以了。设预处理出来p1[x]表示从a[1]到a[x]的异或和,那么很容易得到\[f(l,r)=p1[l-1]\oplus p2[r] \], 那么可以由g的定义就可以知道 \[ g(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} f(i,j) =\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} p1[i-1]\oplus p1[j] \];当然这个东西还是很复杂的,我们想办法把他复杂度搞到O(1):考虑每个p1[x]出现的次数,列个表可以发现,在这个求和式中出现的所有下标,从l-1变化到r, 而每个下标出现的次数都是一样的,这个次数等于 r-l+1 ,那么就可以得出结论,如果r-l+1为偶数,则g(l,r)应为0,否则应为\[ \sum_{i=l-1}^{r} p1[i] \],注意到这个式子又可以用p1的前缀和来O(1)计算,所以又可以提前求出来p1的前缀和p2,这样的话g(l,r)就可以表示为

\[g(l,r)=
\begin{cases}
0& \text{(r-l+1) is odd}\\
p2[l-2]\oplus p2[r]& \text{else }
\end{cases}\]

有了g(l,r)再来考虑w(l,r),\[w(l,r)=\sum_{i=l}^{i=r} \sum_{j=i}^{j=r} g(i,j) \],就跟g的表达式很像,但是这里不能直接再套用g关于p1的公式,因为g里面有很多的0是跟p2无关的,换句话说这些0并不是由p2[l-2]^p2[r]求出来的,所以要分类讨论。分析方法跟g是类似的,列一个表观察每个p2出现的规律,可以发现,这个规律是4个一循环的结构,设\[t=(r-l+1)\mod 4\]; 则当t==0时,所有的p2下标出现次数均为偶数次,也就是结果一定为0,t==2时,所有的p2下标出现次数均为奇数,这样的话即等于\[\sum_{i=l-1}^{r} p2[i] \],这个式子说明我们可以再用一个p2的前缀和p3来O(1)计算这个结果。这是比较简单的两种情况,另外两种是t==1和t==3,这两种一种是奇数项的出现次数为奇数偶数项为偶数,另一种是奇数项出现次数为偶数而偶数项出现次数为奇数,这意味着可以用一个分奇偶的前缀和来O(1)求得这个式子只不过仍需要分类讨论一次。。若令p31[i]和p32[i]分别表示p2的奇偶前缀和,t=(r-l+1)%4, 则w(l,r)的表达式为

\[
w(l,r)=
\begin{cases}
0& \text{t=0}\\
p31[r]\oplus p31[l-3]& \text{t=1 and r is odd}\\
p32[r]\oplus p32[l-3]& \text{t=1 and r is even}\\
p3[l-3]\oplus p3[r]& \text{t=2}\\
p32[r-1]\oplus p32[l-2]& \text{t=3 and r is odd}\\
p31[r]\oplus p31[l-3]& \text{t=3 and r is even}
\end{cases}
\]

这样的话整个问题就可以O(1)解决了。。不知道我当时脑子怎么回事就没推出来
继续阅读“[比赛补题][×] 2019 ICPC南昌邀请赛网络赛 K MORE XOR”