降维打击雪崩效应走火入魔呕吐致死死期将至四条命真假 BOSS 打个鬼以火制火（续上图）连升四级装备致死《礼品卡》去凋...

Yurchiu 2022-03-20, 14:34:58

这里介绍的是高斯-约旦消元法。相对于传统的高斯消元，约旦消元法的精度更高、代码更简单，没有回带的过程。约旦消元法大致思路如下：选择一个尚未被选过的未知数作为主元，选择一个包含这个主元的方程。将这个方程主元的系数化为 1。通过加减消元，消掉其它方程中的这个未知数。重复以上步骤，直到...

Yurchiu 2022-02-26, 22:03:02

Matrix 例题

矩阵 $\LaTeX$ ：

\begin{bmatrix}
1 & 1 & 4 \\\\
5 & 1 & 4
\end{bmatrix}

P1962 斐波那契数列

题意

求斐波那契数列第 $n$ 项，对 $10^9+7$ 取模。 $1\le n\le2^{63}$ 。

点击查看题解

题解

构造矩阵 $A=\begin{bmatrix}1 & 1\\\\1 & 0\end{bmatrix}$ ， $B=\begin{bmatrix}f_2 & f_1\end{bmatrix}$ 。则有：

\begin{aligned} BA&=\begin{bmatrix}f_2+f_1 & f_2\end{bmatrix}=\begin{bmatrix}f_3 & f_2\end{bmatrix} \\\\ BA^2&=\begin{bmatrix}f_3+f_2 & f_3\end{bmatrix}=\begin{bmatrix}f_4 & f_3\end{bmatrix} \\\\ BA^{n-2}&=\begin{bmatrix}f_{n-1}+f_{n-2} & f_{n-1}\end{bmatrix}=\begin{bmatrix}f_n & f_{n-1}\end{bmatrix} \end{aligned}

因为结合律，可得：

BA^k=B(A^k)

矩阵快速幂求之。

可见，矩阵加速递推的关键就在矩阵的构造。之后的题解，递推矩阵都会以注释的形式出现在代码中。

代码

下面的代码中，结构体 Matrix 的定义参加文章“Matrix”。

#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
	typedef long long ll;
	const ll N=200+10,mod=1000000007;
	ll n,init[]={1,1,1,0},ans;
	Matrix A(2,init);
	void main()
	{
		scanf("%lld",&n);
		if(n<=2){printf("1");return;}
		A^=n-2; ans=A.M[1][1]+A.M[2][1];
		printf("%lld\n",ans%mod);
		return;
	}
}
int main()
{
	_yz::main();
	return 0;
}
/*
|1,1|
|1,0| x |f1,f2| = |f1+f2,f2|
*/

Yurchiu 2022-02-26, 17:24:30

Matrix

在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合，最早来自于方程组的系数及常数所构成的方阵。这一概念由 19 世纪英国数学家凯利首先提出。

由 $mn$ 个数 $a_{ij}$ 排成的 $m$ 行 $n$ 列的数表称为 $m$ 行 $n$ 列的矩阵。

A= \begin{bmatrix} a_{11} & a_{12} & a_{13} & \cdots & a_{1n}\\\\ a_{21} & a_{22} & a_{23} & \cdots & a_{2n}\\\\ a_{31} & a_{32} & a_{33} & \cdots & a_{3n}\\\\ \vdots & \vdots & \vdots & \ddots & \vdots\\\\ a_{m1} & a_{m2} & a_{m3} & \cdots & a_{mn} \end{bmatrix}

Yurchiu 2022-02-15, 23:24:29

BSGS 与 exBSGS

Baby-Step-Giant-Step（大步小步法，~~北上广深~~，~~不是个事~~，~~拔山盖世~~），简称 BSGS，使用分块思想解决离散对数问题。

形如 $a^b \equiv c \pmod m$ 的同余式，可产生以下三种问题：

已知 $a,b$ ，求 $c$ ，是快速幂问题。
已知 $a,c$ ，求 $b$ ，是离散对数问题。
已知 $b,c$ ，求 $a$ ，是高次剩余问题。

Yurchiu 2022-02-02, 23:04:48

Markdown Test

