Codeforces #566 Div.2 小结

比赛链接:Codeforces #566 Div.2

A – Filling Shapes

每个$3 \times 2$的区域有两种填充方式,当$n$为偶数时,答案为$2^{\frac{n}{2}}$,$n$为奇数时,不存在填充方案。

B – Plus from Picture

枚举十字架的中心,然后向四个方向探测,统计字符$*$的数量。当一个中心所在的十字架内的$*$等于全部$*$的数量时,答案为YES,否则为NO。

C – Beautiful Lyrics

我们把题目中的条件分成两类

  • 强条件:$s_1$和$s_2$包含的元音数量相同,并且最后一个元音字母相同
  • 若条件:$s_1$和$s_2$包含的元音数量相同,并且最后一个元音字母不同

可以先按照元音数量和最后一个字母为关键字,对原序列进行排序,然后先对强条件进行两两匹配(我们知道满足强条件的一对分别放在第一行第二个和第二行第二个),匹配完之后删去或者标记为已使用,统计匹配对数,记为$c_1$;接下来从没有使用的元素集合当中两两匹配弱条件,统计匹配对数,记为$c_2$。

  • $c_1 < c2$时,答案为$c_1$,为所有的强条件匹配弱条件即可
  • $c_1 \geq c_2$时,答案为$c_2 + \lfloor \frac{c_1 – c_2}{2} \rfloor$,$c_2$表示给弱条件一一匹配强条件,$\lfloor \frac{c_1 – c_2}{2} \rfloor$表示在剩下的没有使用的强条件中进行两两匹配

E – Product Oriented Recurrence

观察到$f(n)$一定可以表示成

$$ f(n) = f(1)^\alpha  f(2)^\beta  f(3) ^\gamma c^\theta $$

一开始我想用矩阵快速幂求出四个指数,后来发现$f(1)$、$f(2)$、$f(3)$的指数是齐次线性递推,而$c$的指数是非齐次线性递推,所以是不可行的。

我们可以这样构造

$$f(n) = c^{2n – 6} f(n – 1)f(n – 2)f(n – 3) \Rightarrow c^n f(n) = c^{n – 1}f(n – 1) c^{n – 2} f(n – 2) c^{n – 3} f(n – 3)$$

令$g(n) = c^n f(n)$,则

$$ g(n) = g(n – 1)g(n – 2)g(n – 3) $$

这样就可以使用矩阵快速幂算指数了,这里要使用降幂公式

$$ a^b \equiv a^{b \bmod \varphi(p)} \pmod{p} $$

注意最终算到了$g(n)$要得到$f(n)$还需要乘上$c^n$在模$p$意义下的逆元。

 

说点什么

avatar
50
  Subscribe  
提醒