【题解】简单数学题放送

四处找来的简单数学题,挑了一些题目整理一下。

[ACM/ICPC CERC 2013] Magical GCD

给一个长度为 $n(n≤100000)$ 的数列(每个数 $a[i]≤10^{12}$ ),找到一个连续子序列使得子序列的公约数与长度的乘积最大,求这个最大值。共 T 组数据。

大概是利用了 $\gcd$ 的一定性质。考虑对于一个确定的右端点 $r$ ,创建一张保存 $\gcd(l,r)$ 本质不同的 $l$ 表,不难发现这张表的长度是 $O(\log n)$ 的。这样就可以用链表维护一下这个表,每次右端 $+1$ 时暴力合并表中间相同的元素。最终复杂度 $O(n\log n)$ 。

除法表达式

给出一个除法表达式 $X_1/X_2/X_3\cdots/X_n$ 。求能否通过加括号的方式让式子的值为整数

考虑贪心的放括号,一定是这么放的:$X_1/(X_2/X_3\cdots/X_n)$ 。因为这样会使分母上的数最多,为 $X_1\cdot \prod X_{j{[j=2\to n]}}$ 。于是就分解一下质因数就好了。

[UVA11582] Colossal Fibonacci Numers! 加强版

求一个广义的斐波那契递推:在 $f(0)=c,f(1)=d$ 时:

的第 $f(x^y)$ 项在模 $n$ 下的值。$1\leq n\leq 5000$ 。

考虑由于是 $2$ 阶线性递推,那么显然在模 $n$ 意义下循环节长度有一个上界 $O(n^2)$ 。于是就可以暴力求出循环节长度 $o$,计算 $a^b$ 的时候模 $o$ 即可。

[UVA10791] Minimum Sum LCM

给定一个 $n$ ,求至少两个正整数使得他们最小公倍数为 $n$ 且其和最小。$n\in \rm int$ 。

考虑为了使和最小,有多余因子是不够优的。所以答案就是 $\sum p_k^{a_k}$ 。注意当 $n$ 是素数幂或者 $1$ 时需要判一点细节。

[ACM/ICPC Dhaka 2013] GCD XOR

给定 $n$ ,求有多少对正整数 $(a,b)$ 满足 $1\leq b\leq a\leq n$ ,且 $\gcd(a,b)=a\operatorname{xor} b$ 。

$1\leq n\leq 10^6$ .

考虑暴力枚举 $a$ 的约数 $c$ 再去 check 的复杂度是 $\log^2n$ 的,需要优化。发现如果 $\gcd(a,b)=a\operatorname{xor} b$ ,那么 $a-b=a\operatorname{xor} b$ 。原因是考虑 $\gcd(a,b)=\gcd(b,a-b)\leq a-b\leq a\operatorname{xor} b$ 。所以这就可以省掉一个求 $\gcd$ 的 $\log$ ,直接枚举 $a$ 的约数 $c$ ,再去 check 是否有 $c=a\operatorname{xor}(a-c)$ 即可。

[ACM/ICPC NEERC 2004] Irrelevant Elements

给定一个长为 $n$ 的数列,每次相邻两项相加得到一个长度减小 $1$ 的新数列,求最后长度为 $1$ 时的数模 $m$ 的余数和哪几项无关。

$1\leq n\leq 10^6$ 。

考虑最后每一项的贡献系数一定是杨辉三角的形式。这样只需要求每一个系数是否是 $m$ 的倍数。注意到暴力求组合数精度会爆炸,于是考虑分解,但是分解了之后复杂度会爆炸。考虑有

那么就可以通过分解质因数的方式来判断是否是 $m$ 的倍数。最后复杂度 $O(n\log n)$。

[ACM/ICPC NEERC 2009] Headshot

枪里有 $n$ 个弹夹 $m$ 颗子弹。你扣了一次扳机之后没有子弹。你希望下一枪也没子弹。你是应该立即再扣一枪还是随机转一下再扣?

因为已经扣了一枪,所以考虑条件概率公式 $P(A) = P(B)\times P(A\mid B)$ ,即可以知道连续两枪没有子弹的概率是 $\dfrac{\mathrm{cnt}(00)}{\mathrm{cnt}(0)}$ 。随机转一下的概率是 $\dfrac{\mathrm{cnt}(0)}{\mathrm{cnt}(0)+\mathrm{cnt}(1)}$ 。比较一下即可。

[UVA10491] Cows and Cars

著名主持人和羊和车问题。共有 $m$ 个羊和 $n$ 个车。主持人会打开 $k$ 扇门。输出在「总是换门」策略的基础上赢得车的概率。

