Chrety

数学

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数据结构(14) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

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

P3455 [POI2007]ZAP-Queries(莫比乌斯反演)

题目 P3455 [POI2007]ZAP-Queries 解析莫比乌斯反演。给定\(n\)，\(m\)，\(d\)，求\[\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\] 那我们设\[f(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}[...

莫比乌斯反演数学

2019-04-12

0 536

矩阵基础

矩阵的话还是慢慢来，前面的定义和基本运算很显然，看完定义就会，从矩阵乘法开始就难多了。定义由\(n\times m\)个数\(a_ij\)排成的\(n\)行\(m\)列的矩阵，记为 \[A=\begin{bmatrix} a_{11} & a_{12} & ··· &...

数学矩阵

2019-04-04

0 530

莫比乌斯反演

莫比乌斯函数定义对\(d\)进行质因数分解：\(d=p_1^{r1}p_2^{r2}p_3^{r3}····p_k^{rk}\) \(r=max\{r_1,r_2,r_3···r_k\}\) 莫比乌斯函数的定义为 \[\mu(d) = \begin{cases}1\qquad d=1\\ 0...

数学莫比乌斯反演

2019-04-06

0 482

P2522 [HAOI2011]Problem b (莫比乌斯反演)

题目 P2522 [HAOI2011]Problem b 解析：具体推导过程同P3455 [POI2007]ZAP-Queries 不同的是，这个题求的是\(\sum_{i=a}^b\sum_{j=c}^dgcd(i,j)=k\) 像二维前缀和一样容斥一下，输出就完了。根据luogu某大...

莫比乌斯反演数学

2019-04-13

0 551

HDU 2604 Queuing (矩阵快速幂)

题目 HDU 2604 Queuing 题意：给你一个数\(L\)代表一个队的长度，男女不限，随便排，\(f\)代表女生，\(m\)代表男生，但是其中不能出现\(fmf\),\(fff\) 这种子序列，问一共有多少种排的方法，结果需要\(mod m\). 解析：构思巧妙的一道矩阵快速幂我...

数学矩阵矩阵快速幂算法

2019-04-15

0 480

P2447 [SDOI2010]外星千足虫 (高斯消元)

题目 P2447 [SDOI2010]外星千足虫解析 sol写到自闭，用文字描述描述了半个小时没描述出来，果然还是要好好学语文用高斯消元求解异或方程组。因为 \(奇数\bigoplus奇数=偶数\) \(偶数\bigoplus偶数=偶数\) \(奇数\bigoplus偶数...

数学矩阵高斯消元算法

2019-04-17

0 471

[SDOI2008]仪仗队（欧拉函数）

题目 [SDOI2008]仪仗队解析这个题，我也不知道他们的soltion是怎么写的这么长的。我们发现我们一次看一条直线上的第一个点，也就是说，若两个点斜率\(k=\frac{y}{x}\)相同的话，我们只能看到x，y最小的那个点。然后根据小学数学，\(\frac{x}{y}=\fra...

数学欧拉函数

2019-05-21

0 605

P2613 【模板】有理数取余 (数论)

题目 P2613 【模板】有理数取余解析简单的数论题发现并没有对小数取余这一说，所以我们把原式化一下， \[(c=\frac{a}{b})\equiv a\times b^{-1}(mod\ p)\] 因为\(p\)是质数，所以我们根据费马小定理\(b^{p-1}\equiv 1(mod...

数学数论

2019-05-26

0 711

白兔的式子 (组合)

题目白兔的式子解析 \(\binom{n-1}{m-1}a^{n-m}b^{m-1}\)，发现数据是1e5，所以用阶乘求，至于有理数取余可以看这篇题解代码 #include <bits/stdc++.h> #define int long long using names...

组合数学数学

2019-05-26

0 545

P1349 广义斐波那契数列(矩阵乘法)

题目 P1349 广义斐波那契数列解析把普通的矩阵乘法求斐波那契数列改一改，随便一推就出来了 \[\begin{bmatrix}f_2\\f_1 \end{bmatrix}\begin{bmatrix} p&q\\ 1&0\\ \end{bmatrix}^{n-2}=\be...

矩阵快速幂矩阵数学

2019-07-12

0 599