This post is originated from here and is used for testing markdown style. This post contains nearly every markdown usage. Make sure all the markdown elements below show up correctly.

Hexo 2022-02-02, 16:56:53

扩展欧拉定理及其证明

若 $b\ge\varphi(m)$ ，则有：

\Large a^b\equiv a^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

$\LaTeX$ ：\Large a^b\equiv a^{b\text{ mod }\varphi(m)+\varphi(m)}\pmod m

下面来证明这一式子。

显然，若 $m=1$ ，式子成立。下面的证明只讨论 $m>1$ 。

Yurchiu 2022-02-02, 15:03:53

一些数论证明或杂论-2

本文是“一些”系列的最后一篇。

本文内容：费马小定理及其证明，【题目】因子和，裴蜀定理，德摩根定理，欧拉定理及其证明，威尔逊定理。

费马小定理及其证明

对于整数 $a$ 和质数 $p$ ，若 $(a,p)=1$ ，则有：

a^{p-1}\equiv1\pmod p

注： $(a,p)$ 指 $a$ 和 $p$ 的最大公约数。

Yurchiu 2022-01-07, 22:49:13

一些数论证明或杂论

本文内容：同余，剩余类，完全剩余系，同余最短路，乘法逆元，笛卡尔积，既约剩余系，完全余数集合，欧拉函数及其性质，Lucas 定理。

本文及以后所设的字母，若无特殊约定，均为整数或正整数。

同余

若两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被正整数 $m$ 整除，即 $m\mid a-b$ ，那么就称整数 $a$ 与 $b$ 对模 $m$ 同余，记作

a \equiv b \pmod m

$\LaTeX$ ：a \equiv b \pmod m。

如果它们都是正数，那么上面的式子等价于 $a$ 与 $b$ 分别用 $m$ 去除，余数相同。

举例：

7^7 \equiv 2023 \pmod{7!}

Yurchiu 2022-01-07, 22:02:53

希腊字母

学习数论，首先需要学习奇奇怪怪的希腊字母（雾）

本文列举各种希腊字母的读音与 $\LaTeX$ 命令。

Yurchiu 2022-01-07, 20:52:44

一个 4 人囚徒困境的必胜策略

zzy 云，要把他的题解放到我的 Blog 上，于是这篇文章出现了。下面是原文。

zzy 2022-01-01, 12:38:12

数论模板

原写作日期：2019-08-24 11:30:21。重置，时间放后 2 年 4 个月。

快速幂

以下以求 $a$ 的 $11$ 次方来介绍。把 $11$ 转换成二进制数 $1011_{(2)}$ 。设其第 $i$ 位的权为 $ 2^{i-1} $。因此，我们将 $a^{11}$ 转化为算 $a^{2^0}+a^{2^1}+a^{2^3}$ 。

ll qpow(ll a,ll p,ll m)
{
    ll r=1;
    while(p)
    {
        r=(p%2?r*a:r)%m;
        p/=2; a=a*a%m;
    }
    return r%m;
}

Yurchiu 2021-12-24, 11:30:21

NOIP-2021 有感

这次 NOIP，是我很失败的一次比赛。相差 2 分，即可一等奖。我仍然是第一名，山东省二等奖第一名。这第一名来的憋屈。

因为是比赛当年后的第二年的游记，细枝末节之事已淡出脑海，故改为有感。

Yurchiu 2021-12-09, 22:47:10

套题 I 题解

本文为题解集。为 Yurchiu 所参加的模拟赛题目。 A factory 题意给出一个长度为 nnn 的正整数序列 aaa。定义一个“家族”为：是序列 aaa 中连续的一段；若 aia_iai 和 aja_jaj 属于同一个家族（i<ji<ji<j），则 ...

Yurchiu 2021-11-27, 10:43:34

CSP-S1&2 of 2021 游记

CSP-S1&2 of 2021 游记：CSP-S 爆零退役记。

Yurchiu 2021-10-29, 23:18:15

«1 234 5…11 »

By Yurchiu.

Yurchiu's Blog

P1962 斐波那契数列

题意

题解

代码

费马小定理及其证明

同余

快速幂

NOIP-2021 有感

CSP-S1&2 of 2021 游记