rprp

分类

动态规划(12) 图论(6) 字符串(3) 搜索(1) 数学(6) 数据结构(18) 未归档(2) 贪心(5) 配置(2)

/ 注册

TA的专栏 1篇文章 0人订阅

1篇文章 687人学习

全部文章（共55篇）

SP5971 【LCMSUM - LCM Sum】

lei/ \[\sum^n_{i = 1} lcm(i,n)=\sum^{n}_{i=1}\frac{in}{gcd(i, n)}= \] \[\sum^{n}_{d|n}\sum^{n}_{i=1}\frac{in}{d}[gcd(i,n)==d]= \] \[n \t...

莫比乌斯反演

2020-07-28

0 507

数学小算法

exgcd \[x = y \ \\ y = t - a /b \times y \] CRT \[ans = \sum_{i = 1}^n{b_i\times M_i\times inv(M_i,mod_i)} \] \[M_k=(\prod_{i=1}^n {} m...

CRT exgcd BSGS

2020-07-25

0 441

PAM

struct PAM { int ch[N][26], fail[N], len[N]; int tot, las; PAM() { len[0] = 0; len[1] = -1; fail[0] = 1; tot = 1; las = 0; } inline int gtfail(...

PAM

2020-07-23

0 379

SAM模板

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define R register #define LL long long const int i...

SAM

2020-07-22

0 371

一个写得很*****的differ

#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cstdlib> #include <string> ...

differ

2020-06-17

0 438

LCT板子

#define ls(x) ch[x][0] #define rs(x) ch[x][1] int fa[N], ch[N][2], sum[N], val[N], rev[N]; inline void update(int x) { sum[x] = sum[ls(x)] ^ sum[rs(x)...

Link-Cut-Tree

2020-06-16

0 362

[wqs二分模板] CF739E Gosha is hunting

题目链接首先一个很显然的想法就是直接\(DP\) 设\(f[i][j][k]\)表示抓前\(i\)个神奇宝贝用了\(j\)个宝贝球和\(k\)个超级球，有： \[f[i][j][k] = max (f[i - 1][j - 1][k] + p[i], f[i - 1][j][k - 1]...

期望ＤＰ wqs二分

2020-06-10

0 392

高精度板子

//#include<bits/stdc++.h> #include<iostream> #include<iomanip> #include<cstring> #include<stack> #include<string> ...

高精度

2020-06-09

0 374

斜率优化DP刷题单

Luogu P3195 [HNOI2008]玩具装箱 Luogu P2900 [USACO08MAR]Land Acquisition G Luogu P5785 [SDOI2012]任务安排 Luogu P4360 [CEOI2004]锯木厂选址 Luogu P2120 [ZJOI2007]仓库建...

斜率优化

2020-06-07

0 377

「JOISC 2016 Day 3」回转寿司

「JOISC 2016 Day 3」回转寿司这题我无力吐槽了... 强烈谴责出题人用脚造数据解法其实这题主要还是部分分启发正解吧。看到有个\(s_i = 1, t_i= n\)的做法就是维护一个堆就可以了，所以扩展下就是分块，然后每个块维护一个堆。散块暴力，大块直接查。但是有个很坑爹的问题...

堆

2020-05-18

0 747