还是条件概率题。考虑一开始在打开了 $k$ 个🐑门之后,还剩 $m-k$ 个羊门,剩 $m+n-k-1$ 个门可以换。那么考虑吧分类:

1、一开始选的是羊门,这部分概率是 $\dfrac{m}{n+m}\cdot \dfrac{n}{n+m-k-1}$ 。

2、一开始选的是车门,这部分概率是 $\dfrac{n}{n+m}\cdot \dfrac{n-1}{n+m-k-1}$ 。

相加一下即可。

[UVA580] Critical Mass

要求你统计所有长度为 $n$ 的 $01$ 串中,有多少个串内至少有 $3$ 个 $1$ 放在一起。

考虑分类讨论最左边连续三个 $1$ 的位置,假设是 $i,i+1,i+2$。设 $f(i)$ 表示答案,那么有

但是这并不对,因为可能会存在 $i-2,i-1,i$ 或者 $i-1,i,i+1$ 是连续 $3$ 个 $1$ (梦回麻将) 。于是就考虑钦定 $i-1$ 放 $0$ 。所以就变成了

其中要单独加上 $i=1$ 的贡献。注意到这就是一个分治 FFT 的标准形式,随便优化一下就好了。

[UVA12034] Race

求 $n$ 个人赛马的最终名次可能性种类数。

$1\leq n\leq 10^5$ 。

暴力的话,考虑最后有 $k$ 个人并列第一。那么有转移

算一下即可。那么如果 $n=10^5$,可以考虑直接分治 FFT。即考虑把式子拆开为

令 $g(i)=\dfrac{1}{i!}$,就可以直接做了。复杂度 $O(n\log ^2 n)$ 。

[ACM/ICPC Daejon 2012] Pole Arrangement

长度分别为 $1\sim n$ 的杆子排成一列。从左边能看到 $l$ 根,从右边能看到 $r$ 根。求有多少种排列数。

$1\leq n\leq 300$ 。

考虑直接 $dp$ 。设 $f_{i,j,k}$ 表示考虑从小到大的 $i$ 个杆子,从左边看到 $j$ 根,从右边看到 $k$ 根的方案数。那么考虑每次通过放一个更加小的杆子来转移。即

其中分别是放在两边和中间的方案数。

考虑这种排列计数的题目大部分都是枚举最大的或者最小的来转移。然而此题放最长的杆子会锅,于是就只能拿最小的杆子来转移。

[ACM/ICPC Wuhan 2009] Crossing Rivers

两地之间距离为 $n$ ,行走速度 $1/s$ 。有 $m$ 条长度分别为 $L_i$ 的河,在上面划船速度为 $v_i$ 。每次到达一条河时需要等船过来再走。如果出门时船的位置和朝向都是随机分布,求期望多久到达对岸。

比较基础的一道期望题目。考虑过第 $i$ 条河的时间在 $\left[\dfrac{L_i}{v_i},\dfrac{3\cdot L_i}{v_i}\right)$ 中均匀随机,于是期望就是做个平均数,用线性性加一下就好了。

[经典问题] 多边形

有一根长度为 $1$ 的木棒。随机选 $k$ 个位置切开,求这些小木条能组成一个多边形的概率。

再 放 送。

考虑连成一个圆之后变成了随便选 $k+1$ 个位置。那么考虑拼成一个多边形当且仅当其中最长的那段弧长度严格小于 $\dfrac{1}{2}$ 。那么答案就是

即考虑对弧计数。考虑对于弧的一个端点 $p$ ,有 $k+1$ 种取法,对于其他的点有 $\dfrac{1}{2^k}$ 的概率都在同一侧。对答案取个补即可。

……注意到是不会有弧长度超过 $\dfrac{1}{2}$ 的,这个小细节一开始被自己忽略了。

[UVA10213] How many pieces of Land?

给定一个圆,边界上选 $n$ 个点两两连边,最多能划分出多少个区域。

考虑一种欧神教我的神奇做法。首先不难发现是可以做到不存在三点共线的,并且不共线结果至少不会更劣。那么如果设 $g(i)$ 表示交出的这些区域中 $i $ 边形的个数(只考虑交出来的最小单元),会有

即每条边会产生两次贡献,这 $n$ 个点最后连出的边可以交出 $\binom{n}{4}$ 个交点,每删掉一个交点可以多出两条线段。同时最后交点删干净之后还剩 $\binom{n}{2}$ 条线段,同时为了单独计算相邻点之间的连边要先减去 $n$ 并且最后再加回来。

同时再考虑内角和的贡献。即

其中右边第一项是每个点周围一圈是 $2\pi$ ,第二项是考虑最大的那个 $n$ 边形的内角和。

考虑上面两个式子作差,可以得到

即为答案。