2017 Multi-University Training Contest 7 solutions BY 杭州二中

1001

有$n$个小于$32677$的非负整数$x_{1...n}$,计算$y_{i,j}=x_i\times x_j\mod32677$,问有多少有序六元组$(a,b,c,d,e,f)$,使得$\gcd(y_{a,b},y_{c,d})=\gcd(y_{c,d},y_{e,f})=\gcd(y_{e,f},y_{a,b})=1$,模$2^{30}$。$n\leq200000$。

第一步我们要计算每种y值出现了多少次ny[],并且我们现在知道每种x值出现了多少次nx[],发现对nx[]做下标乘模32677的自卷积就能得到ny[],考虑如何加速这个卷积。计算知32677是两个质数41和797的乘积,可以用中国剩余定理拆开变成两维下标乘模质数的卷积,而下标乘模质数的卷积是可以先判定0,然后通过用原根的次幂表示每个下标,转化为一般循环卷积的。所以这里变换一下然后做一个二维FFT就好了。
第二部相当于要算sum{ny[a]*ny[b]*ny[c](gcd(a,b)=gcd(a,c)=gcd(b,c)=1)},对每两个都反演一下就得到了sum{miu[a]*miu[b]*miu[c]*S[lcm(a,b)]*S[lcm(a,c)]*S[lcm(b,c)]},其中miu[a]为a的莫比乌斯函数,而S[a]=sum{ny[k*a]}。然而满足miu[a]不为0且miu[b]不为0且lcm(a,b)<=n的数对并不多,而上式的三个参数必须两两满足这个条件,用三元环的做法可以解决。

1002

有一棵$n$个点的有根树,标号为$0$到$n-1$,$i$号点的父亲是$\lfloor\frac{i-1}{k}\rfloor$号点,求所有子树大小的异或和。$1\leq n,k\leq10^{18}$。

这是一棵完全k叉树,考虑根的所有孩子,最多只有一个不是满k叉树,对这个孩子进行递归处理即可。k>1时只有log层,直接做就到底就好了,k=1时要特判。

1003

有一个$n$行$m$列的棋盘,最初每个位置是指定的红色或蓝色或白色。你要将白色的位置染成红色或蓝色,使得对于任意一个长宽均为偶数的连续子棋盘,其中红色和蓝色的位置数相等,求方案数模$998244353$。$1\leq n,m\leq10^3$。

即每个2*2连续子矩阵红蓝数量相等。令红为1,蓝为0,如果让把所有格子按行号与列号的和奇偶反色,则转化为每个2*2子矩阵对角线的和相等。发现这个条件当且仅当每行都是全1或全0,或者每列都是全1或全0,讨论一下就好了。

1004

有一个$n$行$n$列的棋盘,每个位置是黑色或白色,保证其上下左右斜向均对称。给出所有具有代表性的,即行号$x$和列号$y$满足$x\leq y\leq\lfloor\frac{n+1}{2}\rfloor$的$t$个黑方格。有一个$n$层$n$行$n$列的立方体,六个面和棋盘都相同。对于三组对面,对于一面中的每个黑色位置,均沿竖直方向挖穿至另一面的对应黑色位置,求剩余小立方体数量。$1\leq n\leq6\times10^4,1\leq t\leq1.2\times10^5$。

考虑计算被挖掉的数量,使用容斥,先把每个黑色位置挖穿到底的每个方块都算上去,然后把算到两次的去掉(即形如(x,y),(x,z)的两个位置),最后把重复去掉的加回去(即形如(x,y),(y,z),(x,z)的三个位置)。最后一步是一个经典的三元环计数,可以用分块做。注意如果把约8t个黑色位置全部建出来跑三元环,可能会比较卡常,直接利用对称性做就好了。

1005

给定正整数$a$,求对于所有正整数$b$,$a\mod b$有多少种可能的结果。$1\leq a\leq10^9$。

显然小于<a/2的每个非负整数c都是可能成为余数的,取b=a-c即可,另外a本身也能成为余数,而其他数显然都不可能。

