19-大数据一班-杨文冠

题解

学习(23) 未归档(1) 练习(1)

/ 注册

全部文章 / 题解（共137篇）

E. Pchelyonok and Segments 来自专栏

我们发现k{k}k可以是答案的前提是线段的长度总和不超过n{n}n。即k∗(k+1)2≤n\frac{k*(k+1)}{2}\le n2k∗(k+1)≤n，k≤447k\le 447k≤447 令dpi,jdp_{i,j}dpi,j表示长度为jjj的段的最大和，同时我们已经考虑了后缀iii上所有...

dp

2021-10-27

1 454

D. Frog Traveler 来自专栏

nnn为起点，要跳到地面上，每次向上跳需要比之前里地面更近（假设存在状态i−>j,j<ii->j,j<ii−>j,j<i，如果当前有x−>y,j<y<x<ix->y,j<y<x<ix−>y,j<y<...

2021-10-25

2 533

Korney Korneevich and XOR（F1&F2）来自专栏

求递增子序列所有不同的异或值显然，对于递增子序列x<y<z,ax XOR ay XOR az=Ax<y<z,a_x\ XOR\ a_y\ XOR\ a_z = Ax<y<z,ax XOR ay&nb...

dp 递增子序列

2021-10-25

1 593

CF528D Fuzzy Search 来自专栏

k=0k=0k=0时题目保证只有四个字母"ATGC""ATGC""ATGC"，暗示我们可以先分成4种情况处理，最后加起来。比如说文本串S="TAATGCA"S="TAATGCA"S="T...

NTT

2021-10-23

2 497

P4173 残缺的字符串来自专栏

文本串为A(长度为n)A(长度为n)A(长度为n)，模式串为B(长度为m)B(长度为m)B(长度为m) 不考虑通配符的时候，可以用完全匹配函数可以是P(x)=∑i=0m−1[B(i)−A(x−m+1+i)<mtext> </mtext>]2{P(x)=\sum_{i...

FFT

2021-10-22

1 520

P3375 【模板】KMP字符串匹配来自专栏

A.size()==n>=B.size()==mA.size()==n>=B.size()==mA.size()==n>=B.size()==m 定义完全匹配函数：P(x)=∑i=0m−1[B(i)−A(x−m+1+i) ]2{P(x)=\sum_{i=0}^{m-1}{...

NTT kmp

2021-10-22

1 727

F. Lunar New Year and a Recursive Sequence

，求出最小的满足，不存在输出。有原式可知未知。将用原根表示，从而将乘法变成加法，的原根是，则，可得观察可知，的意义同上。这个式子显然能带入快速幂，快速幂主要是求解出的系数，所以将式子带入后就能求出。所以现在问题就变成了求解已知，直接上模板。 code: #include <bits...

BSGS 矩阵快速幂原根

2021-09-17

1 466

261. Discrete Roots

求出的所有解。找到一个特解因为是质数，所以可以求出的质数。因此对于模意义下的任意数有且仅有一个数满足。假设，则，稍加变换，有：然后套用就一定能求出，然后得到原方程的一个特解找到所有解则，对上面的式子，显然有，设，则有 code: #include <bits/stdc++...

BSGS 原根

2021-09-16

1 597

P2485 [SDOI2011]计算器

对于第一个任务，上快速幂。对于第二个任务，因为是质数，就不需要扩展欧几里得求逆元了，直接快速幂求逆元。对于第三给任务，上。原式：，则，枚举，然后用存起来：。接着从小到大枚举，如果，那么最小的。 #include <bits/stdc++.h> using namespace...

BSGS

2021-09-15

1 515

P4195 【模板】扩展 BSGS/exBSGS

求解：，不一定互质。如果，则存在逆元，直接使用求解。具体的，假设，如果，方程无解。否则，方程同时除以：直到记，于是方程变成：套时，没必要计算出的逆元然后挪到等式右边，只需要在枚举时查找是否存在即可。注意，不排除小于等于的情况，也就是可能说在还没有达到时就有解了，这个需要特判。这题卡...

BSGS

2021-09-15

1 449