比赛链接

upsolved by

upsolved by

upsolved by

solved by 2sozx Bazoka13 JJLeo

统计多少个长度为 $n$ 的由小写字母构成的串 $S$ 的回文子串数最少。

$n\le3$ 答案为 $26^n$ ；$n>3$ 答案为 $A(26,3)$.

$n\le3$ 时显然。$n>3$ 时可以构造 $abcabc\cdots$ 这样回文子串个数仅有三个，答案即为 $A(26,3)$

solved by 2sozx JJLeo

给定 $N,C,k$ 求 $F_0^k+F_{C}^k+F_{2C}^k+\cdots+F_{NC}^k(mod 10^9+9)$，其中 $F$ 为斐波那契数列。 $N,C\le10^{18},k\le10^5$

斐波那契数列通项公式 $F_i=\frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i)$ ，且 $5$ 是 $10^9+9$的二次剩余，因此我们可以预处理出来 $x=\frac{1}{\sqrt{5}},a=\frac{1+\sqrt{5}}{2},b=\frac{1-\sqrt{5}}{2}$，对于所求的式子可以通过二项式展开来求 $$S=x^k\sum_{i=0}^{n}(-1)^{(k-i)}C(k,i)\sum_{j=0}^{N}a^{jci}b^{jc(k-i)}$$ 对于后面的求和显然可以通过等比数列求和公式计算，因此我们只需枚举 $i=0\sim k$ 即可，注意特判公比为 $1$ 的情况。

upsolved by

upsolved by

upsolved by

solved by

upsolved by

upsolved by

solved by Bazoka13

给一个凸多边形花园，手动除草需要费用$A$，用圆形除草机费用$B$,使用除草机要确保圆始终在多边形内部，求最小费用。

显然如果$A \leq B$的话可以直接手动除草，否则就把每条边向内垂直移动圆的半径的长度，求一个半平面交，没有交说明只能手动，有交就求出来交的面积$+$交的周长$*$圆的半径$+$圆的面积，手动面积用总面积减一下即可。

-???min：听说这场题巨恶心
0min：分题看题
10+min：一起看D发现有规律，MJX冲D
18min：MJX WA
20min：MJX 发现输出格式出大问题，AC，MJX ZYF看 I
40+min：MJX冲I
53min：MJX WA2 后AC，ZYF 看K可做
81min：ZYF WA，CSK 看 L发现可做冲L
107min：CSK AC L，MJX ZYF开始疯狂冲E
290min：发现爆long long ，改用 __int128，开始CE
298min：WA n 后终于过了E

• csk:这就是North Korea的题🐎，出了一道几何就做不动了，K题想到Lyndon但是没想到做法，这种平常没怎么见过的还是要补补