1006

从不大于$n$的所有正整数中选出至少$1$个且至多$k$个使得乘积不包含平方因子,对$10^9+7$取模。$1\leq n,k\leq500$。

每个质因子只能出现最多一次,考虑如何分配。然后注意到大于根号n的质因子,每个数只能包含一个。于是把小于根号n的所有8个质因子状压起来,枚举每个大于根号n的质因子,考虑怎么选小质因子搭配成一个不大于n的数就好了。

1007

有$n$个小朋友,标号为$1$到$n$,你要给每个小朋友至少$1$个且至多$m$个的糖果。小朋友们共提出$k$个要求,每个要求包括三个整数$x,y,z$,表示$x$号小朋友得到的糖果数减去$y$号小朋友得到的糖果数,结果应当不大于$z$。如果你给$i$号小朋友$j$颗糖果,他会获得$w_{i,j}$的满意度,你需要最大化所有小朋友的满意度之和。$1\leq n,m\leq50,1\leq k\leq150,1\leq w_{i,j}\leq10^3$。

用i.j这点表示给第i个孩子至少j块糖,当这个点属于S集合时所代表条件成立。然后i.j->i.j+1连1000-wi,j,i.m向T连1000-wi,m,S向i.1连inf。如果存在ax-ay>=z,x.k->y.k+z连inf。跑最小割,再用n*1000减掉答案。

1008

平面直角坐标系上有$n$个整点,第$i$个点有一个点权$val_i$,坐标为$(x_i,y_i)$,其中不存在任意两点连成的直线经过原点。这些整点两两之间连有一条线段,线段的权值为其两端点的权值之积。你需要作一条过原点而不过任意一个给定整点的直线,使得和这条直线相交的线段的权值和最大。$1\leq n\leq5\times10^4,1\leq val_i\leq10^4,|x_i|,|y_i|\leq10^9$。

对于一条直线,线段权值和实际上就等于其两边点权和的乘积,所以把所有点按极角排个序,然后扫一圈就好了。

1009

有$n$个小于质数$p$的非负整数$a_{1…n}$,你想知道有多少对$i,j(1\leq i<j\leq n)$,使得模$p$意义下$\frac{1}{a_i+a_j}\equiv\frac{1}{a_i}+\frac{1}{a_j}$,即这两数的和的逆元等于它们逆元的和,注意零元没有逆元。$1\leq n\leq10^5,2\leq p\leq10^{18}$。

把式子推一下,可以得到当且仅当模意义下两数之比为(1+sqrt(-3))/2或(1-sqrt(-3))/2即可。求取这个可以直接拿二次剩余硬上,也可以优雅地发现这其实就是x^3=1除x=1外的其他两个解然后利用这个来做。注意特判-3无二次剩余的情况,并且处理好p=3的可能比较特殊的情况,以及记得把0去掉。

1010

有一个长度为$n$的整数序列$\{a_n\}$,对其做$m$次前缀异或和,求最终的序列。$1\leq n\leq2\times10^5,1\leq m\leq10^9,0\leq a_i\leq2^{30}-1$。

可以发现做m次后,位置为x的初始值对位置为y的最终值的贡献次数是一个只和m与y-x相关的组合式,而我们只关注这个次数的奇偶性。考虑Lucas定理,C(a,b)是奇数当且仅当把a,b二进制表达后b中1的位置是a中1的位置的子集,于是这里所有满足条件的b有很好的性质,对每一个二进制位独立处理就能算出答案。

1011

以下是Kolakoski数列:$1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1……$,这个数列仅有$1$和$2$组成,并且第一项是$1$。同时还满足一个性质,如果把相邻且相同的项看成一组,可以得到$1,22,11,2,1,22,1,22,11,2,11,22,1……$,计算每一组项的数量,则能得到这个序列本身。这个数列是可以被唯一确定的,请求出它的第$n$项。$1\leq n\leq10^7$。

考虑如何模拟数列的构造,只要在拿一个指针在序列中间扫的同时,往序列末端加数就可以了。

