6-1

西南科技大学第十二届ACM/ICPC程序设计大赛题解

这里是ABCDEF题的题解,GHIJK题题解:哈特13

校赛终于结束了,这次比赛还算比较完美,没有出现题目上的问题=。=

废话不多说,上题解(代码仅供参考,写的太丑)

 


 

A. A+B Problem

观察一下会发现每个 \(A_i\) 会加上数组 \(B\) 的一段,所以利用前缀和的思想即可。这道题暴力是肯定会超时的。

 


 

B. Football

这道题主要就是模拟,暴力枚举,处理好优先级关系,各种姿势都能过。

 


 

C. GCD

题目求 \(\begin{split}G(a,b)=\prod_{1\leqslant i< b, a\leqslant j\leqslant b,i< j}\ gcd (i,j)\end{split}\)

\(\begin{split}g(n)=\prod_{1\leqslant i< j\leqslant n} gcd(i,j)\end{split}\)

\(G(a,b)=\frac{g(b)}{g(a-1)}\)

则问题转化成求 \(g(n)\) ,就是一个很眼熟的题了,具体过程:

\(\begin{split}f(n)=\prod_{i=1}^{n-1} gcd(i,n)\end{split}\)

\(\begin{split} g(n) & =\prod_{j=2}^{n} f(j)\\ &=g(n-1)f(n)\end{split}\)

所有 \(gcd(x,n)\) 的值都是 \(n\) 的约数,按照约数进行分类,令 \(p(d,n)\) 表示满足 \(gcd(x,n)=d(x< n)\) 的正整数 \(x\) 的个数

\(f(n)=\prod_{d|n} d^{p(d,n)}\)

\(gcd (x, n) = d\) 的充要条件为 \(gcd (\frac{x}{d}, \frac{n}{d}) = 1\) ,因此满足条件的 \(\frac{x}{d}\)\(\phi(\frac{n}{d})\) 个,则 \(f(n)=\prod_{d|n}d^{\phi(\frac{n}{d})}\)

如果依次计算 \(f(n)\) ,枚举 \(f(n)\) 的约数的话效率太低,因此对于每个 \(d\) 枚举它的倍数 \(n\) 并更新 \(f(n)\)

因为运算结果要对 \(10^9+7\) 取余,所以还需要求 \(g(a-1)\) 的逆元

 


 

D. Mode

首先要明白,m一定是数组a中的数,这个有兴趣可以自己证明一下。

有了这个前提,我们可以先将数组a按升序排序。

然后这道题的解法就是二分长度(即答案中的出现次数),然后枚举端点,也可以枚举端点,然后二分长度。

设端点坐标为 \(x\) ,则当长度 \(len\) 满足 \(len\times a_x-\sum_{i=x-len+1}^{x}a_i\leqslant k\) 时,表示可以让 \(a_i\) 出现 \(len\) 次,其中 \(\sum_{i=x-len+1}^{x}a_i\) 可以预处理前缀和快速求出

 


 

E. 01 String

水题之一,答案就是0和1的个数之差

 


 

F. Fibonacci

列出前几项会发现,设 \(F_i\) 为A, \(F_{i+1}\) 为B,那么会发现之后的组合顺序有:BA、AB、BB

\(C_A\) 为字符串s在A中出现的次数, \(C_{AB}\) 为字符串s在AB相接处出现的次数,其他同理

\(F_k\) 中出现的次数为 \(C_A+C_B+C_{BA}+C_{AB}+C_{BB}\)

但不可能直接求出 \(F_k\) ,所以我们需要找出 \(F_n\)\(F_{n+1}\)\(C_A,C_B,C_{BA},C_{AB},C_{BB}\) 的关系(为了简洁,以下公式中省略C)。

通过观察可以得出下面的关系:

\[\begin{equation}\label{1}\left\{\begin{matrix}A_{n+1}=BA_{n+1}&=&B_n\\B_{n+1}&=&A_n+B_n\\AB_{n+1}&=&A_n+BB_n\\BB_{n+1}&=&AB_n\end{matrix}\right.\end{equation}\]

设:

\[\begin{equation}\label{2}\begin{pmatrix}A_n & B_n & AB_n & BB_n\end{pmatrix}\begin{pmatrix}a_1 & a_2 & a_3 & a_4\\b_1 & b_2 & b_3 & b_4\\c_1 & c_2 & c_3 & c_4\\d_1 & d_2 & d_3 & d_4\end{pmatrix}=\begin{pmatrix}A_{n+1} & B_{n+1} & AB_{n+1} & BB_{n+1}\end{pmatrix}\end{equation}\]

\((\ref{1})\)\((\ref{2})\) 可得:

\[\begin{equation}\label{3}\begin{pmatrix}A_n & B_n & AB_n & BB_n\end{pmatrix}\begin{pmatrix}0 & 1 & 1 & 0\\1 & 1 & 0 & 0\\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\end{pmatrix}=\begin{pmatrix}A_{n+1} & B_{n+1} & AB_{n+1} & BB_{n+1}\end{pmatrix}\end{equation}\]

则:

\[\begin{equation}\label{4}\begin{pmatrix}A_1 & B_1 & AB_1 & BB_1\end{pmatrix}\begin{pmatrix}0 & 1 & 1 & 0\\1 & 1 & 0 & 0\\0 & 0 & 0 & 1\\0 & 0 & 1 & 0\end{pmatrix}^{n-1}=\begin{pmatrix}A_{n} & B_{n} & AB_{n} & BB_{n}\end{pmatrix}\end{equation}\]

由此可以先找出k较小时字符串s出现的次数,然后通过矩阵快速幂来求出答案

 

Categories: ACM