owcoder题解牛客网赛前集训营普及组（第二场）

啊...表示一大早还没睡醒就开始打比赛(开始前一分钟的我还在桌子上趴着休眠)...表示题目思路清奇(尤其C题)...但是我还是太蒻了...\(D\)题暴力都没打...题解正式开始之前先\(\%\)一下\(\color{#FF6161}{风浔凌}\)巨佬\(qwq\)...\(320\)真是太强了\(\%\%\%\)...

\(A\) 你好诶加币题目描述:就是简单的\(a+b\)啊(逃)题目本质:数据范围是\(long\ long\)的\(a+b\)啊(逃)思路:显然不可能直接算啊...所以并不可解(逃)详解:非常显然爆\(long\ long\)的情况只有在\(a,b\)同号时才会出现,所以考虑按照\(a,b\)的符号来分类

\(AC\)代码:

\(B\) 最后一次题目描述:求不超过\(n(n\in[2,10^{12}])\)的最大质数题目本质:就是求不超过\(n\)的最大质数啊(逃)思路:看到数据范围之后显然不能直接算啊...所以并不可解(逃)详解:考虑到质数的分布密度,可以从\(n\)开始倒序查找,复杂度大概在\(O(logn\cdot \sqrt{n})\)...(口胡)

\(AC\)代码:

\(C\) 选择颜色题目描述:求一个长度为\(n(n\in[3,10^9])\)的有序环用\(c(c\in[3,100])\)种颜色染色,相邻颜色不相同的染色方式有多少种题目本质:小学组合数学题(逃)思路:如果是一条链不成环就非常容易...乘法原理就能解决...然而成环嘛...并不可解(逃)详解:从简单的情况开始考虑,如果是一条链不成环那么结果显然是\(c\cdot (c-1)^{n-1}\),而成环之后的合法方式显然比不成环时少,少的部分是链染色方式中首尾颜色相同的部分,所以可以考虑用链方式数减链成环后不合法的方式数求出环合法染色方式数,此时问题就在于求链染色方式中首尾相同的方式数,此时问题可以转化为一个由\(n\)个点组成的无自环的无向完全图中长度为\(n-1\)的路径数,此时设\(f_{ij}\)表示从\(1\)出发到达\(j\)的长为\(i\)的路径条数,此时不难发现\(f_{i\ j}=\sum_{k=1}^{c}f_{i-1\ k}-f_{i-1\ j}\),据此可以考虑用矩阵快速幂完成线性递推求\(f_{n-1\ j}\),则有\(f_1\)矩阵$$\begin{vmatrix}f_{1\ 1}\f_{1\ 2}\f_{1\ 3}\\vdots\f_{1\ c}\end{vmatrix}=\begin{vmatrix}0\1\1\\vdots\1\end{vmatrix}$$基底矩阵为$$base=\begin{vmatrix}0&1&1&\cdots&1\1&0&1&\cdots&1\1&1&0&\cdots&1\\vdots&\vdots&\vdots&\ddots&\vdots\1&1&1&\cdots&0\end{vmatrix}$$则可求出从\(1\)出发到\(1\)路径长为\(n-1\)的路径条数\(f_{n-1\ 1}=f_{1\ 1}\times base^{n-2}\),同理可得不合法方式的总数为\(c\times f_{1\ 1}\times base^{n-2}\),故答案为\(c\times [(c-1)^{n-1}-f_{1\ 1}\times base^{n-2}]\),此时采用快速幂和矩阵加速求解即可

\(AC\)代码:

\(D\) 合法括号序列\(\color{#55ACEE}{表示这题还没过...暂且咕着qwq}\)