1012

有$m$个集合$P_i,Q_i$,$\forall i(1\leq i\leq m),Pi,Qi\subseteq \{1…i-1\}$。有一个$m$层循环,第$j$层循环的循环变量是$i_j$,下界是$\max\{i_k(k\in P_j)\}$(特殊地,$P_j$为空集表示下界是$1$),上界是$\min\{i_k(k\in Q_j)\}$(特殊地,$Q_j$为空集表示上界是$n$)。求循环内部被执行的次数,对$p$取模。$1\leq m\leq15,1\leq n\leq10^9,2\leq p\leq10^9+7$。

注意到这里循环的下界一定是若干个变量的最大值,而上界一定是若干个变量的最小值,这就决定了变量之间的某些大小关系。由于n很大,我们考虑这些变量的的完整大小关系,如果能分成 k 组,每一组值相等且前一组的值严格小于后一组,那么再考虑具体取值就有C(n,k)种方案。考虑dp,令f[S][k]表示将所有变量的子集S表示成k层的方案数,转移时选取S的子集T,考察T能否作为最后一层即可。

1013

$Hazel$ 想了解关于二叉树的一切。

她有一棵带标号满二叉树 $T$ 。

对于 $T$ 中每个点 $i$ ,$Hazel$ 定义其高度 $h_i$ 为点 $i$ 到其子树中任意叶子节点的最短路径上的点数(包括起点和终点),其权重 $A_i=X^{hi}$ 。

她想给每个点染上颜色 $B_i$ 满足

* $\forall i\in T,B_i\in N$

* $\forall i\in T,B_i\ge B_{fa_i}$

* $Y\ge 2\times \sum \limits_{i\in leaf} B_i-\sum \limits_{i\in T}B_i$

(单独定义 $B_{fa_{root}}=0$ )

对于树 $T$ , $Hazel$ 定义其美丽程度 $S=\sum \limits_{i\in T}A_i\times B_i$ ,树高 $H=\max \limits_{i\in T} h_i$ 。

她想知道有多少种给 $i$ 染色的方案,使得这个二叉树的美丽程度 $S$ 是 $P$ 的倍数,答案对 $1000000007$ 取模。

两个染色的方案被认为是不同的,当且仅当存在点 $i$ ,在两次染色方案中染的颜色不同。

---

我们把染上颜色 $B_i$ 看作将 $i$ 点覆盖 $B_i$ 次。

由于 $B_i-B_{fa_i}\ge 0$ 以及发现 $2\times \sum \limits_{i\in leaf} B_i-\sum \limits_{i\in T}B_i = \sum \limits_{i\in T} B_i - B_{fa_i} \le Y$ ,我们考虑现在不是覆盖一个点,而是覆盖一个完整的子树。那么从根到叶子的递推一下可以发现,覆盖点 $i$ 的子树次数就是 $B_i - B_{fa_i}$ 。

现在染色操作被转化为每次可以覆盖一个子树,总次数不超过 $Y$。

考虑覆盖一个子树的贡献 $C_i$ ,是子树内的点 $A$ 的和。很容易发现,同一深度的点 $C$ 是相同的。那么对深度做一次递推就能求出其贡献 $C_{d}=2\times C_{d-1}+A_d,A_d=X\times A_{d-1}$ 。但是深度有 $10^{18}$ ,直接做肯定不行,观察一下递推试,只和两项有关,那么其在模 $P$ 的意义下有循环节,且根据抽屉原理,循环节长度至多为 $P^2$ 。至此解决了 $C$ 的求解。

由于能快速求 $C$ ,我们能很方便的知道贡献模 $P$ 为 $j$ 的子树的个数,剩余计算方案数的部分就很简单了, $F(i,j)$ 表示当前已经染了 $i$ 个节点,总美丽程度 $S$ 模 $P$ 为 $j$ 的方案数,从小到大枚举加的子树贡献模意义下的值,组合数转移即可。

总时间复杂度为 $O(Y^2P^2)$ 。