2020-2021:teams:farmer_john:2020hdu暑期多校第一场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020hdu暑期多校第一场 [2020/07/24 14:25] 2sozx [记录] |
2020-2021:teams:farmer_john:2020hdu暑期多校第一场 [2020/10/07 21:23] (当前版本) jjleo |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ======2020hdu暑期多校第一场====== | + | ======2020HDU暑期多校第一场====== |
| [[https://codeforces.com/contestInvitation/377448d2c4fe386ab80df2e4d6f6ea0ef6fcb105|比赛链接]] | [[https://codeforces.com/contestInvitation/377448d2c4fe386ab80df2e4d6f6ea0ef6fcb105|比赛链接]] | ||
| =====A.===== | =====A.===== | ||
| 行 31: | 行 31: | ||
| 给定 $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$ | 给定 $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$ 的情况。 | + | 斐波那契数列通项公式 $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}^{k}(-1)^{(k-i)}C(k,i)\sum_{j=0}^{N}a^{jci}b^{jc(k-i)}$$ 对于后面的求和显然可以通过等比数列求和公式计算，因此我们只需枚举 $i=0\sim k$ 即可，注意特判公比为 $1$ 的情况。 |
| =====F.===== | =====F.===== | ||
| - | **upsolved by ** | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | $n$个点$m$条边的无向图，每个点有一个权值，$q$次操作，每次更改一个点权值，或询问与一个点相邻所有点权值组成集合的$\operatorname{mex}$。$(n,m,q \le 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| + | 将度数$\ge \sqrt{n}$的节点称为大节点，其它节点称作小节点。对于每个大节点开一个其对应度数大小的树状数组用于统计$\operatorname{mex}$（当然还需要一个相同大小的数组记录每个元素的出现次数）。当每个节点权值发生改变时，只需更改相邻的大节点。询问时，大节点直接用树状数组求$\operatorname{mex}$即可，小节点直接将相邻节点权值暴力排序求即可。 | ||
| =====G.===== | =====G.===== | ||
| **upsolved by** | **upsolved by** | ||
| 行 49: | 行 51: | ||
| =====I.===== | =====I.===== | ||
| - | **solved by ** | + | **upsolved by ** |
| ====题意==== | ====题意==== | ||
| 行 60: | 行 62: | ||
| ====题解==== | ====题解==== | ||
| =====K.===== | =====K.===== | ||
| - | **upsolved by ** | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 求字符串每个前缀的最小后缀，多组数据。$\sum|s| \le 2 \times 10^7$ | ||
| ====题解==== | ====题解==== | ||
| + | 对字符串进行Lyndon分解，考虑在Duval算法中三个下标的含义：$i$为$s_2$开头，$j$为$s_3$开头，$k$为当前考虑和$j$匹配的位置。如果$s[k]=s[j]$，说明$s[k \cdots j]$作为Lyndon串的一个循环同构，最小后缀不会出现在其中，只需将$k$对应的最下后缀下标进行位移即可，即此时最小后缀的下标$pos[j]=pos[k]+j-k$；如果$s[k]<s[j]$，此时$s[i \cdots j]$构成一个Lyndon串，因此$pos[j]=i$。另外，每次$i$变化后，可以得到$pos[i]=i$。进行上述三种维护即可。 | ||
| =====L.===== | =====L.===== | ||
| **solved by Bazoka13** | **solved by Bazoka13** | ||
| 行 84: | 行 87: | ||
| =====总结===== | =====总结===== | ||
| * csk:这就是North Korea的题🐎，出了一道几何就做不动了，K题想到Lyndon但是没想到做法，这种平常没怎么见过的还是要补补 | * csk:这就是North Korea的题🐎，出了一道几何就做不动了，K题想到Lyndon但是没想到做法，这种平常没怎么见过的还是要补补 | ||
| + | * MJX:这是MJX犯病的第二天，真就疯狂出问题。 | ||
| + | * ZYF:这是ZYF划水的第一天，看来最近太摸鱼了。 | ||
2020-2021/teams/farmer_john/2020hdu暑期多校第一场.1595571949.txt.gz · 最后更改: 2020/07/24 14:25 由 2sozx
