用 Astro 搭建一个高性能博客
import Info from "../../components/mdx/Info.astro"; import Error from "../../components/mdx/Error.astro"; import Warning from "../../components/mdx/Warning.astro"; import Success from "../../components/mdx/Success.astro";
前言
为什么选择 Astro
关于这个问题，你可以访问它的官方网站：为什么是 Astro? | Docs
如果你想了解我的想法，请移动至本文结尾
需要的环境
● 为了让 Astro 在你的系统上运行，你需要安装 Node.js、版本
● [可选] 安装 pnpm：
我还需要什么
● 一个 GitHub 账号
● 一个合适的代码编辑器
● 掌握一定的 魔法-Magic
创建你的博客项目
{" "} Astro 不像 Hexo，可以安装多个主题，然后只用写几个配置文件就好了——还能随便切换主题。Astro 每个主题就是一个项目，而每位作者用的 `frontmatter` 格式可能都不一样，所以为了避免频繁迁移项目，请先选好自己要使用的主题。{" "}
选择你需要的主题
Astro 像 Hexo 一样，也有很多主题可用（更好的说法是项目模板）。你可以在 Themes | Astro 挑选自己需要的主题，这里我选择简单好用的 AstroPaper 作为示例。
拷贝主题 / 项目模板（仓库）
只需要使用包管理器即可（推荐使用 pnpm）：
完成后的目录如下：
安装必要的内容：
如果你迫不及待想看看自己的博客，可以启动 Astro 开发服务：
你应该能在终端中看到 Astro 正在以开发模式运行的提示信息。
在浏览器中输入
个性化你的博客
config.ts
里面包含了网站的一些基本信息，下面是 AstroPaper 的
新文章
下面是 AstroPaper 的
部署你的博客项目
随便找一个托管平台部署即可，这里使用
将你的项目托管至 GitHub
这个不用多说了吧：
托管 Vercel
1. 进入 Vercel 然后注册一个账号；
2. 新建一个项目；
3. 选择你刚刚创建的仓库（这里拿之前的举例子）；
4. 点击
5. 看到满屏的烟花了吗？你成功了！
可能遇到的问题
1. 克隆项目时报错了： 这可能是 npm 镜像的问题，推荐使用官方镜像 + 使用魔法。
1. 项目自己就报错了： 因为 Astro 的博客就是一个独立的项目： 所以这个很难有一个通用的解法，下面是可能的问题： ● 启用了作者的实验性内容（我就遇到过）； ● 文章格式不符合项目要求或者文件路径错误； ● ……
2. 本地没问题，部署报错了： 看看
3. 其他（待添加）
尾声——我为什么选择 Astro
搭建个人博客有很多种途径，作者本人（我）曾在此吃了不少苦头。刚开始我买了云服务器准备使用 WordPress 搭建网站，结果发现这对服务器的要求太高了，WP 还会出一些奇怪的 BUG （比如某一个重要 .js 突然祭了，就写不了文章了）。于是乎，我找到了成本更低也更快捷的方法——Hexo。它拥有庞大的社区，解决方案也很成熟，很适合我这种没有基础的小白。问题就是，单从我个人体验来说，Hexo 并不像它简介说的一样快速，它太臃肿了，尤其是对于某些主题来说，东西太多太杂，资源浪费严重。如果你曾使用PageSpeed Insights (web.dev)测试过 Hexo 站点，会发现它真的慢……
下面是用 Butterfly 搭建的一个 Hexo 站点，仅有两篇文章：
我的老博客：
更不用说其他的了……
而下面是我现在的博客：
就我个人而言，Astro 是一个优于 Hexo 的替代品，那么我为什么不用 Astro 呢？
via サン猫の時間漂流
Invalid media:
image
image
image
image
image
image
image
import Info from "../../components/mdx/Info.astro"; import Error from "../../components/mdx/Error.astro"; import Warning from "../../components/mdx/Warning.astro"; import Success from "../../components/mdx/Success.astro";
前言
本篇文章的目的旨在读者无须在多个窗口间跳动即可完成 Astro 的部署与个性化。需要下载的内容可在本页面一键下载
为什么选择 Astro
关于这个问题，你可以访问它的官方网站：为什么是 Astro? | Docs
如果你想了解我的想法，请移动至本文结尾
需要的环境
● 为了让 Astro 在你的系统上运行，你需要安装 Node.js、版本
v18.14.1 或更高版本。点击下载： node-v20.11.1-x64
● [可选] 安装 pnpm：
npm install -g pnpm
我还需要什么
● 一个 GitHub 账号
● 一个合适的代码编辑器
● 掌握一定的 魔法-Magic
创建你的博客项目
{" "} Astro 不像 Hexo，可以安装多个主题，然后只用写几个配置文件就好了——还能随便切换主题。Astro 每个主题就是一个项目，而每位作者用的 `frontmatter` 格式可能都不一样，所以为了避免频繁迁移项目，请先选好自己要使用的主题。{" "}
选择你需要的主题
Astro 像 Hexo 一样，也有很多主题可用（更好的说法是项目模板）。你可以在 Themes | Astro 挑选自己需要的主题，这里我选择简单好用的 AstroPaper 作为示例。
拷贝主题 / 项目模板（仓库）
只需要使用包管理器即可（推荐使用 pnpm）：
# npm 6.x
npm create astro@latest --template satnaing/astro-paper
# npm 7+, extra double-dash is needed:
npm create astro@latest -- --template satnaing/astro-paper
# yarn
yarn create astro --template satnaing/astro-paper
完成后的目录如下：
/
├── public/
│ ├── assets/
│ │ └── logo.svg
│ │ └── logo.png
│ └── favicon.svg
│ └── astropaper-og.jpg
│ └── robots.txt
│ └── toggle-theme.js
├── src/
│ ├── assets/
│ │ └── socialIcons.ts
│ ├── components/
│ ├── content/
│ │ | blog/
│ │ | └── some-blog-posts.md
│ │ └── config.ts
│ ├── layouts/
│ └── pages/
│ └── styles/
│ └── utils/
│ └── config.ts
│ └── types.ts
└── package.json
安装必要的内容：
npm installl
如果你迫不及待想看看自己的博客，可以启动 Astro 开发服务：
npm run dev
你应该能在终端中看到 Astro 正在以开发模式运行的提示信息。
在浏览器中输入
http://localhost:4321/ 即可即时预览。个性化你的博客
config.ts
里面包含了网站的一些基本信息，下面是 AstroPaper 的
config.ts：// file: src/config.ts
export const SITE = {
website: "https://astro-paper.pages.dev/",
author: "Sat Naing",
desc: "A minimal, responsive and SEO-friendly Astro blog theme.",
title: "AstroPaper",
ogImage: "astropaper-og.jpg",
lightAndDarkMode: true,
postPerPage: 3,
scheduledPostMargin: 15 * 60 * 1000, // 15 minutes
};
新文章
blog/ 文件夹中放的就是你的文章，用一般的 MarkDown 格式编写即可，注意里面的 frontmatter，不同的主题可能有不同的 frontmatter 规则，详见主题仓库的 README.md。下面是 AstroPaper 的
frontmatter 规则：部署你的博客项目
随便找一个托管平台部署即可，这里使用
Vercel 。将你的项目托管至 GitHub
这个不用多说了吧：
git init
git add README.md
git commit -m "first commit"
git branch -M main
git remote add origin 你的仓库地址
git push -u origin main
托管 Vercel
1. 进入 Vercel 然后注册一个账号；
2. 新建一个项目；
3. 选择你刚刚创建的仓库（这里拿之前的举例子）；
4. 点击
Deploy；5. 看到满屏的烟花了吗？你成功了！
可能遇到的问题
1. 克隆项目时报错了： 这可能是 npm 镜像的问题，推荐使用官方镜像 + 使用魔法。
博主之前就是用了其他镜像导致祭了。
npm config set registry https://registry.npmjs.org/
1. 项目自己就报错了： 因为 Astro 的博客就是一个独立的项目： 所以这个很难有一个通用的解法，下面是可能的问题： ● 启用了作者的实验性内容（我就遇到过）； ● 文章格式不符合项目要求或者文件路径错误； ● ……
2. 本地没问题，部署报错了： 看看
pnpm-lock.yaml 和 package.json 有没有问题。3. 其他（待添加）
尾声——我为什么选择 Astro
搭建个人博客有很多种途径，作者本人（我）曾在此吃了不少苦头。刚开始我买了云服务器准备使用 WordPress 搭建网站，结果发现这对服务器的要求太高了，WP 还会出一些奇怪的 BUG （比如某一个重要 .js 突然祭了，就写不了文章了）。于是乎，我找到了成本更低也更快捷的方法——Hexo。它拥有庞大的社区，解决方案也很成熟，很适合我这种没有基础的小白。问题就是，单从我个人体验来说，Hexo 并不像它简介说的一样快速，它太臃肿了，尤其是对于某些主题来说，东西太多太杂，资源浪费严重。如果你曾使用PageSpeed Insights (web.dev)测试过 Hexo 站点，会发现它真的慢……
下面是用 Butterfly 搭建的一个 Hexo 站点，仅有两篇文章：
我的老博客：
更不用说其他的了……
而下面是我现在的博客：
就我个人而言，Astro 是一个优于 Hexo 的替代品，那么我为什么不用 Astro 呢？
via サン猫の時間漂流
Invalid media:
image
image
image
image
image
image
image
清楚？明白？
----------------------
----------------------
----------------------
坚信客观事实，不加主观修饰
我在我们班里总看见一类人：他们每天唯一的生活好像只有做作业了——自习课做作业；上主副课做作业；下课做作业；午休做作业；竞赛做作业；就连晚上寝室里面也开个手电筒做作业……问题是，往往每天晚自习下课说做不完作业的人，刚好就是同一批人。我于是陷入了沉思：兄弟，你已经废了这么多功夫做作业了，你怎么还是做不完啊！？
这类人是很擅长自我安慰的：我已经这么努力了……（别人就不会说我了吧） 如此这般，往往会形成滚雪球的情景：今天任务没完成，留到明天；明天又没有完成，继续拖……最后拖到回家，家里则奋笔疾书继续补，嗯，这样一个星期的轮回就完成了。
别说做作业了，做别的事情也是一样的。这种行为毫无疑义是有问题存在的，可是你又说不得他们：你有他们认真吗？你看过他们的笔记、错题本吗？你看过他们挑灯夜读的样子吗？你自己又是什么样的呢……可惜事实不会骗人，他们往往是成绩吊车尾的几个，虽然全段不差，但是在提前班着实是不够看的层面。
我看过他们的样子，也看过他们的笔记、错题本。说实话，我是真的为他们心痛，有如此精力却不愿意花时间整理反思，这样浪费时间，最后又获得了什么呢？
这也不能算是假努力，但这结果往往比假努力更为糟糕。假努力是你自己清楚的，是有问题的，但是这种情况给自己铺设了一条后路：我已经很努力了。 于是人就会
因为我们没有明确客观事实的因果关系。
我不需要知道你是怎么怎么想的，不考虑你到底是为了什么也要这样做。我只需要明确一个
我知道这很残酷，尤其是对于那些人来说。但，这就是事实，这是不能改变的。不是别人的学习方法拿来一用就好的，不是每天埋头做作业就好的。如果发现实际与设想有偏差，就应该立足于实际，而不是用设想麻痹自己！
----------------------
清楚想要什么，明白改变什么
经典问题之一：什么是学习？什么能算学习？学习的定义是什么？
你也许会说，这是一个没有答案的问题，或者说出自己的见解。两种都可以接受，但是关键不是这个问题的答案，关键是你有没有一条可以说服自己并且可以致用的
经典问题之二：你学习是为了什么。
为了什么？不同的人会有不同的答案——这很正常。但是如果我过一会再问你呢？几天后？一个月后？你的答案会与第一次相同吗？这很难吧……毕竟就我自己而言，也不能找到一条终身侍奉的真理来指引我，所以我现在仍然不得不面对这个问题，并且加以修改。
上面两个问题也许太空太大了，不过我们可以把这个思路拓展一下，反思我们平常做的一些事情。就拿最普通的——
你做错题本是为了什么？我这里就坦白说了，很多人，包括我，做错题本都是被迫的，被迫于完成老师的任务。那么这样一来，事情就变质了。也许你拿第一种
复习错题是你
----------------------
真实的是什么？虚假的是什么？那些学习方法真的是法宝吗？那些不良行为真的是阻碍吗？施行蒙骗我们的不仅有我们自己，还有我们周围的一切。我们应该勤问：事实是什么？以自己内心出发，探求客观事实的因果关系，在敢于承认自己的错误的基础上对别人的想法进行批判论证，然后下好定义，明确目的，再加以施行。
一切应该建立在事实之上，而不是主观臆断上。每每问起那两个问题，我们总会说：我当然知道。但，你真的清楚了吗？你真的明白了吗？你真的认真思考过背后的逻辑，抛开主观的蒙蔽了吗？还是只是，套用那些成功经验呢？
via サン猫の時間漂流
这篇文章算是对之前想法的一些总结归纳，其中还有很多不严谨或者未经推敲的部分，换句话说，也许我自己都不清楚我在讲什么，是对或是错。
----------------------
高中正式的第一个学期结束了，我如愿以偿拿到了班级前十的好成绩。而每到大考结束，考了前十的人都会多一个额外任务：分享自己的学习方法。这时候我就开始琢磨了——我要分享什么好呢~奇怪的是，我的脑海中没有一点思绪。我心心念念盼了那么久的机会，等到真的到我手上的时候，我居然不知道应该说什么！？因为我发现我根本没有什么所谓的学习方法！
在提出这个暴论之前，我应该明确的一点就是：我指的是没有确切的，一以贯之的学习方法。也许在别人眼里，我是一个自律的人，可事实上，我没有定过一天计划、任务，更不要说什么做错题本的习惯了。如果硬拿一点来说，就是有时间写写日记，在里面吐槽一些事情，似乎也不是什么重要的线索……
----------------------
前面的只是引子，真正内容在下面
----------------------
坚信客观事实，不加主观修饰
我在我们班里总看见一类人：他们每天唯一的生活好像只有做作业了——自习课做作业；上主副课做作业；下课做作业；午休做作业；竞赛做作业；就连晚上寝室里面也开个手电筒做作业……问题是，往往每天晚自习下课说做不完作业的人，刚好就是同一批人。我于是陷入了沉思：兄弟，你已经废了这么多功夫做作业了，你怎么还是做不完啊！？
这类人是很擅长自我安慰的：我已经这么努力了……（别人就不会说我了吧） 如此这般，往往会形成滚雪球的情景：今天任务没完成，留到明天；明天又没有完成，继续拖……最后拖到回家，家里则奋笔疾书继续补，嗯，这样一个星期的轮回就完成了。
别说做作业了，做别的事情也是一样的。这种行为毫无疑义是有问题存在的，可是你又说不得他们：你有他们认真吗？你看过他们的笔记、错题本吗？你看过他们挑灯夜读的样子吗？你自己又是什么样的呢……可惜事实不会骗人，他们往往是成绩吊车尾的几个，虽然全段不差，但是在提前班着实是不够看的层面。
我看过他们的样子，也看过他们的笔记、错题本。说实话，我是真的为他们心痛，有如此精力却不愿意花时间整理反思，这样浪费时间，最后又获得了什么呢？
这也不能算是假努力，但这结果往往比假努力更为糟糕。假努力是你自己清楚的，是有问题的，但是这种情况给自己铺设了一条后路：我已经很努力了。 于是人就会
不思进取，反而更差了，陷入一种恶性循环。因为我们没有明确客观事实的因果关系。
我不需要知道你是怎么怎么想的，不考虑你到底是为了什么也要这样做。我只需要明确一个
事实：你这样做，是达不到你当前想要的所谓的目的（为什么是所谓下面有）的。这是无法辩驳的，因为你每天做的事情不断地在论证这一点。那么，你就应该承认自己的过失（如果你想改变的话），并且停止一切的主观修饰，不要给自己加滤镜了，别人只是不好意思说出来，如果你自己都被自己骗了，那就只能装一辈子了。我知道这很残酷，尤其是对于那些人来说。但，这就是事实，这是不能改变的。不是别人的学习方法拿来一用就好的，不是每天埋头做作业就好的。如果发现实际与设想有偏差，就应该立足于实际，而不是用设想麻痹自己！
这回答了我为什么不随便说几个学习方法糊弄一下，因为这很可能产生误解，达不到原有的效用。那么，我们应该怎么办呢？很简单，从内心出发，清楚自己到底想要什么，明白应该改变什么，你就会找到属于自己的一套方法，这是独一无二的。
----------------------
清楚想要什么，明白改变什么
经典问题之一：什么是学习？什么能算学习？学习的定义是什么？
你也许会说，这是一个没有答案的问题，或者说出自己的见解。两种都可以接受，但是关键不是这个问题的答案，关键是你有没有一条可以说服自己并且可以致用的
定义？很多人都忽略了这一点，以为这是一个开放性的问题就不需要回答了。可仔细想想很可笑了，每天在学习的人，居然连学习的定义都不知道？那你怎么知道你是否在学习？或者你不在学习？这难道依你的意志而改变吗？不会，对一个人来说，这也是客观事实的一种。经典问题之二：你学习是为了什么。
为了什么？不同的人会有不同的答案——这很正常。但是如果我过一会再问你呢？几天后？一个月后？你的答案会与第一次相同吗？这很难吧……毕竟就我自己而言，也不能找到一条终身侍奉的真理来指引我，所以我现在仍然不得不面对这个问题，并且加以修改。
上面两个问题也许太空太大了，不过我们可以把这个思路拓展一下，反思我们平常做的一些事情。就拿最普通的——
做错题本这个方法来讲吧。你对做错题本的定义是什么？是把题目干干净净抄写一次然后附上解析，还是抄一次题目重做一遍，还是标记错题位置以便后续查找复习？你以为的做错题本其实也有很多种方式去实现，问题就在于没有搞清自己的定义就火急火燎地忙于实践，这不是和上文讲的例子一样可笑又无助吗？你做错题本是为了什么？我这里就坦白说了，很多人，包括我，做错题本都是被迫的，被迫于完成老师的任务。那么这样一来，事情就变质了。也许你拿第一种
把题目干干净净抄写一次然后附上解析做了好几本错题本，甚至还被老师公开表扬。但这并不能改变什么东西，用之前的话来说，我不管你内心如何想的，总之你确是没有在写完错题本之后再仔细看过那些题目了，这些也许只是你炫耀的资本。但，我要强调的是客观事实，这就会引出后面的结果——错题本对你没有任何帮助。这时候又回到前面了，因为你现在不仅仅有了炫耀的资本，还有了安慰的资本：老师说的我都做了，你看我写了这么多，还被表扬了呢~复习错题是你
所谓的目的，至于真正的……那就要看你如何想的了。其实我也明白，没有人会有那种奇怪的目的。但是不妨在做事之前好好想一想，我到底是为了什么？我到底在做着什么？我们往往会被自己蒙骗——我们不希望自己拥有一个坏心情，不希望浪费。于是只能尽一切力量合法化自己的行为，深陷泥潭。
----------------------
真实的是什么？虚假的是什么？那些学习方法真的是法宝吗？那些不良行为真的是阻碍吗？施行蒙骗我们的不仅有我们自己，还有我们周围的一切。我们应该勤问：事实是什么？以自己内心出发，探求客观事实的因果关系，在敢于承认自己的错误的基础上对别人的想法进行批判论证，然后下好定义，明确目的，再加以施行。
一切应该建立在事实之上，而不是主观臆断上。每每问起那两个问题，我们总会说：我当然知道。但，你真的清楚了吗？你真的明白了吗？你真的认真思考过背后的逻辑，抛开主观的蒙蔽了吗？还是只是，套用那些成功经验呢？
via サン猫の時間漂流
在网络的另一头相遇
之前在学校里看主持人大赛的时候，有一个题目让我印象很深：“成功路上，总是与知音相伴”。可我觉得，这句话应该是“成功的路上，总是与孤独相伴”。哎，每每说到这种事，总是让我想起先前的一段时光，那时候我老是希望能找到一个真正的朋友——一位可以倾心交流的人。可结果……我往往成了小丑……有一句话令我彻底破防了：
“你和我之前见过的人都不一样，很少有人会像你一样说心里话……不太适应。为什么不能像别的人一样呢，每天过开心就好了呀”
----------------------
“朋友，难道只是这样吗？”我轻声地问自己，为什么我终于鼓起勇气和别人坦白时，却没人要听呢……难道真的是我太不合群了吗，还是我本来就不适合这样……
不知道又有多少次，当我以为可以在网上找到寄托时，他们却一个又一个地离开了。最后只剩下我了，而我也已经上了高中，也不知道还可以把这项未尽的事业推到多远。
----------------------
我和他的相遇只是偶然，我已不是之前那个一天到晚追求所谓朋友的我了，一切都很平静，他问我答，仿佛这次聊天仍然会像之前几次一样，没几天就结束了，扔进池塘里，泛不起一点涟漪。他还和我讲过他自己的一个宏伟目标，做一个高三毕业纪念程序。我有点好笑，倒不是笑他过于自大，只怕这愿望过于天真了。他把一切都列出来，很认真的给我看他的想法。原谅我不愿意再接触这种项目，因为之前的很多都化为了泡影。
“算了，我也不关心，这个，你需要我帮什么呢”
一切都很正常，他把我拉进了 github 的共同开发的名单。我没多想，只是我自己的项目都没时间做，哪有功夫管你呢。于是我就一直躺在名单里面装死，顺便看看项目怎么样罢了。后来，他还把我拉近他的小群里面让我当顾问，“哎，又是这种无聊的过家家游戏”，我想到，一切都很正常。
但是他做了一件让我想不到的事情……正中我的眉心。
我感觉他怎么和我之前一样，那么天真呢……
----------------------
我：“想不好给你送什么（没什么拿得出手的）”
他：“没有关系，感觉你帮了我忙, 这是应该的。” （其实没有帮什么忙的我愧疚感++）
我：“哎哎哎那也不至于这样吧”
他：“几十块钱没啥”
……
他：“其实不光是因为你帮了忙, 我觉得更多是因为”
----------------------
我承认我真的被吓傻了……
从小到大，这种话只有我对别人说，我也写过这种信，但是结局很悲惨。
我陷入了沉默。这个世界上，竟然还有人能做出这种事！？虽然我并不能完全理解他的做法，但想起曾经那些孤独的时光，突然觉得……
或许，当初我被孤独困扰时，是因为我过于在意表达自己，急于敞开心扉了。却没有想到，每个人都不同，每一次交往都需要过程，需要时间。有时候，真正的知音可能会悄然而至，而我们却未曾察觉。或许，在追求友谊的过程中，我过于焦虑，让自己变得有些刻意。
他的诚挚和天真，让我反思了很多。或许，我应该更加开放一些，不要过于拘谨。毕竟，人与人之间的联系，就像一场旅行，需要一点点勇气，一点点耐心，去发现彼此的美好，而不是急于要求对方与自己产生深刻的共鸣。
在这个瞬间，他在我眼中的形象，发生了翻天覆地的变化，我决定给自己一次机会，抓住他，哪怕是，面对之前我的不作为。
我：“其实你对我来说也差不多……”
我突然觉得自己也好天真，他只是送了一个小礼物，我却再一次变得和之前一样了。
“你不怕再一次扑空吗？”我问我自己。
“扑空又如何呢？人生就是一场冒险，而每一次尝试都是一次成长。就算扑空了，也不过是一段经历罢了。”我回答道，“毕竟，我也不缺这一段经历了。”
在这个寂静的时刻，我不禁想起了那句“成功路上，总是与知音相伴”。或许，我错过了很多人，但这一次，我不想再错过他，不论有意无意。
他：“不好和你说太多, 不然我的信就剧透完了”
明明已经在配送了，我却要走了……今天是等不到你的信了，这算是上天的安排吗？
via サン猫の時間漂流
Invalid media:
image
image
之前在学校里看主持人大赛的时候，有一个题目让我印象很深：“成功路上，总是与知音相伴”。可我觉得，这句话应该是“成功的路上，总是与孤独相伴”。哎，每每说到这种事，总是让我想起先前的一段时光，那时候我老是希望能找到一个真正的朋友——一位可以倾心交流的人。可结果……我往往成了小丑……有一句话令我彻底破防了：
“你和我之前见过的人都不一样，很少有人会像你一样说心里话……不太适应。为什么不能像别的人一样呢，每天过开心就好了呀”
----------------------
“朋友，难道只是这样吗？”我轻声地问自己，为什么我终于鼓起勇气和别人坦白时，却没人要听呢……难道真的是我太不合群了吗，还是我本来就不适合这样……
不知道又有多少次，当我以为可以在网上找到寄托时，他们却一个又一个地离开了。最后只剩下我了，而我也已经上了高中，也不知道还可以把这项未尽的事业推到多远。
……其实本来还写了很多，但是正如《乡土中国》中所说，文字仍然只是一个工具，一个不太完善的工具。现在我确是倒不出更多墨水来了，否则思想就歪了。
----------------------
我和他的相遇只是偶然，我已不是之前那个一天到晚追求所谓朋友的我了，一切都很平静，他问我答，仿佛这次聊天仍然会像之前几次一样，没几天就结束了，扔进池塘里，泛不起一点涟漪。他还和我讲过他自己的一个宏伟目标，做一个高三毕业纪念程序。我有点好笑，倒不是笑他过于自大，只怕这愿望过于天真了。他把一切都列出来，很认真的给我看他的想法。原谅我不愿意再接触这种项目，因为之前的很多都化为了泡影。
“算了，我也不关心，这个，你需要我帮什么呢”
一切都很正常，他把我拉进了 github 的共同开发的名单。我没多想，只是我自己的项目都没时间做，哪有功夫管你呢。于是我就一直躺在名单里面装死，顺便看看项目怎么样罢了。后来，他还把我拉近他的小群里面让我当顾问，“哎，又是这种无聊的过家家游戏”，我想到，一切都很正常。
但是他做了一件让我想不到的事情……正中我的眉心。
方便发一下你家地址吗？提前一个月的新年礼物 ⬇️我承认我被吓傻了，这这这我什么都没做怎么就，怎么就可以呢。
我感觉他怎么和我之前一样，那么天真呢……
----------------------
我：“想不好给你送什么（没什么拿得出手的）”
他：“没有关系，感觉你帮了我忙, 这是应该的。” （其实没有帮什么忙的我愧疚感++）
我：“哎哎哎那也不至于这样吧”
他：“几十块钱没啥”
……
他：“其实不光是因为你帮了忙, 我觉得更多是因为”
----------------------
我承认我真的被吓傻了……
从小到大，这种话只有我对别人说，我也写过这种信，但是结局很悲惨。
我陷入了沉默。这个世界上，竟然还有人能做出这种事！？虽然我并不能完全理解他的做法，但想起曾经那些孤独的时光，突然觉得……
或许，当初我被孤独困扰时，是因为我过于在意表达自己，急于敞开心扉了。却没有想到，每个人都不同，每一次交往都需要过程，需要时间。有时候，真正的知音可能会悄然而至，而我们却未曾察觉。或许，在追求友谊的过程中，我过于焦虑，让自己变得有些刻意。
他的诚挚和天真，让我反思了很多。或许，我应该更加开放一些，不要过于拘谨。毕竟，人与人之间的联系，就像一场旅行，需要一点点勇气，一点点耐心，去发现彼此的美好，而不是急于要求对方与自己产生深刻的共鸣。
在这个瞬间，他在我眼中的形象，发生了翻天覆地的变化，我决定给自己一次机会，抓住他，哪怕是，面对之前我的不作为。
我：“其实你对我来说也差不多……”
我突然觉得自己也好天真，他只是送了一个小礼物，我却再一次变得和之前一样了。
“你不怕再一次扑空吗？”我问我自己。
“扑空又如何呢？人生就是一场冒险，而每一次尝试都是一次成长。就算扑空了，也不过是一段经历罢了。”我回答道，“毕竟，我也不缺这一段经历了。”
在这个寂静的时刻，我不禁想起了那句“成功路上，总是与知音相伴”。或许，我错过了很多人，但这一次，我不想再错过他，不论有意无意。
他：“不好和你说太多, 不然我的信就剧透完了”
明明已经在配送了，我却要走了……今天是等不到你的信了，这算是上天的安排吗？
via サン猫の時間漂流
Invalid media:
image
image
从”数字识别“看人工智能理解问题
都说 2023 年是 AI 元年。诚然，在人工智能蓬勃发展的今天，从刚开始的“新奇玩意”，现在的人工智能更为成熟与完善。不同于先前的人工智能只能在特定内容中大放异彩，现在的人工智能还可以解决泛化问题：天文地理，古今中外，几乎无所不能。但是，看似“无敌”的人工智能却总是在基础问题——尤其是数学问题上面出错，这不得不让人怀疑，人工智能它真的“理解”了文本、图像吗？还是仅仅装作了解“东拼西凑”呢？
关于这个问题，让我们把时光转移到人工智能刚刚出现的那一段时间，去挖掘它的本质。其中最具代表性的项目就是“数字识别”了，它是人工智能在计算机视觉领域中的一个经典问题，通过这个问题，我们可以深入探讨人工智能在理解和解决问题时的一般性原理。我们不会深入了解其中的实现方式，仅仅通过其原理探讨理解问题。
“数字识别”的目标是让计算机系统能够自动辨识和理解手写或印刷的数字，这里我们讨论相对简单的点阵数字识别。在点阵数字识别中，每个数字由一个网格，其中每个元素表示一个像素的状态，通常是黑色（点亮）或白色（未点亮）。而这些一张张的“点阵图”，就被称作为“数据集”，每个点阵图有一个答案（标签），这就是我们人工智能在训练时的“训练数据”。有了“学习资料”，就需要“学生”，所谓的神经网络就是我们的“学生”。神经网络通常由多个层组成，包括输入层、隐藏层和输出层。这输入层就像眼睛、耳朵，用来接收数据；隐藏层就像人的大脑，用来处理数据；这最后的输出层就是人的嘴巴了，返回最终的结果。
与人的大脑类似的，在神经网络中有很多“神经元”，也称为节点或感知器。每个神经元接收来自输入的信号后对这些信号进行加权求和，并通过激活函数产生输出。在神经网络中，每一个神经元都链接了一条“单向边”。边上有一个“权重（w）”，代表了神经元链接的强度。通过激活函数，每次经过边时，就可以得到下一个神经元的状态，公式为“输出 = 激活函数 (∑i wi⋅xi)”。可以看见，激活函数是相同的，唯一有变化的就是权重了。这恰恰是整个神经网络的关键，一组合适的权重，就可以输出正确的结果。权重通过反向传播算法在训练过程中进行调整，以最小化网络输出与实际标签之间的误差。这调整权重的过程，也正是人工智能学习的过程。
最后我们终于得到了“一个”结果。真的是一个吗？其实不然。我们的人工智能有“十张嘴巴”，分别代表 1234567890 十个数字，每个“嘴巴”上有一个“置信度”，代表模型对某个类别的预测概率。最后，程序只会输出置信度最高的结果，看似只有“一个”结果而已。
讲了这么多基础知识，也许你已经发现了，整个神经网络的运算过程与真正的大脑有本质上的区别，其输出的结果（不是最后输出）也有天壤之别。若只看最后的结果，也许并不能发现什么明显区别，但“置信度”就是人工智能露出的马脚。我们经常说“1 是 1，2 是 2”，而并不是“这个数字有 83.237%的可能是 1”。在人脑中，这种“置信度”是不存在的，也是不需要的。也许有人会说：“那我看不清数字的时候，我也会猜一个最有可能的数字呀。”，这也是不一样的：人工智能不是“猜”出来的，而是“算”出来的。它的运作模式就确定了它在训练完毕之后，面对没有标签的训练集，其权重是不会改变的——也就是说，输入相同的内容，其返回的也是相同的，本质只是通过神经网络将结果“泛化”了，而没有真正意义上的“猜测”。
举个文本例子：比如我现在输入了“1+1=?”。如果是人脑，可能会直接说“2”。但人工智能就不同了，它可以直接“算”出上百个结果，“答案是 2”的置信度为 99.28%；“1+1=2”的置信度为 99.93%；“答案是 3”的置信度为 0.72%……当然，在不同神经网络中，所谓的“置信度”可能略有不同。但不可否认的是，人工智能仅仅是“算”出一个最可能的答案，而不是“算出答案”。也许你问 ChatGPT 什么是“+”，它会告诉你一堆定义理论，但是它实际上完全不能理解什么是“+”，其回答也不过是用海量数据堆砌起来的其中一张嘴巴而已了。如果从这个方面来说，人工智能甚至不如计算器——毕竟后者是真的“理解”数学运算的。
“数字识别”也好，“1+1”也罢。不论从哪方面看，得出的结果是相同的：“人工智能并不理解问题”。它缺乏对问题的内在理解，无法理解数字的概念，而只是通过学习大量样本数据中的模式来进行分类。即使在数字识别等任务上表现良好，但并不意味着人工智能理解了问题的本质。
via サン猫の時間漂流
都说 2023 年是 AI 元年。诚然，在人工智能蓬勃发展的今天，从刚开始的“新奇玩意”，现在的人工智能更为成熟与完善。不同于先前的人工智能只能在特定内容中大放异彩，现在的人工智能还可以解决泛化问题：天文地理，古今中外，几乎无所不能。但是，看似“无敌”的人工智能却总是在基础问题——尤其是数学问题上面出错，这不得不让人怀疑，人工智能它真的“理解”了文本、图像吗？还是仅仅装作了解“东拼西凑”呢？
关于这个问题，让我们把时光转移到人工智能刚刚出现的那一段时间，去挖掘它的本质。其中最具代表性的项目就是“数字识别”了，它是人工智能在计算机视觉领域中的一个经典问题，通过这个问题，我们可以深入探讨人工智能在理解和解决问题时的一般性原理。我们不会深入了解其中的实现方式，仅仅通过其原理探讨理解问题。
“数字识别”的目标是让计算机系统能够自动辨识和理解手写或印刷的数字，这里我们讨论相对简单的点阵数字识别。在点阵数字识别中，每个数字由一个网格，其中每个元素表示一个像素的状态，通常是黑色（点亮）或白色（未点亮）。而这些一张张的“点阵图”，就被称作为“数据集”，每个点阵图有一个答案（标签），这就是我们人工智能在训练时的“训练数据”。有了“学习资料”，就需要“学生”，所谓的神经网络就是我们的“学生”。神经网络通常由多个层组成，包括输入层、隐藏层和输出层。这输入层就像眼睛、耳朵，用来接收数据；隐藏层就像人的大脑，用来处理数据；这最后的输出层就是人的嘴巴了，返回最终的结果。
与人的大脑类似的，在神经网络中有很多“神经元”，也称为节点或感知器。每个神经元接收来自输入的信号后对这些信号进行加权求和，并通过激活函数产生输出。在神经网络中，每一个神经元都链接了一条“单向边”。边上有一个“权重（w）”，代表了神经元链接的强度。通过激活函数，每次经过边时，就可以得到下一个神经元的状态，公式为“输出 = 激活函数 (∑i wi⋅xi)”。可以看见，激活函数是相同的，唯一有变化的就是权重了。这恰恰是整个神经网络的关键，一组合适的权重，就可以输出正确的结果。权重通过反向传播算法在训练过程中进行调整，以最小化网络输出与实际标签之间的误差。这调整权重的过程，也正是人工智能学习的过程。
最后我们终于得到了“一个”结果。真的是一个吗？其实不然。我们的人工智能有“十张嘴巴”，分别代表 1234567890 十个数字，每个“嘴巴”上有一个“置信度”，代表模型对某个类别的预测概率。最后，程序只会输出置信度最高的结果，看似只有“一个”结果而已。
讲了这么多基础知识，也许你已经发现了，整个神经网络的运算过程与真正的大脑有本质上的区别，其输出的结果（不是最后输出）也有天壤之别。若只看最后的结果，也许并不能发现什么明显区别，但“置信度”就是人工智能露出的马脚。我们经常说“1 是 1，2 是 2”，而并不是“这个数字有 83.237%的可能是 1”。在人脑中，这种“置信度”是不存在的，也是不需要的。也许有人会说：“那我看不清数字的时候，我也会猜一个最有可能的数字呀。”，这也是不一样的：人工智能不是“猜”出来的，而是“算”出来的。它的运作模式就确定了它在训练完毕之后，面对没有标签的训练集，其权重是不会改变的——也就是说，输入相同的内容，其返回的也是相同的，本质只是通过神经网络将结果“泛化”了，而没有真正意义上的“猜测”。
举个文本例子：比如我现在输入了“1+1=?”。如果是人脑，可能会直接说“2”。但人工智能就不同了，它可以直接“算”出上百个结果，“答案是 2”的置信度为 99.28%；“1+1=2”的置信度为 99.93%；“答案是 3”的置信度为 0.72%……当然，在不同神经网络中，所谓的“置信度”可能略有不同。但不可否认的是，人工智能仅仅是“算”出一个最可能的答案，而不是“算出答案”。也许你问 ChatGPT 什么是“+”，它会告诉你一堆定义理论，但是它实际上完全不能理解什么是“+”，其回答也不过是用海量数据堆砌起来的其中一张嘴巴而已了。如果从这个方面来说，人工智能甚至不如计算器——毕竟后者是真的“理解”数学运算的。
“数字识别”也好，“1+1”也罢。不论从哪方面看，得出的结果是相同的：“人工智能并不理解问题”。它缺乏对问题的内在理解，无法理解数字的概念，而只是通过学习大量样本数据中的模式来进行分类。即使在数字识别等任务上表现良好，但并不意味着人工智能理解了问题的本质。
via サン猫の時間漂流
新的起点
我再一次把我的博客重置了。
我也不知道我为何如此沉浸于这过程：推倒，重来，再推倒，在重来……从米拓，到 WordPress ；从 Hexo，到如今的 Astro。那些炫酷，华丽，甚至令人眼花缭乱的特效，无一不在勾引着我幼小的心灵——为什么呢？从我接触的 CUI 到 GUI，到前端博客完全不是一个量级：本来需要死死敲代码才能实现的效果，而现在，现在只需要 pull 、 copy 一下就好了。可当裁缝终归不是不行的，于是我不停的 pull 、 push……到如今，我的提交次数已经超过了一千次。
巨量的提交次数却没有提升我的水平。我仍然是连一句前端代码都看不懂的 noob ，面对巨量的、重复的“Butterfly 美化日志”，我能做的只有对着报错发呆。回过头来，博客只有寥寥 20 几篇，彻底成为了一个臃肿的花架子。
博客本身的功能就很有限，现在看来，它甚至只能算是一个归档。可我却妄图使它变成一个“社交中心”：评论、说说、图库……说到底，我写博客，不是想要给予，只是想要索取。索取什么？不过是点击量、评论量、赞助量这种虚无缥缈的数据罢了。
人总会经历这种过程，我也理解以前的自己。但人是要改变的，总不能再这样下去了。没有真材实料，用博客制造所谓“空中楼阁”，骗取关注，是我所不齿的
我再一次把我的博客重置了。
没有带上之前的 28 篇文章，是因为我认为，这是一个新的起点。
我希望，当有一天我再一次回过头来翻阅这篇文章时，它再不是孤独的。
via サン猫の時間漂流
我再一次把我的博客重置了。
我也不知道我为何如此沉浸于这过程：推倒，重来，再推倒，在重来……从米拓，到 WordPress ；从 Hexo，到如今的 Astro。那些炫酷，华丽，甚至令人眼花缭乱的特效，无一不在勾引着我幼小的心灵——为什么呢？从我接触的 CUI 到 GUI，到前端博客完全不是一个量级：本来需要死死敲代码才能实现的效果，而现在，现在只需要 pull 、 copy 一下就好了。可当裁缝终归不是不行的，于是我不停的 pull 、 push……到如今，我的提交次数已经超过了一千次。
巨量的提交次数却没有提升我的水平。我仍然是连一句前端代码都看不懂的 noob ，面对巨量的、重复的“Butterfly 美化日志”，我能做的只有对着报错发呆。回过头来，博客只有寥寥 20 几篇，彻底成为了一个臃肿的花架子。
博客本身的功能就很有限，现在看来，它甚至只能算是一个归档。可我却妄图使它变成一个“社交中心”：评论、说说、图库……说到底，我写博客，不是想要给予，只是想要索取。索取什么？不过是点击量、评论量、赞助量这种虚无缥缈的数据罢了。
人总会经历这种过程，我也理解以前的自己。但人是要改变的，总不能再这样下去了。没有真材实料，用博客制造所谓“空中楼阁”，骗取关注，是我所不齿的
我再一次把我的博客重置了。
没有带上之前的 28 篇文章，是因为我认为，这是一个新的起点。
我希望，当有一天我再一次回过头来翻阅这篇文章时，它再不是孤独的。
via サン猫の時間漂流
【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中)
前言
我们之前说了 k 阶常系数线性递推方程的解法，可以使用特征方程求解。今天我们就来学习以下有关于
生成函数
概念
生成函数本身不代表什么特殊意义，生成函数是无限的，对其求解是无意义的，它仅仅作为一个工具来使用。
生成函数是一个形式幂级数，通常用来表示一个数列的各项。生成函数的一般形式如下：
$$ F(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots $$
其中，$a_0, a_1, a_2, \ldots$ 是数列的各项，$x$ 是一个变量。生成函数可以是有限的（当数列是有限项时）或无限的（当数列有无穷多项时）。同时我们也可以看到，函数中的自变量 $x$ 好像并没有什么意义，他的取值并不影响序列的表示，因此我们称这种函数为形式幂级数。
那么这时候就有小伙伴要问了，既然生成函数本身是一个无限长的函数，那么我们要如何使用它呢？
其实很简单，我们前面说了，生成函数可以将序列转换成多项式，那么如果我们能够计算出一个数列的生成函数，我们就可以知道这个数列的通项——也就是说，当我们可以把前面一般形式中的 $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots$ 表示出来，我们就完成了我们的目标，对于这个无限函数本身来说，这不是我们关心的内容。
应用
在常数性齐次递推中
之前我们说了，在这种一般情况下，我们使用特征方程可以求出其通项，我们今天尝试使用生成函数解决此类问题。
我们要构建生成函数 $H(x)$，使其满足递推关系。首先，将每一项 $h_n$ 与 $x^n$ 相关联：
$$H(x) = h_0 + h_1 x + h_2 x^2 + h_3 x^3 + \ldots$$
然后考虑我们已知的递推关系：$h_n = 5h_{n-1} + 6h_{n-2}$，可以写出下面三个函数。
$$ \begin{aligned} H(x) &= h_0 + &h_1 x& + &h_2 x^2& + &h_3 x^3& + &h_4 x^4& + &h_5 x^5&+\ldots \ 5xH(x) &= &5h_0x& + &5h_1 x^2& + &5h_2 x^3& + &5h_3 x^4& + &5h_4 x^5&+\ldots \ 6x^2H(x) &= &&&6h_0x^2& + &6h_1 x^3& + &6h_2 x^4& + &6h_3 x^5&+\ldots \ \end{aligned} $$
因为$h_n = 5h_{n-1} + 6h_{n-2}$，所以我们很容易发现从第三位开始，它们相加都满足$h_n x^n = 5h_{n-1} x^n + 6h_{n-2} x^n$的样子，则可以得到生成函数如下：
$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$
那么我们已经有了生成函数方程：
$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$
接下来，我们可以整理这个方程，将 $H(x)$ 的项整合在一起：
$$H(x) - 5xH(x) - 6x^2H(x) = h_0 - 5h_0x + h_1x$$
将 $H(x)$ 提取出来，得到：
$$(1 - 5x - 6x^2)H(x) = h_0 - 5h_0x + h_1x$$
现在，我们可以将方程两边除以 $(1 - 5x - 6x^2)$，从而求解出最终的生成函数 $H(x)$：
$$H(x) = \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$$
我们已经有了最终的生成函数 $H(x)$，接下来的步骤是将其重新展开成幂级数形式，然后找到系数，以得到数列 ${h_n}$ 的通解，让我们继续吧。
首先，我们要分解分母 $1 - 5x - 6x^2$，得到 $(1 - 6x)(1 + x)$。
然后，我们将分式进行部分分解，得到：
$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = \frac{A}{1 - 6x} + \frac{B}{1 + x}$$
接下来，我们可以计算系数 $A$ 和 $B$，
$$ \begin{aligned} A(1 + x) + B(1 - 6x) &= h_0 - 5h_0x + h_1x\ A + Ax + B - 6Bx &= h_0 - 5h_0x + h_1x\ \end{aligned} $$
得到：$A = \frac{h_0 + h_1}{7}$；$B = \frac{6h_0 - h_1}{7}$。
然后将分式展开成幂级数的形式：
$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = (\frac{h_0 + h_1}{7}) \cdot \frac{1}{1 - 6x} + (\frac{6h_0 - h_1}{7}) \cdot \frac{1}{1 + x}$$
使用几何级数的展开，几何级数的展开公式是：
$$\frac{1}{1 - r} = 1 + r + r^2 + r^3 + \ldots$$
其中，$r$ 是一个实数，通常称为公比。这个级数在 $|r| < 1$ 的情况下是收敛的，即当公比的绝对值小于 1 时，级数的和会收敛到一个有限的值。
如果公比 $r$ 的绝对值大于等于 1，那么级数就会发散，没有有限的和。
对于这个公式，我们简单证明一下：
$$ \begin{aligned} &设\ &S &= 1 + r + r^2 + r^3 + \ldots\ &则\ &rS &= r + r^2 + r^3 + r^4 + \ldots\ &得\ &(1-r)S&=1\ &综上所述 &S=\frac{1}{1 - r} &= 1 + r + r^2 + r^3 + \ldots\ \end{aligned} $$
在生成函数的推导中，几何级数展开经常用于将分式进行展开成幂级数形式。在这种情况下，我们通常需要确保公比 $r$ 的绝对值小于 1，以确保级数收敛。
还有 $1 + r$ 的情况如下：
$$\frac{1}{1 + r} = 1 - r + r^2 - r^3 + \ldots$$
那么我们把原式进行几何数级展开，我们可以得到：
$$(\frac{h_0 + h_1}{7}) \cdot (1 + 6x + 36x^2 + 216x^3 + \ldots) + (\frac{6h_0 - h_1}{7}) \cdot (1 - x + x^2 - x^3 + \ldots)$$
现在，我们将每一项展开并合并：
$$\frac{h_0 + h_1}{7} + \frac{h_0 + h_1}{7} \cdot (6x) + \frac{h_0 + h_1}{7} \cdot (36x^2) + \ldots + \frac{6h_0 - h_1}{7} + \frac{6h_0 - h_1}{7} \cdot (-x) + \frac{6h_0 - h_1}{7} \cdot (x^2) + \ldots$$
将各项整合：
$$\frac{h_0 + h_1}{7} + \frac{6h_0 + 6h_1}{7}x + \frac{36h_0 + 36h_1}{7}x^2 + \ldots + \frac{6h_0 - h_1}{7} - \frac{6h_0 - h_1}{7}x + \frac{6h_0 - h_1}{7}x^2 + \ldots$$
将各项系数与幂次结合，得到合并后的幂级数形式：
$$h_0 + h_1x + \left(6h_0 + 5h_1\right)x^2 + \left(30h_0 + 31h_1\right)x^3\ldots$$
那么它最后的通项公式如下：
$$h_n = (\frac{h_0 + h_1}{7}) \cdot 6^n + (\frac{6h_0 - h_1}{7}) \cdot (-1)^n$$
所以我们实际上是进行了一次展开->合并->展开的过程，刚开始我们定义了一个生成函数，但是由于都是未知项，我们无法直接求得确切值。所以我们通过合并成$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$的形式，把原先无穷个未知项变成了已知的$h_0$与$h_1$。最后我们再重新展开，就得到了一个可用于求解的幂级数形式。
在常数性非齐次递推中
终于上正片了，在一般情况下，递
via サン猫の時間漂流
前言
我们之前说了 k 阶常系数线性递推方程的解法，可以使用特征方程求解。今天我们就来学习以下有关于
生成函数的内容，它是一种在组合数学和离散数学中非常有用的工具，用于处理序列和计数问题。它可以将序列转换成多项式，从而使得处理序列的操作变得更加方便。在解决非齐次线性递推关系（也称为线性递推方程）时，生成函数可以提供一种有效的方法。生成函数
概念
生成函数本身不代表什么特殊意义，生成函数是无限的，对其求解是无意义的，它仅仅作为一个工具来使用。
生成函数是一个形式幂级数，通常用来表示一个数列的各项。生成函数的一般形式如下：
$$ F(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots $$
其中，$a_0, a_1, a_2, \ldots$ 是数列的各项，$x$ 是一个变量。生成函数可以是有限的（当数列是有限项时）或无限的（当数列有无穷多项时）。同时我们也可以看到，函数中的自变量 $x$ 好像并没有什么意义，他的取值并不影响序列的表示，因此我们称这种函数为形式幂级数。
那么这时候就有小伙伴要问了，既然生成函数本身是一个无限长的函数，那么我们要如何使用它呢？
其实很简单，我们前面说了，生成函数可以将序列转换成多项式，那么如果我们能够计算出一个数列的生成函数，我们就可以知道这个数列的通项——也就是说，当我们可以把前面一般形式中的 $a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots$ 表示出来，我们就完成了我们的目标，对于这个无限函数本身来说，这不是我们关心的内容。
应用
1. 序列的计数： 生成函数可以将序列的每一项与幂级数的相应项联系起来。通过操作生成函数，可以进行加法、乘法等操作，从而获得序列的某些性质，如总项数、平均值等。
2. 组合计数： 生成函数在组合数学中应用广泛。例如，如果我们有若干种物品，每种物品有不同的数量，我们可以使用生成函数来计算不同方式选择这些物品的总数。
3. 解决递推关系： 对于线性递推关系，生成函数可以转化为一个多项式方程，从而帮助我们求解递推关系中的项。形式幂级数在齐次递推关系中，生成函数的转化可以非常直接。对于非齐次递推关系，我们可以将问题转化为齐次递推关系的形式，然后使用特定的技巧来解决。
在常数性齐次递推中
之前我们说了，在这种一般情况下，我们使用特征方程可以求出其通项，我们今天尝试使用生成函数解决此类问题。
我们要构建生成函数 $H(x)$，使其满足递推关系。首先，将每一项 $h_n$ 与 $x^n$ 相关联：
$$H(x) = h_0 + h_1 x + h_2 x^2 + h_3 x^3 + \ldots$$
然后考虑我们已知的递推关系：$h_n = 5h_{n-1} + 6h_{n-2}$，可以写出下面三个函数。
$$ \begin{aligned} H(x) &= h_0 + &h_1 x& + &h_2 x^2& + &h_3 x^3& + &h_4 x^4& + &h_5 x^5&+\ldots \ 5xH(x) &= &5h_0x& + &5h_1 x^2& + &5h_2 x^3& + &5h_3 x^4& + &5h_4 x^5&+\ldots \ 6x^2H(x) &= &&&6h_0x^2& + &6h_1 x^3& + &6h_2 x^4& + &6h_3 x^5&+\ldots \ \end{aligned} $$
因为$h_n = 5h_{n-1} + 6h_{n-2}$，所以我们很容易发现从第三位开始，它们相加都满足$h_n x^n = 5h_{n-1} x^n + 6h_{n-2} x^n$的样子，则可以得到生成函数如下：
$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$
那么我们已经有了生成函数方程：
$$H(x) = h_0 - 5h_0x + h_1x+ 5xH(x) + 6x^2H(x)$$
接下来，我们可以整理这个方程，将 $H(x)$ 的项整合在一起：
$$H(x) - 5xH(x) - 6x^2H(x) = h_0 - 5h_0x + h_1x$$
将 $H(x)$ 提取出来，得到：
$$(1 - 5x - 6x^2)H(x) = h_0 - 5h_0x + h_1x$$
现在，我们可以将方程两边除以 $(1 - 5x - 6x^2)$，从而求解出最终的生成函数 $H(x)$：
$$H(x) = \frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$$
我们已经有了最终的生成函数 $H(x)$，接下来的步骤是将其重新展开成幂级数形式，然后找到系数，以得到数列 ${h_n}$ 的通解，让我们继续吧。
首先，我们要分解分母 $1 - 5x - 6x^2$，得到 $(1 - 6x)(1 + x)$。
然后，我们将分式进行部分分解，得到：
$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = \frac{A}{1 - 6x} + \frac{B}{1 + x}$$
接下来，我们可以计算系数 $A$ 和 $B$，
$$ \begin{aligned} A(1 + x) + B(1 - 6x) &= h_0 - 5h_0x + h_1x\ A + Ax + B - 6Bx &= h_0 - 5h_0x + h_1x\ \end{aligned} $$
得到：$A = \frac{h_0 + h_1}{7}$；$B = \frac{6h_0 - h_1}{7}$。
然后将分式展开成幂级数的形式：
$$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2} = (\frac{h_0 + h_1}{7}) \cdot \frac{1}{1 - 6x} + (\frac{6h_0 - h_1}{7}) \cdot \frac{1}{1 + x}$$
使用几何级数的展开，几何级数的展开公式是：
$$\frac{1}{1 - r} = 1 + r + r^2 + r^3 + \ldots$$
其中，$r$ 是一个实数，通常称为公比。这个级数在 $|r| < 1$ 的情况下是收敛的，即当公比的绝对值小于 1 时，级数的和会收敛到一个有限的值。
如果公比 $r$ 的绝对值大于等于 1，那么级数就会发散，没有有限的和。
对于这个公式，我们简单证明一下：
$$ \begin{aligned} &设\ &S &= 1 + r + r^2 + r^3 + \ldots\ &则\ &rS &= r + r^2 + r^3 + r^4 + \ldots\ &得\ &(1-r)S&=1\ &综上所述 &S=\frac{1}{1 - r} &= 1 + r + r^2 + r^3 + \ldots\ \end{aligned} $$
在生成函数的推导中，几何级数展开经常用于将分式进行展开成幂级数形式。在这种情况下，我们通常需要确保公比 $r$ 的绝对值小于 1，以确保级数收敛。
还有 $1 + r$ 的情况如下：
$$\frac{1}{1 + r} = 1 - r + r^2 - r^3 + \ldots$$
那么我们把原式进行几何数级展开，我们可以得到：
$$(\frac{h_0 + h_1}{7}) \cdot (1 + 6x + 36x^2 + 216x^3 + \ldots) + (\frac{6h_0 - h_1}{7}) \cdot (1 - x + x^2 - x^3 + \ldots)$$
现在，我们将每一项展开并合并：
$$\frac{h_0 + h_1}{7} + \frac{h_0 + h_1}{7} \cdot (6x) + \frac{h_0 + h_1}{7} \cdot (36x^2) + \ldots + \frac{6h_0 - h_1}{7} + \frac{6h_0 - h_1}{7} \cdot (-x) + \frac{6h_0 - h_1}{7} \cdot (x^2) + \ldots$$
将各项整合：
$$\frac{h_0 + h_1}{7} + \frac{6h_0 + 6h_1}{7}x + \frac{36h_0 + 36h_1}{7}x^2 + \ldots + \frac{6h_0 - h_1}{7} - \frac{6h_0 - h_1}{7}x + \frac{6h_0 - h_1}{7}x^2 + \ldots$$
将各项系数与幂次结合，得到合并后的幂级数形式：
$$h_0 + h_1x + \left(6h_0 + 5h_1\right)x^2 + \left(30h_0 + 31h_1\right)x^3\ldots$$
那么它最后的通项公式如下：
$$h_n = (\frac{h_0 + h_1}{7}) \cdot 6^n + (\frac{6h_0 - h_1}{7}) \cdot (-1)^n$$
所以我们实际上是进行了一次展开->合并->展开的过程，刚开始我们定义了一个生成函数，但是由于都是未知项，我们无法直接求得确切值。所以我们通过合并成$\frac{h_0 - 5h_0x + h_1x}{1 - 5x - 6x^2}$的形式，把原先无穷个未知项变成了已知的$h_0$与$h_1$。最后我们再重新展开，就得到了一个可用于求解的幂级数形式。
在常数性非齐次递推中
终于上正片了，在一般情况下，递
via サン猫の時間漂流
【数论】初等数论与线性代数综合（整合中）
前言
此篇为导航，由几篇子博客构成。
导航
via サン猫の時間漂流
前言
此篇为导航，由几篇子博客构成。
导航
● 关于数学符号：队列中
● 高斯消元入门：队列中
● 矩阵乘法入门：【线性代数】矩阵乘法与线性 DP 优化 | SaroProck
● 生成函数入门：【线性代数】生成函数在非常系数与非齐次的线性递推关系的应用(编辑中) | SaroProck
via サン猫の時間漂流
【数论】费马小定理
前言
费马小定理（Fermat's Little Theorem）是数论中的一个重要定理，它与素数和模运算相关。定理的表述如下：
对于任意素数 $p$，如果 $a$ 是一个整数，且 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} ≡ 1 (\mod p)$。
应用
模逆元计算
在模运算中，给定两个整数 $a$ 和 $p$，我们想要找到整数 $b$，使得 $(a \times b) \mod p = 1$。这里 $a$ 和 $p$ 必须互质，即它们没有共同的因子。费马小定理提供了一种计算模逆元的方法：
根据费马小定理，如果 $a$ 和 $p$ 互质（$a$ 不是 $p$ 的倍数），则有 $a^{p-1} ≡ 1 (\mod p)$。将等式两边同时乘以 $a^{-1}$（a 的模 p 逆元），得到 $a^{-1} ≡ a^{p-2} (\mod p)$。这意味着 $a^{p-2}$ 就是 $a$ 在模 $p$ 下的逆元。
所以，如果要计算 $a$ 在模 $p$ 下的逆元，只需计算 $a^{p-2} \mod p$，即可得到 $b$，使得 $(a \times b) \mod p = 1$。
via サン猫の時間漂流
前言
费马小定理（Fermat's Little Theorem）是数论中的一个重要定理，它与素数和模运算相关。定理的表述如下：
对于任意素数 $p$，如果 $a$ 是一个整数，且 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} ≡ 1 (\mod p)$。
应用
模逆元计算
在模运算中，给定两个整数 $a$ 和 $p$，我们想要找到整数 $b$，使得 $(a \times b) \mod p = 1$。这里 $a$ 和 $p$ 必须互质，即它们没有共同的因子。费马小定理提供了一种计算模逆元的方法：
根据费马小定理，如果 $a$ 和 $p$ 互质（$a$ 不是 $p$ 的倍数），则有 $a^{p-1} ≡ 1 (\mod p)$。将等式两边同时乘以 $a^{-1}$（a 的模 p 逆元），得到 $a^{-1} ≡ a^{p-2} (\mod p)$。这意味着 $a^{p-2}$ 就是 $a$ 在模 $p$ 下的逆元。
所以，如果要计算 $a$ 在模 $p$ 下的逆元，只需计算 $a^{p-2} \mod p$，即可得到 $b$，使得 $(a \times b) \mod p = 1$。
via サン猫の時間漂流
【博弈论】博弈论与SG函数
前文
从 ICD 到 DAG 的转化
DAG（有向无环图）可以用来代表任意一个 ICG 游戏。我们把 ICG 假设我们有两种点，一种为值为 1，代表从这个状态出发，先手必胜；另一种值为 0，代表从这个状态出发，先手必败。对于两种状态，把每一条有向边看作是状态的转移，我们可以得出以下连边规则：
第二条规则也是一个道理，如果我从这个状态转移能够让我的对手进入必败状态，那么对于当前的我来说我这个状态就是必胜的。
需要注意的是，虽然我们的有向边是从起点->终点的，且终点值为 0。但是实际上我们应该倒推，从一个状态的子状态可以得到这个状态，换句话说就是从终点 0 开始向后走，用现在处理的状态得到前一个状态。
但是这样会有问题，我们 1->1 的不好处理，不仅不知道实际情况，也不好知道转移的结果，所以需要用到下文的 SG 函数来辅助求解我们每一个状态的 SG 数，用 SG 数代替 01。
Sprague-Grundy 数的推导
SG 是 Sprague-Grundy 的缩写，查阅后才发现是两个人名，它使用起来非常简单，但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话，你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理，所以我们需要详细解释一下它的推导过程，这样才能加深理解。
首先我们定义一个概念，在一个状态节点$i$中，如果$SG[i]$大于零，则是必胜状态，如果如果$SG[i]$等于零，则是必败状态。那么这样就可以分开 1->1 的情况。
那么根据我们上面的守则，我们可以写出下面的更新过程：
$$ SG_{}\left(A\right)=mex\left\lbrace SG\left(B\right)\left|A\rightarrow B\right.\right\rbrace $$
式子中的A 和 B 表示状态，$A\rightarrow B$表示$A$状态可以达到$B$状态，也就是$B$是$A$的子状态。mex 是一个定义在集合上的函数，返回的是不属于这个集合的最小非负整数。比如$mex(0, 1)= 2$，$mex(0, 2) = 1$, $mex(0,1, 2, 3)=4$。那么我们就把上面啰嗦的三句话整合成了等价的一个$mex$函数。
最后还有一点，就是我一个子状态可能包含几个“孙状态”。比如有一道例题如下：
SG 的结论推导
这个是博弈论最最困难的地方，像通过 SG 函数与$mex$你可以很轻松求出每一个状态的 SG 值，但是实际应用中总是不切实际的——你不可能枚举每一个子状态再计算。这就要求选手通过有限的打表推断出普遍规律，这总是很难的。
每一道题目的结论都不相同，但宗旨就是——把对手扔到必败状态。具体来说就是我们可以锁定最后几个失败的状态找到他们与众不同的特点，虽然在中间满足这些特点的状态不一定是必败的，但是我们可以确定 ICG 游戏一定是会结束的，所以如果你可以让对手一直保持这个特点，那么只要走到终点状态，对手一定是必败的。
SG 的结论推导需要多刷多看才能找出其奥妙所在，有时候也可以根据题面找线索，比如二分图想到最大连通分量这些。但最后还是要看选手自己对数的理解——实在不行也有 SG 陪着你不是吗，不论如何，ICG 游戏只有先手必胜和先手必败两种情况，虽然打表找规律这种方法不甚高明，但是在比赛中也无可厚非了。
via サン猫の時間漂流
前文
有两个游戏者：$A$和$B$。有$n$颗石子。这类经典的 NIM 游戏（Impartial Combinatorial Games——ICG 游戏的一种）可以通过博弈论与Sprague-Grundy 数——SG 函数解决，当然其前提要求是 ICG 游戏，也就是公平组合游戏，它往往要满足以下要求。
约定：两人轮流取走石子，每次可取 1、2 或 3 颗。$A$先取，取走最后一颗石子的人获胜。
问题：$A$有没有必胜的策略？
1. 两名选手；本文将详细介绍如何通过基础博弈论与 SG 函数通过归纳数学解决此类问题。
2. 两名选手轮流行动，每一次行动可以在有限合法操作集合中选择一个；
3. 游戏的任何一种可能的局面(position)，合法操作集合只取决于这个局面本身；局面的改变称为“移动”(move)。
4. 若轮到某位选手时，该选手的合法操作集合为空，则这名选手判负。
需要说明的是，棋类游戏都不是 ICG 游戏，包括封面的国际象棋。
从 ICD 到 DAG 的转化
DAG（有向无环图）可以用来代表任意一个 ICG 游戏。我们把 ICG 假设我们有两种点，一种为值为 1，代表从这个状态出发，先手必胜；另一种值为 0，代表从这个状态出发，先手必败。对于两种状态，把每一条有向边看作是状态的转移，我们可以得出以下连边规则：
1. 一个状态是必败状态当且仅当它的所有后继都是必胜状态。第一条规则的含义很清楚了，如果我不管怎么走，我走之后对于对方来说永远都是必胜的，那么对我来说我这个状态就是必败的。
2. 一个状态是必胜状态当且仅当它至少有一个后继是必败状态。
第二条规则也是一个道理，如果我从这个状态转移能够让我的对手进入必败状态，那么对于当前的我来说我这个状态就是必胜的。
需要注意的是，虽然我们的有向边是从起点->终点的，且终点值为 0。但是实际上我们应该倒推，从一个状态的子状态可以得到这个状态，换句话说就是从终点 0 开始向后走，用现在处理的状态得到前一个状态。
但是这样会有问题，我们 1->1 的不好处理，不仅不知道实际情况，也不好知道转移的结果，所以需要用到下文的 SG 函数来辅助求解我们每一个状态的 SG 数，用 SG 数代替 01。
Sprague-Grundy 数的推导
SG 是 Sprague-Grundy 的缩写，查阅后才发现是两个人名，它使用起来非常简单，但是推导过程有些复杂。如果我们忽略推导过程直接去研究它的使用的话，你会有一种在运用魔法的感觉。因为你完全猜测不到它其中的原理，所以我们需要详细解释一下它的推导过程，这样才能加深理解。
首先我们定义一个概念，在一个状态节点$i$中，如果$SG[i]$大于零，则是必胜状态，如果如果$SG[i]$等于零，则是必败状态。那么这样就可以分开 1->1 的情况。
那么根据我们上面的守则，我们可以写出下面的更新过程：
1. 首先获得一个状态的所有子状态这个面向过程的更新多少有点繁琐，我们可以写一个$mex$函数一次解决，具体写法如下：
2. 如果子状态中有 0，说明这个是一个必胜状态，给它打上一个与子状态不同的标记
3. 如果子状态都大于 0，说明这是一个必败状态，就打上标记 0
$$ SG_{}\left(A\right)=mex\left\lbrace SG\left(B\right)\left|A\rightarrow B\right.\right\rbrace $$
式子中的A 和 B 表示状态，$A\rightarrow B$表示$A$状态可以达到$B$状态，也就是$B$是$A$的子状态。mex 是一个定义在集合上的函数，返回的是不属于这个集合的最小非负整数。比如$mex(0, 1)= 2$，$mex(0, 2) = 1$, $mex(0,1, 2, 3)=4$。那么我们就把上面啰嗦的三句话整合成了等价的一个$mex$函数。
最后还有一点，就是我一个子状态可能包含几个“孙状态”。比如有一道例题如下：
在一个平面上有$n$个点勾勒了一个凸四边形的轮廓，有两个游戏者$A$和$B$，每一个人可以连接任意两个点画出一条实线，要求实线不能交叉，一个点也不能被多次选择，问谁胜？在这个题目中，我举一个例子：当$n$为 4 时，我有两种子状态：连相近的两条边，剩下两个可以连接的边；还有连对角的两条边，剩下两个孤立的点。第一个很好判断，子状态就是$SG(2)$。而第二个子状态却是用两个孙状态拼起来的，也就是一个$SG(1+1)$，这与$SG(2)$是不等价的，我们规定$SG(A + B) = SG(A) xor SG(B)$，如果有多个孙状态，就是他们的异或和，如此一来就可以正常表示一个子状态了。
SG 的结论推导
这个是博弈论最最困难的地方，像通过 SG 函数与$mex$你可以很轻松求出每一个状态的 SG 值，但是实际应用中总是不切实际的——你不可能枚举每一个子状态再计算。这就要求选手通过有限的打表推断出普遍规律，这总是很难的。
每一道题目的结论都不相同，但宗旨就是——把对手扔到必败状态。具体来说就是我们可以锁定最后几个失败的状态找到他们与众不同的特点，虽然在中间满足这些特点的状态不一定是必败的，但是我们可以确定 ICG 游戏一定是会结束的，所以如果你可以让对手一直保持这个特点，那么只要走到终点状态，对手一定是必败的。
SG 的结论推导需要多刷多看才能找出其奥妙所在，有时候也可以根据题面找线索，比如二分图想到最大连通分量这些。但最后还是要看选手自己对数的理解——实在不行也有 SG 陪着你不是吗，不论如何，ICG 游戏只有先手必胜和先手必败两种情况，虽然打表找规律这种方法不甚高明，但是在比赛中也无可厚非了。
via サン猫の時間漂流
【线性代数】矩阵乘法与线性DP优化
前言
现在有一道题目如下：
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
via サン猫の時間漂流
前言
现在有一道题目如下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。众所周知斐波那契数列的递推公式是：$f_i = f_{i-1} + f_{i-2}$。通过$O(N)$的时间递推可以在 1s 内求出前 1e8 的斐波那契数，但是题目的范围是 1e18，这要怎么办呢？这时候就要引出我们今天要学习的内容——矩阵与矩阵乘法了。
概念
什么是矩阵（matrix）
下面是一个$2 \times 2$的矩阵，其中
a，b，c，d，是里面的元素，矩阵里的元素可以是数字符号或者数学式。$$\begin{bmatrix}{a} & {b} \ {c} & {d}\end{bmatrix}$$
关于矩阵的其他内容我们不再延申，你现在只要知道矩阵是这么样的一个东西就可以了。
矩阵可以用字母代表，那么矩阵 $A_{n \times m}$ 本质上是一个 n 行 m 列的二维数组。
矩阵乘法
矩阵之间可以相乘，并且满足结合律与分配律——不满足交换律，在$n \times m(n \ne m)$这种不是
正方形的矩阵中，交换前后两个矩阵相乘会导致结果矩阵的形状不同，我们会在后面解释。矩阵相乘时，相乘矩阵的宽高必须有一个相同，否则无法配对。比如下面这个式子，把矩阵$A \times B = C$，可以这样写：
$$ C*{n\times s}=A*{n\times m}:\times B_{m\times s} $$
那么它实际上就等于：
$$ C*{ij}=\sum A*{ik}\times B_{kj}\left(1:\le:k:\le:m\right) $$
其中 k 的遍历过程也就是
相乘矩阵的宽高必须有一个相同的原因，否则匹配不了。写成代码形式，就和弗洛伊德很像，可以把弗洛伊德看成是魔改的矩阵乘法：
for(int i = 1; i <= an; i++)
for(int k = 1; k <= am; k++)
for(int j = 1; j <= bm; j++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];
用矩阵优化线性 DP
回到前言我们说的题目，这里回顾一下：
输入一个整数 n ($n \leq 10^{18}$)， 求第 n 个斐波那契数。我们每一次转移可以用一个矩阵表示：
$$ \left[{f_{i-1}},:f_{i-2}\right]\times\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]=\left[{f_i},:f_{i-1}\right] $$
因为是线性的，所以我们很容易发现，每一转移其实就是当前的状态矩阵乘上我们的$\left[\begin{matrix}{1} & {1} \ {1} & {0}\end{matrix}\right]$，那么每转移一次，i 就加一，我们先处理出$f_1,f_2$，那么通过$n-2$次转移，我们就可以得到$f_n$的值。
延伸
所有类似于这样的线性 DP 都可以用矩阵来转移，比如$f_i = f_{i-1} + f_{i-3} + f_{i-4}$，这种转移，我们可以构造下面这一个转移矩阵：
$$ \begin{bmatrix}1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 1 & 0 & 1 & 0 \ 1 & 0 & 0 & 1\end{bmatrix} $$
然后使用快速幂可以把时间复杂度从$O(N)$优化到$O(k^3 \log N)$ ，其中 k 是状态是数量，也就是转移矩阵的边长。
下面是实例代码，可以解决$f_i = f_{i-1} + f_{i-3} + f_{i-4}$求解$f_n$并且$n \leq 10^{18}$的情况。
这里因为乘的顺序不一样（交换了），矩阵不能使用交换律，所以转移矩阵稍有不同。（实际上一般情况下习惯把系数放在第一行，也就是代码中转移矩阵的样子）
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> matrix;
matrix multiply(matrix a, matrix b, ll mod)
{
ll n = a.size();
matrix c(n, vector<ll>(n));
for (ll i = 0; i < n; i++)
for (ll j = 0; j < n; j++)
for (ll k = 0; k < n; k++)
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
return c;
}
matrix matrix_pow(matrix a, ll n, ll mod)
{
ll m = a.size();
matrix res(m, vector<ll>(m));
for (ll i = 0; i < m; i++)
res[i][i] = 1;
while (n)
{
if (n & 1)
res = multiply(res, a, mod);
a = multiply(a, a, mod);
n >>= 1;
}
return res;
}
int main()
{
matrix a = {{1, 0, 1, 1},
{1, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0}}; // 转移矩阵
ll n;
scanf("%lld", &n); // 2, 4, 6, 9
matrix ans = matrix_pow(a, n - 4, 10007);
printf("%lld", (ll)(2 * ans[0][3] + 4 * ans[0][2] + 6 * ans[0][1] + 9 * ans[0][0]) % 10007);
return 0;
}
via サン猫の時間漂流
【题解】7月11日比赛题解备份
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
一．重复字符串(powerstr):
30分做法：枚举
长度范围只有 1000 时，我们可以枚举 k， 取字符串第 1 个到第 k 个字符作为子串 T，然后去验证剩下的字符串是否都是 T 重复得来
时间复杂度 O(n^2)
100分做法：KMP，Next数组
假设字符串为 S，长度为 N，子串 T 重复 K 次后得到串 S，那么 T 的长度一定为 L = N/K(要整除)，则$T = S[1...L]$，将 S 拆分成 K 份，每份长度为 L，则有
$$S[1...L] = S[L+1...2L] = S[2L+1...3L] = ... = S[(K-1)L+1...KL]$$
由于要保证 K 最大，势必 L 要取最小，所以根据 Next 函数的定义，有$Next[KL] = (K-1)L;$
即$Next[N] = N - L$，所以$L = N - Next[N];$
但是得出的长度 L 还要保证能被 N 整除，所以如果不能整除说明 L = N，即 K = 1；而如果能整除，那么$K = N / (N - Next[N]);$
因而我们只要对字符串 S 做一趟 KMP，对其求 Next 数组，剩下的就是上述结论
时间复杂度$O(n)$
二．Fibonacci 进制(fib):
100分做法：DP
N 很大，先尝试几个小数据。可以发现，每个 Fibonacci 表示的长度，和 Fibonacci 数大小有关（1,2,3,5,8,13,21……），这些值最高位上是 1，后面全是 0，即第一个 Fibonacci 表示长度为 i 的数是$fib[i]$。因此按照长度对 Fibonacci 表示进行分类，长度为 i 的数有$fib[i-1]$个，看做是第 i 组。那么第 i 组的总长度$len[i] = fib[i-1]*i$。
接下来，看 1 出现的次数。长度为 i 的数的表示中，第 i-1 位肯定是 0。
$Sum[i]$表示前 i 组的 1 的个数。可以得到如下式子：$Sum[i]=sum[i-1]+fib[i-1]+sum[i-2]$。第 i 组首位 1 的个数为$fib[i-1]$，$i-1$位为 0，那么最后的 i-2 位的情况，恰好为 1~i-2 组的所有情况。
整体算法也就明了了：
1. 求出 N 位所在的 Fibonacci 表示的数的长度 t
2. 求 1~t 中 Fibonacci 表示中 1 出现的个数。
3. 继续求解剩余字符的 1。
4. 最后一个暴力扫描
例如求解得到最后对应 Fibonacci 表示为 x=100100
1. 对于长度为 1~5 的 Fibonacci 表示中 1 的个数为$sum[5]$，i<=100000 中 1 的个数即为$sum[5]+1$。
2. 对于 100000<i<=100100,最高位都是 1，共有$fib[3]$个，后三位 1 的个数为$sum[2]+1$。
3. 1 的总个数为$sum[5]+1+fib[3]+sum[2]+1$。
最后细节比较多，要实现的仔细一些。
三.发奖金(reword):
100*分做法：组合+质因数分解+逆元+中国剩余定理
题目相当于求 n 个数的和不超过 m 的方案数。
首先如果是恰好等于 m，那么就等价于求方程$x_{1} + x_{2} + ... + x_{n} = m$的解的个数，利用插板法可得到公式：$C(n + m - 1, m)$ 现在要求不大于 m 的，相当于对$i = 0 ... m$对$C(n + i - 1, i)$求和，根据 pascal 递推式可以得到答案为$C(n + m, m)$ 现在就需要求$C(n + m, m) \mod P$
这里我们主要要解决如何快速计算$n! \mod P$
以及当分母有$m! \mod P$的情况
1. 当 n,m 都比较小的时候，同时 P 为比较大的素数时，可以直接利用逆元求解，当 n,m 比较大的时候，见下面两种情况（以下参考魏铭 2011 年国家集训队作业）
2. 当 P 为素数的情况：
我们发现$n! \mod P$的计算过程是以 P 为周期的，举例如下：
$$n = 10, P = 3$$ $$n! = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10$$ $$= 1 * 2 * 4 * 5 * 7 * 8 * 10 * 3 * 6 * 9$$ $$= (1 * 2)^3 * 3^3 * (1 * 2 * 3)$$
最后一步中的$1 * 2 *3$可递归处理。
因为 P 的倍数与 P 不互质，所以 P 的倍数不能直接乘入答案，应当用一个计数器变量 cnt 来保存答案中因子 P 的个数。
我们提前预处理出$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$，函数 calcfac(n)返回$n! \mod P$的值，power(a, b, c)返回$a^b \mod c$的值，可用快速幂在$O(logb)$的时间内完成。
typedef long long LL;
LL calcfac(LL n)
{
if (n <P) return fac[n];
LL seg = n / P, rem = n % P;
LL ret = power(fac[P - 1], seg, P); //fac[P - 1]重复出现了seg次
ret = ret * fac[rem] % P; //除去seg次fac[P – 1]外，剩下的零头
cnt += n / P; //提出n / P个因子P
ret = ret * calcfac(n / P) % P; //递归处理
return ret;
}
于是$n! \mod p$的计算可在$O(logn)$的时间内解决。
对于分母中的 n!，方法是相似的。若 a 为正整数，$a * a’ = 1(\mod P)$，那么我们称 a’为 a 的逆元，记作 a-1，并有$b / a(\mod P) = b * a-1(\mod P)$。这样我们只需要把预处理$fac[i] = 1 * 2 * 3 * … * (i – 1) * i \mod P$更换为$inv[i] = 1-1 * 2-1 * 3-1* … * (i – 1) -1 * i-1 \mod P$，其计算方法与分子中的 n!计算相差无几，具体可参考我的代码。求逆元可以使用扩展欧几里得算法。
3. 当 p 为合数时
对于某些测试点，我们发现 P 分解后只有 2 个因子，并且不相同，所以我们可以对这两个因子分别运行算法 2，最后用中国剩余定理合并即可。
对于剩下的数据，可以对 P 进行质因数分解，得到$P = p1^{c1} * p2^{c2} * … * pt^{ct}$。
对于每个$1≤i≤t$，以$pi^{ci}$为模运行算法 2，最后用中国剩余定理合并。这里$pi^{ci}$不一定为质数，不过只需对原算法稍加修改即可。令$P = pi^{ci}$，$fac[i] = 除去pi的倍数外i的阶乘$。例如$pi = 3,ci = 2$，那么$fac[10] = 1 * 2 * 4 * 5 * 7 * 8 * 10$，除去了 3 的倍数 3、6 和 9。阶乘依然是以 P 为周期的，calcfac(n)与算法 2 主体相同，只是统计因子个数时，应使用$ret += n / pi$而不是$ret += n / P$，递归处理时也应该是 calcfac(n / pi)而不是 calcfac(n / P)。
时间复杂度$O(t * n)$
via サン猫の時間漂流
【图论】双连通分量
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
求双连通分量
先观察
via サン猫の時間漂流
前言
在学习双连通分量之前请先了解强连通分量，有助于理解双连通分量，其中相同的概念不再赘述。
我的强连通分量笔记在：【图论】强连通分量
概念
强连通分量是对于有向图而言的，而双连通分量是对于无向图而言的。
割边与割点
在无向图中， 割点：去掉一个点及与其相邻的所有边，无向图中的连通分量增加，则称该点为割点。 割边：去掉一条边，无向图中的连通分量增加，则称该边为割边。 割点与割边的关系：
1. 有割点不一定有割边，有割边一定有割点。
2. 割边的两个端点中一定有一个是割点。
详细内容请阅读：【图论】割边与割点
什么是双连通分量
根据上面割边与割点的定义，我们可以把双连通分量分成边双和点双两种。
1. 边双：对于一个图，假如仅仅对于该图而言其中没有割边，那么我们称这个图是边双联通的。那么一个极大的边双连通子图就是母图的边双连通分量。也就是说在这个子图中任意删去一条边，每一个点之间仍然是连通的。
2. 点双：对于一个图，假如仅仅对于该图而言其中没有割点，那么我们称这个图是点双联通的。那么一个极大的点双连通子图就是母图的点双连通分量。也就是说在这个子图中任意删去一个点和那些与之相邻的边，每一个点之间仍然是连通的。
需要注意的是点双与强连通分量和边双不同，它会与其他点双相交，需要注意
求双连通分量
先观察
via サン猫の時間漂流
【数据结构】邻接表与链式前向星
邻接表（使用 vector）
存图方式
遍历方式
添加方式
----------------------
链式前向星
存图方式
遍历方式
添加方式
via サン猫の時間漂流
邻接表与链式前向星更正： 使用vector存图的叫做邻接表使用数组模拟的叫做链式前向星
邻接表（使用 vector）
使用邻接表的优劣： 优势：
1. 码量少，易操作
2. 不用担心空间，不易写错
劣势：
1. cpp11 之前不能使用auto v : i形式遍历 vector
2. 在不能开启O2的题目中较慢（POJ 全占）
存图方式
struct line // 自定义结构体
{
int ver; // 指向的结点
int edge; // 边的权值
line(int v, int e) // 构造函数
{
ver = v;
edge = e;
}
};
vector<line> g[MAX]; // 新建邻接表
遍历方式
对于 C++11 后的 OJ，使用如下方式遍历：
// line是结构体的名字
// from是父节点的下标
for(line son : g[crd])
{
// 示例代码，含义为不经过父节点
if(son.ver == from) continue;
}
对于 C++11 前的 OJ，使用如下方式遍历其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2
// line是结构体名字
for (line son = g.begin(); son != g.end(); son++)
// 下略……
添加方式
// N为边的数量
for(int i = 1; i < N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(line(v, w));
g[v].push_back(line(u, w));
}
----------------------
链式前向星
使用链式前向星的优劣： 优势：
1. 速度快，无需O2
2. 不受 C++版本限制，适用于所有题目
劣势：
1. 数组模拟链表，初学者不易理解
2. 码量多，不理解容易打错，不易 Debug
存图方式
struct line
{
int ver; // 指向的结点
int next; // 下一条边
// int edge; // 边的权值
}node[MAX * 2]; // 新建链式前向星
int head[MAX]; // 表头数组
遍历方式
for(int son = head[crd]; son; son = node[son].next)
// 下略……
添加方式
// 前向星添加边（使用函数）
// tot为所有边的数量，初始值为0
void add(int u, int v/*, int edge*/)
{
node[++tot].next = head[u];
node[tot].ver = v;
//node[tot].edge = edge;
head[u] = tot;
}
via サン猫の時間漂流
