rprp

数学

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

/ 注册

全部文章 / 数学（共6篇）

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 483

数学小算法

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 412

AT1983 [AGC001E] BBQ Hard

前言学到了一个\(trick\)。对于一个组合数 \(C_{x+y}^x\)可以看成是从\((0,0)\)到\((x,y)\)的路径条数。解法对于这题而言，\(C_{a_i+b_i+a_j+b_j}^{a_i+a_j}\)就表示从点\((0,0)\)到点\((a_i+a_j,b_i+b...

妙啊数学动态规划

2020-05-14

0 524

FFT板子

#include <cmath> #include <cstdio> #include <vector> #include <cstring> #include <algorithm> using namespace std; #def...

FFT 多项式

2020-05-11

0 390

斐波那契数列简单性质

计数性质 \(F_i=F_{i-1}+F_{i-2}\) \(\sum^{n}_{i=1}F_i=F_{n+2}-F_2\) 证明：当\(n=1\)时，\(F_3-F_2=F_1\)显然成立。当\(n=2\)时，\(F_4-F_2=F_3+F_2-...

斐波那契数列

2020-05-05

0 405

二项式反演学习笔记

前置知识容斥原理组合数约定 \(A'_i\)表示集合\(A_i\)的补集。反演形式形式一 \[f(n)=\sum_{i=0}^{n}(-1)^iC^i_ng(i)\Leftrightarrow g(n)=\sum_{i=0}^{n}(-1)^iC^i_nf(...

二项式反演

2020-05-03

0 471