CF1970E3 Trails (Hard) 题解

题目

题目大意: 给定 个点. 每个点都和一个共同的中心点有若干条路径. 对于第 个点, 有 条短路径, 条长路径. 一个小人开始在 号点, 每天他要走两条路径到达一个点(可以和出发点相同), 要求每天走过的路径至少有一条长路径. 问走 天后, 所有合法路径的方案数.

思路

一个朴素的想法是递推.

设第 天在 号点的方案数为 .

则有

令 也就是

使用矩阵快速幂可以解决.

但是我们发现 我们甚至连一次矩阵乘法都做不完!

我们发现

这何尝不是一种矩阵乘法?

于是我们构造矩阵

那么

而 是一个二阶矩阵, 可以计算!

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define ls tree[p].l
#define rs tree[p].r
#define mid ((l + r) >> 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
int mylog(int a){
	int ans=0;
	if(a&0xffff0000){
		ans+=16;
		a>>=16;
	}
	if(a&0x0000ff00){
		ans+=8;
		a>>=8;
	}
	if(a&0x000000f0){
		ans+=4;
		a>>=4;
	}
	if(a&0x0000000c){
		ans+=2;
		a>>=2;
	}
	if(a&0x00000002){
		ans+=1;
		a>>=1;
	}
	return ans;
}
inline int read(){
	register int a=0,b=0;
	register char c;
	c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')b=1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return b?-a:a;
}
const int MAXM = 100010;
const int MOD = 1e9 + 7;
struct Matrix{
	int n, m;
	int **data;
	Matrix(int e) : n(e), m(e){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			data[i][i] = 1;
		}
	}
	Matrix(int n, int m) : n(n), m(m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
	}
	Matrix(const Matrix & other) : n(other.n), m(other.m){
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
	}
	~Matrix(){
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
	}
	Matrix& operator= (const Matrix & other){
		if(&other == this) return *this;
		rep(i, 0, n){
			delete[] data[i];
		}
		delete[] data;
		n = other.n;
		m = other.m;
		data = new int*[n + 1];
		rep(i, 0, n){
			data[i] = new int[m + 1];
		}
		rep(i, 1, n){
			rep(j, 1, m){
				data[i][j] = other.data[i][j];
			}
		}
		return *this;
	}
	Matrix operator* (const Matrix &other){
		Matrix ans(n, other.m);
//		ans.n = n;
//		ans.m = other.m;
		rep(i, 1, ans.n){
			rep(j, 1, ans.m){
				ans.data[i][j] = 0;
				rep(k, 1, m){
					ans.data[i][j] = ((ll)ans.data[i][j] + (ll)data[i][k] * other.data[k][j] % MOD) % MOD;
					if(ans.data[i][j] < 0){
						cout << 1;
					}
				}
			}
		}
		return ans;
	}
};
Matrix ksm(Matrix a, int k){
	if(k == 0) return Matrix(a.n);
	if(k == 1) return a;
	if(k & 1){
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp * a;
	}
	else{
		Matrix tmp = ksm(a, k >> 1);
		return tmp * tmp;
	}
}
int s[MAXM], l[MAXM];
signed main(){
	int m = read(), n = read();
	rep(i, 1, m) s[i] = read();
	rep(i, 1, m) l[i] = read();
	Matrix A(m, 2), B(2, m);
	rep(i, 1, m){
		A.data[i][1] = s[i] + l[i];
		A.data[i][2] = l[i];
	}
	rep(i, 1, m){
		B.data[1][i] = s[i] + l[i];
		B.data[2][i] = MOD - l[i];
	}
	Matrix a0(m, 1);
	rep(i, 2, m) a0.data[i][1] = 0;
	a0.data[1][1] = 1;
	Matrix tmp = ksm(B * A, n - 1) * B * a0;
	Matrix ans = A * tmp;
	ll sum = 0;
	rep(i, 1, m) sum += ans.data[i][1];
	printf("%lld", sum % MOD);
    return 0;
}

你想活出怎样的人生？《吹响吧！上低音号》人物志与我的竞赛半生

4 月 7 日，《吹响把，上低音号 3》即将播出，希望大家可以看看，很好的群像剧。至少，希望读者可以看看我的这篇人物志，多少可以一窥这部优秀作品与笔者的人生。

前言

《吹响把，上低音号》（以下简称《悠风号》）无疑是一部非常出色的群像剧。当我去看这部番的时候，我从没想到，这部番能引起我如此巨大的共鸣，以至于我现在想要写一些什么来表达我对这部作品的思考。

我喜欢的作品很多，但真正愿意投入精力的很少。我向来不会因为某些但单一的元素而热爱一部作品。只有当一部作品真正写出了我人生当中很多经历的时候，我才会发自内心地热爱一部作品，就像《Canon in D Major》一样。在我看来，《悠风号》正是一部这样真实得令人“痛苦”的作品。

所以，在第三季开播的前夕，我用这样一篇人物志来探讨这部作品反映的一些不同人生，以及与我竞赛半生的相似之处。

背景

为了让更多的读者可以更好地看懂这篇文章，有必要描述一下故事的背景。

故事背景设定在北宇治高中的吹奏部。主人公（剧情触发机）黄前久美子是吹奏部的上低音号手。

剧情主要是从久美子的视角讲述社团为了冲击全国金不断努力以及部员们之间的故事。

可能读者会觉得，这是一部老套的以社团为主题的作品罢了。可是，我想说，就是这样看似平凡的作品，却无比真实。使我不禁想到了我高中的竞赛经历。

下面，我将会联系作品和我的经历来分析剧中人物和现实当中这类人物。如果读者没有看过作品也没有关系，只要多想想生活当中是否有这样的人物，一定也会有所感悟和理解。

人物

斋藤葵

斋藤葵（斎藤 葵（さいとう あおい），声：日笠阳子）

三年级生，使用乐器是次中音萨克斯管。与久美子是总角之交，两人独处时久美子会称呼其“小葵”。为了考试而上补习班，最后选择退出了管乐团。

中考失利没有考到理想的学校才来了北宇治高中，不想升学考试再次失利，因此上了补习班，当吹奏乐部要加练时常常早退。因发觉时间有限无法兼顾课业和社团活动而选择退社，直接导致部长晴香情绪崩溃：退部什么的，我不明白啊！虽然本人退社了，但没有放弃音乐，转行做了歌星还学会了些打击乐。

最初投票决定社团是否以参加全国大赛为目标的时候，投了唯一的反对票。

从北宇治毕业后，考入了理想的私立大学。在那里与晴香再次相遇，之后一起加入了吹奏部。

斋藤葵无疑是存在感比较低的一个角色，但确实我们生活中很常见的一类人。葵无疑是热爱管乐的，但是升学的压力迫使她放弃了自己的所爱，但好在最后能够考入理想大学，不失为一个相对圆满的结局。在我多年的竞赛生涯中，这样的人可能是见的最多的，他们其中不乏有热爱竞赛的，在种种因素的影响下，他们选择了一时的放弃，抑或永远离开竞赛。

很多时候，我们说他们并非真正热爱，但是，我想说，人和人的经历、家庭背景等条件是不一样的，我们没有真正经历他人所经历的，也不能肆意评价他人的选择。我选择了竞赛，固然有我热爱的因素，但不可否认也有学校，老师，家庭的因素，倘若我没有进入外国语，没有接触到竞赛，又何谈选择呢？所以，我一向是感谢过去支持我的所有人的，没有他们，毫无疑问，我的人生不会这样精彩。

葵是大部分普通人的写照。他们有着自己所爱，却又因现实割爱，个中痛苦，只有他们自己知道。急流勇退，弯道超车何尝不是一种明智选择？

田中明日香

田中明日香（田中 あすか（たなか あすか），声：寿美菜子）

三年级生，使用的乐器是粗管上低音号。副乐团长，负责带领乐团低音分部的职务。统率能力十分高，但并不想成为乐团长或副乐团长。曾说连当上副乐团长都是被百般请求才愿意担任副乐团长一职。一直在乐团的冲突中保持中立，从不讲自己的想法。红框眼镜为其标志。

父母在2岁时离异，小时候时收到了父亲寄来的自用上低音号和笔记，因此学习了吹上低音号，但也被其母亲所厌恶，以答应保持成绩不退步来维持吹上低音号的承诺。当得知全国大会的评委有其父亲，为了见上父亲一脸而努力带领管乐团冲击全国大会，但也因此激怒了母亲而被迫暂时退出社团活动，最终在模拟考中保持水平而与母亲谈判得以继续。

“她表现得太完美了，完全分不清哪些是她的伪装，哪些是她的真实想法。”——秀一

“明日香学姐的伪装太过严实，要剥下她伪装的面具，我实在无能为力。”——久美子

田中明日香可以说是理想的葵，不仅在吹奏乐上实力强大，在学习上更是恐怖（全国前 30 的水平）。但是明日香可以说是全局中背负最多的，受伤最多，却又最不肯展现真实自己的角色。为了能见到自己父亲，即使被母亲反对也同时坚持了吹奏乐和学业，并且将社团打理得井然有序。这里说一个维基中没有提及的情节：母亲为了明日香的学业强迫明日香退社，在明日香表达反对后，当着老师和校长的面抽了明日香一个耳光，但随即意识到自己又情绪失控而自责。但是，明日香的反应异常冷静，反而原谅母亲并向老师请假，并带着母亲目不斜视地从目睹一切的久美子面前走过，并在久美子提起时一带而过。这段情节在动漫中表现得淋漓尽致，甚至观众都没反应到明日香会挨这一耳光，更惊叹与明日香的超过成人的成熟和冷静。

但是，对应到生活中，这种人反而是最少的。既要有实力，又要有强大的内心。我至今还从未在现实中遇到。在我看来，成为像明日香一样的强者意味着要承受普通人难以承受的压力和痛苦，是否要成为这样的人，见仁见智。但是，能否成为这样的人，恐怕不是靠想与不想决定的。

小笠原晴香

小笠原晴香（小笠原 晴香（おがさわら はるか），声：早见沙织）

三年级生，使用的乐器是上低音萨克斯管。乐团长，并为萨克斯管分部的部长。性格温柔亲切，作为乐团长包容整个乐团。由于性格柔弱，所以曾推选明日香担当部长但没被接受，对自己作为团长自信心不足。

当作为部长站在大家面前时会努力的挺起胸膛大声说话，可一旦丧失自信就会缩成一团。

因为经常落泪在部员内也有“雨女”的爱称。

優しいなんて褒めるところがない人に言うことセリフでしょ（温柔什么的，就是给没有值得称赞优点的人的台词不是吗？）——小笠原晴香

明日香、私ソロ吹くことになったから、しっかり支えてね（明日香，我要进行独奏，要认真的支持我哦。）——小笠原晴香

晴香作为社长却因为性格原因长期大权旁落于明日香手中，以至于一度陷入自我怀疑而说出惊世名言：“温柔什么的，就是给没有值得称赞优点的人的台词不是吗？”但是当明日香因为种种因素无法主持吹奏部时，第一个站出来了却是晴香，并在公演中完美地完成了《宝岛》的低音萨克斯 solo。

这种人在生活中也不少见，他们平日里可能平平无奇，但是总能在关键时候站出来稳定局面。这不是因为他们天性如此，而是平日里他们在我们看不见的地方默默努力付出。可能一时没有获得人们的注意，但只有在最需要的时候，才能感受到他们的可贵。成为晴香这样的人无疑是一个不错的选择。

中世古香织

中世古香织（中世古 香織（なかせこ かおり），声：茅原实里）

三年级生，使用的乐器是小号。乐团小号分部的领队。被晴香喻为管乐团的玛丹娜，受很多人仰慕。一直希望能在音乐会上独奏，却因各种因素屡次没有被选中。当众与丽奈比试之后，被泷老师问是否想担任独奏，但最后决定让给实力较强的丽奈。

性格稳重，很有大小姐的风范，不喜争锋。对社团活动也十分热心，憧憬着明日香的天赋才华，自己也每日刻苦的练习技艺。 在泷昇顾问没有来到吹奏乐部时，吹奏乐部几乎名存实亡，部员们每天的活动都是摸鱼聊天，而香织是少属不愿随波逐流，独自练习的成员。

在二年级时看到毫无上进心的三年级部员对希美优子等部员施行冷暴力时，主动向前辈低头，请求他们不要再无视一年级的新生们。为了缓和部内沉闷的气氛，愿意主动让出首席的位置，把机会给那些没有实力的前辈。

香织是作为部长小笠原晴香的左臂右膀，能够调和田中明日香与部长的关系。可以说，香织真的是北宇治最温柔（完全褒义，不是上文含义）的前辈。她的所有举动都是为了最大化社团的利益。在社团风气差时不随波逐流坚持练习，并积极为后辈争取权益，在社团风气蒸蒸日上时没有选择用前辈的地位和实力拿下 solo 名额，而是敢于承认自己实力不如后辈。

香织这一形象虽然看起来没有难度，可在现实中，又有多少人能够做到？

在付出与索取面前，大把的人选择索取；

在努力与安逸面前，大把的人选择安逸；

在集体与个人面前，大把的人选择个人；

在实力与资历面前，大把的人选择资历。

而香织不一样，她选择了集体，选择了努力，选择了付出，最后甚至让出了自己努力的成果。只为了能让社团保证公平，让自己内心安心。

我个人非常认可并且努力追寻做这样追求公平正义，不用权利谋取私利的人。

吉川优子

吉川优子（吉川 優子（よしかわ ゆうこ），声：山冈百合）

二年级生，来自管乐强校市立南中，使用的乐器是小号。非常仰慕学姐香织。对丽奈纯熟的小号吹奏能力十分嫉妒，时常以上辈的身份打压。曾经怀疑丽奈借与泷老师相熟而获得竞演比赛的独奏机会，而迫使泷老师进行第二次小号独奏选拔。为了让香织学姐获得独奏机会，而偷偷在第二次独奏选拔前拜托丽奈把这个机会让给香织，但被丽奈拒绝。

将霙视为朋友，也知道霙有心灵创伤，并希望作为希美的替代。

在三年级毕业退出后被指定担任新团长。

优子给大部人的第一影响是无脑追求前辈的后辈形象，在动漫刚开始的时候风评较差。可随着剧情的发展，我们能够更加客观地看到一个立体的优子。有人说这部番中没有反派，我深以为然。从优子角度来看，多次帮助自己的前辈被后辈抢去 solo 资格难免打抱不平。她当然知道反对实力至上无疑是没有出路的，即便如此，她还是选择了为前辈说话，哪怕与大半社团为敌。可谓人人骂优子，可人人又都想有一个这样永远支持你的朋友。

在当选部长后，优子更是用自己的能力解决了部里的众多问题。这样一个有实力，有义气的人怎能不让我们喜欢呢？

铠冢霙

强烈建议和后文伞木希美结合来看。

铠冢霙（鎧塚 みぞれ（よろいづか みぞれ），声：种崎敦美）

二年级生，来自管乐强校市立南中。故事的第一年曾是北宇治高中管乐团中唯一使用双簧管的人。

初中时，因为性格阴沉而没有朋友，后来被希美邀请加入管乐团。视希美为很重要的朋友，但也意识到自己只是希美众多朋友其中一员。初中三年级的时候，希美向霙说“入读高中之后，一定要取得金奖”。但后来希美却退出了管乐团，而自己竟然是透过希美其他朋友得知。霙感到自己对希美的友谊竟如此薄弱。以致开始无法面对希美，深怕看到自己以为的真相。对希美的恐惧已经到“光看就想呕吐”的地步。只好将乐器视为与希美唯一的联系，继续留在管乐团。

以为优子接近自己是因为看自己可怜，所以不视其为朋友。后经过与优子和希美的对话解开心结。

在剧场版中揭露，其双簧管实力已强至会无意识的顾虑配合希美的长笛，但此举导致合奏出现断层。

强烈建议看一下 wiki。

很喜欢的一个角色，因为是“三无”。

铠冢霙和伞木希美的故事在剧场版《利兹与青鸟》中有详细描写，高分文艺片。

铠冢霙作为内向的人，在伞木希美邀请进入吹奏部前几乎没有朋友，也因此伞木希美作为最重要的人，起初一切的演奏都是在为伞木希美而奏，但在初中失利后开始厌恶比赛。在经历很多事情后最终发自内心爱上双簧管和音乐。天赋异禀，唯二进入音大的人。

铠冢霙类的人物在竞赛中也不少见。不少人进入竞赛不是发自内心的喜爱，甚至只是为了功利的目的，但是他们天赋异禀，依然取得不错成绩。但是最终，他们发自内心爱上了算法，不再为了功利而练习，而是为了自身的爱好而努力。成为这种人真的是我内心的向往啊，只可惜大部分人难以摆脱功利，我也不例外。

伞木希美

伞木希美（傘木 希美（かさき のぞみ），声：东山奈央）

二年级生，来自管乐强校市立南中，使用的乐器是长笛。一年级时，满腔热诚地与同样来自管乐强校市立南中的朋友一起，想改革弱小的北宇治高中管乐团，但最终因为忍受不了当时的顾问采取不问实力只按辈份来选拔参赛成员的方针，以及高年级生不认真练习的态度而退出了。

将明日香视为特别的存在，一直不断希望借由明日香的准许回到管乐团。在泷老师成为顾问并改革之后希望返回管乐团，帮上明日香的忙。

与霙是国中好友。但由于自身拥有许多朋友加上未将退团一事告知霙。以致霙以为自己从不受到重视，导致她十分严重的心结，希美却一直没有察觉。而这也是明日香不希望希美回乐团的主要原因。最终和霙解释清楚后解开了霙的心结，也最终得到允许回到乐团。

“才能”远低于霙。两人之间复杂的情感导致第二次全国大赛自选曲中，两人乐声应答出现违和。

上面的 wiki 不太行啊。大家看看就好。

她们既是对方的莉兹，也是对方的青鸟。曾经伞木希美是铠冢霙的青鸟，带她走进了音乐的世界不再孤独；但现在铠冢霙是自己的青鸟，最好的爱应该是放手，她有属于自己的更大的天空。

萌娘 win 了。

伞木希美啊。痛，太痛了。

把霙带入管乐，却发现霙的实力远在自己之上。最终认清现实，选择考入普通的大学。

op 当中一句迫伞台词：“如果努力的尽头就是奇迹”

很现实的一个问题：努力的尽头是奇迹吗？

很大概率不是的。希美就是这样一个人，努力不比任何人少，成功却不比任何人多。

这样的人，生活中也不少。如何面对失败，不同人的选择却不一样。如果缺少天赋，换条赛道不是一种明智的选择。

高坂丽奈

高坂丽奈（高坂 麗奈（こうさか れいな），声：安济知佳）
一年级生，使用的乐器是小号。与久美子就读同一间初中，父亲为知名小号演奏家。从小于父亲要求下开始吹奏小号，上高中决定在管乐团继续吹奏下去。其演奏实力在高中生中出类拔萃，自己也对音乐相关事务要求严格，但不善于人际关系。暗恋泷老师，也因此无法忍受别人说他的坏话，但同时亦对久美子有超越一般同性朋友的情感。曾说过“为了成为与众不同的人，所以我吹小号”。在小说第三本中从泷老师口中得知泷老师前妻一事。

私、特別になりたいの、他の奴らと、同じになりたくない。だから私はトランペットをやってる、特別になりために。（我想成为特别的人，不想和其他人一样。为此我选择了小号，不愿随波逐流。）——高坂丽奈

丽奈是一个比较好分析的人物，因为她单纯，单纯到只想成为特别的人，可这“想成为特别的人”十分其实并不特别。她吹奏小号是否是真的因为热爱，抑或只是想要变得特别。不同人有不同看法。

在现实中，我比较害怕用丽奈头像的人。因为潜意识里认为这些人会为了目标不择手段。我喜欢这样纯粹，追求“特别”的人，可我又害怕他们的歇斯底里。相比之下，铠冢霙无疑是更加专注于音乐。

以下引用京吹学报

丽奈毫无疑问是强大的，压倒性的强大，相对于她来说大部分的吹奏部员都是弱小的。整个久三年，她不断在用话语和行动诠释，她一点也不在乎实力不如她的人是怎么想的，所有弱者的痛苦、不甘、难过在她看来都是无病呻吟。

在首席会议上，有声部长提出有落选了的人在闹情绪，丽奈回以怒斥 “随他们去”；在三人的干部会议上，秀一说丽奈管的太严了，丽奈回以 “实力不如我的人不配对顾问不满”；在石造的堤防上，久美子说这次我没办法完全信任老师，丽奈回以 “那你不配当部长”。

但是，即便如此，我依然赞赏每一个为了梦想不顾一切的人。但是，想必他们根本不会在乎他人的看法，深处自己的世界，怡然自乐。

黄前久美子

黄前久美子（黄前 久美子（おうまえ くみこ），声：黑泽朋世）

一年级生，使用的乐器是粗管上低音号。因为憧憬水手服而进入北宇治高中就读。初中时是管乐团的成员，进入高中后同样加入管乐团。较为没有主见，有着想说什么就说什么的习惯，被丽奈说“久美子的性格真是糟糕呢”。以前曾在东京居住过，会使用该地区罕见的标准语。

“うまくなりたい、うまくなりたい！（想要变得更好）”

我想要吹的更好

久美子作为主角似乎没有什么特别突出的特点，几乎每一方面都有比她更好的。可是他是我最为感同身受的一个角色。

恐怕她也是很多人最感同身受的角色。

我们可能也像久美子一样，有一些特长，有一些朋友，有过高光，又有过黯淡；久美子也和我们一样，为了学业倍感压力，为了金奖努力练习，一样有过挫折，一样想要变好。她就是我们普通人的真实写照，从初入社团的青涩到当部长时的干练。千言万语敌不过一句“想要变得更好”。

虽然直到毕业也有这样那样的缺点，但是她只是一个高中生，我们也不过是一个个普通的人。但是只要心怀“想要变得更好”就不会止步。

曾几何时，我也想要成为像霙一样天赋异禀的人，可渐渐，我意识到与其希望自己天赋异禀，不如怀着想要变好的心投入到努力当中。

总结

时间有限，只写了几个主要的角色，很多新角色包括第三季即将登场的黑江真由都没有写，以后大概可能会更新。

《悠风号》作为群像剧，人物众多，性格各异。即便如此，我们也不必认为某个人物和自己很像而去模仿，每个人都是独特的存在，学习他们身上的优点并在生活中不断提升自我难道不是更好吗？你想活出怎样的人生完全取决于你自己！

愿我们都能活成我们心目中的样子！

2023 年终总结

2024 年了捏，写一个 2023 年的年终总结也是有必要的。本来打算是百度之星国赛完了写，结果紧接着的考试周没有时间。考完试想着成绩出了再一起写，前一天成绩全部出了，我们的年终总结也就可以动笔了。

关于上半年的一些事情在暑假回忆录中就已经很详细地写过了，所以这份年终总结主要写一些 10 月之后的事情。

十月

十月貌似没什么特别的事情，基本都是在学校上课什么的。这里不妨说说日常吧。平时基本除开高数的课会提前一个小时到教室外，别的课程都是按部就班去上课。周三和周六有 ACM 的集训，基本是一套区域赛题目，一般可以做 4 到 5 道题。平时没事就去图书馆或者打打音游。真是朴实无华的日常呐。

给大家看看十月的黑胶。

十一月

十一月比较有意思的事情就是 ICPC 南京赛区了。虽然结果有点难绷。

南京站前我们队伍对于拿牌子还是很有信心的，平时模拟赛做的还行，甚至在省赛拿到了二等奖。怀着这样的心情，我们登上了去往南京的飞机。

不是这架，将就着看

第一天晚上和 lhm 去瞎逛，结果马路上看到这个东西。

于是晚上吃了这个。

然后去看了看南京长江大桥，夜景还是很不错的。

第二天是签到和热身赛。

这里放几张照片，只能说南航还是有实力的。

第三天是正式赛，但是结果三个人不知道怎么回事没一个人在线，直接打铁。😥😥😥

十二月

十二月还不错。

首先是 ACM 选修课的校赛，运气不错 10 题拿下第二。

然后是月底的百度之星国赛。

第一天随便去玩了玩。

地坛十分冷清，但是南边的河里有不少人滑冰。

第二天正式赛，每个题都觉得不难，但是过题过得非常慢，最后拿了个铜首。绷。主办方甚至精心准备了铁奖。

第三天就是开玩。

去看了元旦的升旗，放和平鸽还是比较震撼的。

晚上去三里屯玩了玩，各方面都给了我很大的震撼。

最后一天就回学校了。CR400 确实快。

一月

各种考试。除开英语都比较游刃有余，英语属实玄学，甚至难以估分。

考完试玩了玩雀魂，太费脑子了。

然后就回太原了。

然后去高中看了看老师，出来玩了玩。

关于三个人吃饭，还没吃却绷不住这件事。

服务员：给大家介绍一下……

我们仨：微笑 -》 绷 -》 互相看一下 -》 开怀大啸

饭后，rx：你这顿吃得开心吗？ 我：那可太开心了，没吃就已经开心了。

你可能很奇怪，但事实就是这样。

前一天出了成绩，你怎么知道我 C 语言满绩了？

除了英语都能接受，均绩 4.1。希望能绷住。

总结

过去一年还是很充实的。希望下一年能更好。志存高远，脚踏实地。

一个积分后求导的小结论

引入

做高数题的时候会遇到一类题目：对一个变上限函数求导。例如

这是显然的。

但如果积分函数中加入了 $x$，例如：

问题就不在那样显然了。

我初次遇到这题把它拆成导数定义来做，结果算错了。于是我在想有没有一种结论可以省去讨论，于是又了今天的这篇文章。

推导

考虑一个一般的情况。求以下函数：

我们令 $F(x) = \int f(x) \mathrm{d}x$。

根据导数的定义，有

根据微积分基本定理有

板刷 Atcoder Educational DP Contest 总结

前言

最近为了水 ACM 选修课积分, 于是写了一下 OJ 中的 DP 提高题, 发现是 AtCoder 上的题目. 做下来收获颇丰, 所以写篇总结.

总结会写一些我在写的时候花时间比较多或者看了题解或者有收获的题, 代码选择性地放.

正文

J Sushi

题目链接

难在优化状态, 发现答案与盘子的顺序无关, 设计状态 $f_{i, j, k}$ 表示有 $i$ 个盘子有 $1$ 个寿司, 有 $j$ 个盘子有 $2$ 个寿司, 有 $k$ 个盘子有 $3$ 个寿司全部吃光的期望次数.

状态转移方程推出来是

一个易错点是循环顺序是 $k$, $j$, $i$. 读者可以思考一下原因.

R Walk

题目链接

设计状态 $f_{i, u, v}$ 表示长度为 $i$ 的从 $u$ 到 $v$ 的路径个数.

转移方程

这东西很像矩阵乘法, 可以用矩阵快速幂优化.

U Grouping

题目链接

枚举子集的方法

1
2
3

for(int i = now; i; i = (i - 1) & now){
	f[now] = max(f[now], f[now ^ i] + solve(i));
}

V Subtree

题目链接

换根 DP. 但是模数不一定为质数, 所以记录前缀积和后缀积解决.

W Intervals

题目链接

好题.

按区间右端点排序, 只有考虑到 i 时, 计算所有右端点为 i 的区间对答案的贡献, 可以做到不重不漏. 而且可以发现, 这样计算只需要考虑最右边选的点的位置.

令 $f_{i,j}$ 表示考虑到 i, 最后一个点在 j 的最大值.

写出状态转移方程发现可以把 $f$ 放在线段树上. 很好的一道题.

Y Grid 2

题目链接

带障碍的走方格. 一开始想离散化做, 发现代码困难遂看题解.

设计状态 $f_{i}$ 表示从开始到障碍 $i$ 的位置且不通过障碍的方案数.

Z Frog 3

题目链接

斜率优化 DP 模板题.

NEUOJ 2383 流行的字符串 题解

题目

分析

一眼感觉可以用线段树维护, 难点在于需要存储哪些数据.

受 KMP 算法的启发, 若某个节点覆盖区间的后缀相同, 则可以存储这个后缀在字符串 $S$ 当中的位置. 此外还要维护当前区间的答案数.

再考虑如何添加字符串. 可以把叫加入的字符串作为线段树修改的参数(实际代码中使用的是队列, 应为数字更好维护). 若当前区间被覆盖, 就暴力逐个加入字符, 然后修改后缀在 $S$ 的位置. 转移可以用 KMP 的方法, 具体来说是预处理出失陪数组, 再预处理出 $to[i][j]$ 表示在第 $i$ 个字符后加入 $j$ 的转移, 具体可以参考代码.

再考虑如何下传标记. 若未传递字符串长度大于等于 $|S|$, 则直接修改即可. 否则暴力加字符, 若子节点区间的后缀相同, 可以即时修改后缀在 $S$ 的位置.

再考虑如何询问. 基本是正常的线段树操作, 一点不同在于若当前区间答案未知需要分别询问两个子节点, 复杂度可能会受影响, 但是调用层数不会很高(大概). 但是这题时限很宽, 所以还是可以过的.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#include<queue>
#include<map>
#include<bitset> 
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define frep(i,a,b) for(int i=a;i<(b);++i)
#define drep(i,a,b) for(int i=a;i>=(b);--i)
#define mid ((l + r) >> 1)
#define ls (p << 1)
#define rs (p << 1 | 1)
typedef long long ll;
typedef unsigned long long ull;
#define Maxq priority_queue<int,vector<int>,greater<int> >
using namespace std;
int mylog(int a) {
	int ans=0;
	if(a&0xffff0000) {
		ans+=16;
		a>>=16;
	}
	if(a&0x0000ff00) {
		ans+=8;
		a>>=8;
	}
	if(a&0x000000f0) {
		ans+=4;
		a>>=4;
	}
	if(a&0x0000000c) {
		ans+=2;
		a>>=2;
	}
	if(a&0x00000002) {
		ans+=1;
		a>>=1;
	}
	return ans;
}
inline int read() {
	register int a=0,b=0;
	register char c;
	c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')b=1;
		c=getchar();
	}
	while(c>='0'&&c<='9') {
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return b?-a:a;
}
const int MAXN = 1e5 + 10;
int to[30][30], fail[MAXN];
char str[30];
int len;
struct node{
	queue<int> q;
	int now, cnt;
}tree[MAXN << 2];
void build(int p, int l, int r){
	tree[p].cnt = 0;
	tree[p].now = -1;
	if(l == r) return;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	return;
}
void pushdown(int p, int l, int r){
	if(tree[p].now != -1){
		tree[ls].now = tree[rs].now = tree[p].now;
		while(!tree[p].q.empty()){
			if(tree[ls].q.size() >= len) tree[ls].q.pop();
			if(tree[rs].q.size() >= len) tree[rs].q.pop();
			int x = tree[p].q.front();
			tree[p].q.pop();
			tree[ls].q.push(x);
			tree[rs].q.push(x);
		}
	}
	else{
		while(!tree[p].q.empty()){
			if(tree[ls].q.size() >= len) tree[ls].q.pop();
			if(tree[rs].q.size() >= len) tree[rs].q.pop();
			int x = tree[p].q.front();
			tree[p].q.pop();
			tree[ls].q.push(x);
			if(tree[ls].now != -1) tree[ls].now = to[tree[ls].now][x];
			tree[rs].q.push(x);
			if(tree[rs].now != -1) tree[rs].now = to[tree[rs].now][x];
		}
		if(tree[ls].q.size() >= len && tree[ls].now == -1){
			tree[ls].now = 0;
			rep(i, 1, len){
				int x = tree[ls].q.front();
				tree[ls].q.pop();
				tree[ls].q.push(x);
				tree[ls].now = to[tree[ls].now][x];
			}
		}
		if(tree[rs].q.size() >= len && tree[rs].now == -1){
			tree[rs].now = 0;
			rep(i, 1, len){
				int x = tree[rs].q.front();
				tree[rs].q.pop();
				tree[rs].q.push(x);
				tree[rs].now = to[tree[rs].now][x];
			}
		}
	}
	if(tree[ls].now == len) tree[ls].cnt = (mid - l + 1);
	else if(tree[ls].now != -1) tree[ls].cnt = 0;
	else tree[ls].cnt = -1;
	if(tree[rs].now == len) tree[rs].cnt = (r - mid);
	else if(tree[rs].now != -1) tree[rs].cnt = 0;
	else tree[rs].cnt = -1;
	return;
}
void pushup(int p, int l, int r){
	if(tree[ls].now == tree[rs].now) tree[p].now = tree[ls].now;
	else tree[p].now = -1;
	tree[p].cnt = (tree[ls].cnt < 0 || tree[rs].cnt < 0) ? -1 :tree[ls].cnt + tree[rs].cnt;
	return;
}
void add(int p, int l, int r, int x, int y, queue<int> s){
	if(x <= l && r <= y){
		if(tree[p].now != -1){
			while(!s.empty()){
				if(tree[p].q.size() >= len) tree[p].q.pop();
				int x = s.front();
				s.pop();
				tree[p].q.push(x);
				tree[p].now = to[tree[p].now][x];
			}
		}
		else{
			while(!s.empty()){
				if(tree[p].q.size() >= len) tree[p].q.pop();
				int x = s.front();
				s.pop();
				tree[p].q.push(x);
			}
			if(tree[p].q.size() >= len){
				tree[p].now = 0;
				rep(i, 1, len){
					int x = tree[p].q.front();
					tree[p].q.pop();
					tree[p].q.push(x);
					tree[p].now = to[tree[p].now][x];
				}
			}
		}
		if(tree[p].now == len) tree[p].cnt = (r - l + 1);
		else if(tree[p].now != -1) tree[p].cnt = 0;
		else tree[p].cnt = -1;
		return;
	}
	if(y < l || x > r) return;
	pushdown(p, l, r);
	add(ls, l, mid, x, y, s);
	add(rs, mid + 1, r, x, y, s);
	pushup(p, l, r);
	return;
}
int query(int p, int l, int r, int x, int y){
	if(x <= l && r <= y && tree[p].cnt >= 0) return tree[p].cnt;
	if(y < l || x > r) return 0;
	pushdown(p, l, r);
	int res = query(ls, l, mid, x, y) + query(rs, mid + 1, r, x, y);
	pushup(p, l, r);
	return res;
}
int main(){
	scanf("%s", str + 1);
	len = strlen(str + 1);
	fail[0] = -1;
	rep(i, 1, len){
		for(int j = fail[i - 1]; j != -1; j = fail[j]){
			if(str[j + 1] == str[i]){
				fail[i] = j + 1;
				break;
			}
		}
	}
	rep(i, 1, len){
		rep(c, 'a', 'z'){
			if(c == str[i]){
				to[i - 1][c - 'a'] = i;
			}
			else{
				to[i - 1][c - 'a'] = to[fail[i - 1]][c - 'a'];
			}
		}
	}
	rep(c, 'a', 'z'){
		to[len][c - 'a'] = to[fail[len]][c - 'a'];
	}
	int n = read(), q = read();
	while(q--){
		int op = read();
		if(op == 1){
			int x = read(), y = read();
			char str[30];
			queue<int> q; 
			scanf("%s", str);
			int l = strlen(str);
			frep(i, 0, l){
				q.push(str[i] - 'a');
			}
			add(1, 1, n, x, y, q);
		}
		else{
			int x = read(), y = read();
			int ans = query(1, 1, n, x, y);
			printf("%d\n", ans);
		}
	}
	return 0;
}

总结

这题细节比较多, 写起来比较头大. 大家看个乐呵就好. 想提交可能也比较困难, NEUOJ 常年不开放注册. 可以和我的代码对拍.

《你的名字。》黑胶音乐推荐

前言

昨天鼠鼠收到了在叔叔那买的《你的名字。》原声带，所以借机写个歌推吧。

说到这盘黑胶，就不得不提《你的名字。》这部空前绝后的作品。顺便一提，《你的名字。》已经是 7 年前的作品了，时间就是流逝得这么快。

我第一次了解到这部作品是通过 OI。想必 OIer 都还记得，当年有人 P 了这么一个图片。

这幅图如今可能已经是时代的眼泪了。但是这幅图对于刚学 OI 的我还是有一点小小的震撼。图片右面“自主招生”如今看来是一个很久以前的词。谁能想到几年后由于自主招生政策的取消，OI 已经越来越成为一种兴趣而非升学的一种途径。很难评价这对于信息学人才的培养是有利的还是不利的。话说我在找这陈年老图的时候发现萌娘百科甚至有一个页面来介绍 OI 梗，感兴趣的读者可以前往链接。

回到作品本身，君名可谓是一部最能体现新海诚创作哲学的作品，平凡的人物，平常的场景，细腻的画面，感人的情节，以及人与人的羁绊在这部作品当中展现得淋漓尽致。不少观众都是从这个作品开始了解新海诚，以至于了解动漫。

这部作品的配乐由 RADWIMPS 担当，这个乐队也担当了新海诚后续作品《天气之子》和《铃芽之旅》的配乐工作。这个在当时处于巅峰的乐队在这部作品的配乐方面给出了令人满意的答卷。可以说，贴合情节的配乐让《你的名字。》这个本就优秀的作品更上了一步台阶。其中《前前前世》MV 在 YouTube 的点击量已经突破 3 亿，我也是从这部 MV 接触到君名的 OST。所以我一直希望入手君名 OST 的黑胶，由于市面盗版充斥等原因，错过了日版的黑胶。但是很幸运的是这张专辑国内引进了，于是我入手了中国唱片（上海）公司发行的君名 OST，也就是我们今天要谈论的这张黑胶。

关于这张黑胶的音质，我由于设备原因没法给大家展示，大家可以到 b 站 up 主混交林上传的视频中领略，这个 up 通过内录的方式获取了黑胶原声，理论上是最接近黑胶原声的。附上链接。

01 夢灯籠

《夢灯籠》作为片头，很好地将观众带入了作品营造的轻松梦幻的氛围。这首歌的歌词也非常具有感染力，表达了梦想、回忆和相遇的主题，以及主人公之间那种特殊的纽带。

08 前前前世 (movie ver.)

这个可以说是我比较喜欢的一首曲子，同时它也被当作君名的主题曲。这首歌在电影中出现在两主人公意识到交换身体并且说出

我在梦中和那个男生

我在梦中和那个女生

交换了身体

这句台词后响起，并且快速地展现了三叶和泷交换身体后的种种细节。

而歌词

君の前前前世から僕は 君を探しはじめたよ

从你的前前前世开始 我就一直寻觅着你的踪迹

そのぶきっちょな笑い方をめがけて やってきたんだよ

追寻着你那略显笨拙的笑容 终于找到了你

也暗示了故事的结局不会是个令人伤心的结局。

这里还是推荐大家可以看一下原版 MV，这里附上油管链接。

24 スパークル (movie ver.)

《火花/スパークル》出现于电影泷和三叶相见又分离之后，泷想办法回忆三叶名字却发现怎么也想不起来时。作品在这里逐渐令人揪心。这里更是出现了名台词

重要的人

不能忘记的人

不想忘记的人

随后 BGM 响起，直接泪目。

27 なんでもないや (movie ver.)

片尾曲，却也是我最喜欢的一曲，也是我在 OSU 当中玩的做多的谱子之一。一开始打这张谱，会发现总是快，听多了就会明白这首曲子更多的是想描绘一种日常而非某种宏大的叙事，自然要求准确而非急切。

歌曲的标题本身就是“没什么”的意思，它的歌词提供了对日常的细微瞬间和人际关系的深入哲学考察。而往往最打动人心的不是宏大的场面，而是最珍贵的日常。

总结

第一次写歌推，写得不好。我更多地希望结合个人的经历来谈这个 OST，如果只是为了描述音乐，不如直接听。音乐的旋律本身固然重要，但更重要的还是其背后的故事。

在写歌推的过程中又看了几次君名，有了更深的理解，但过去一个人傻呵呵看君名的时光却一去不返。时间就是这样，一晃眼七年过去，懂得多了，疑惑更多，反而想回到过去一无所知但总觉得无所不知的日子，可谁又能说现在的自己不是一无所知呢？

还有很多想说，但是不太想说太多空洞的文字。还是留给大家遐想的空间，读到这里的读者不妨回忆一下自己七年前的生活吧，一定会发现自己的经历比音乐和电影还更要打动人心。不妨也分享一下自己的过往，不要未来只记得曾有人和事不能忘记，不想忘记。

2021 ICPC Asia Taiwan Online Programming Contest 题解

训练题, 场上做了 ABDFG. 目前补了 CJ. 比较可惜是 J 题是签到题, 放在最后没来得及看, 经验问题.

题目链接: https://codeforces.com/group/nzwf9tsg2d/contest/477278

A Olympic Ranking

分析

一眼顶针

代码

GitHub/a.cpp)

B Aliquot Sum

分析

求因数和, 可以对每个数枚举因子, 复杂度 $O(n\sqrt{n})$.

如果用筛法, 对于每个数筛它的倍数, 可以做到 $O(n\log{n})$. 证明需要用到调和级数的增长近似于 $\ln(n) + C$, 其中 $C$ 为 欧拉常数.

代码

GitHub/b.cpp)

C A Sorting Problem

分析

考场上往这个方向想, 但没深入, 就先做后面了. 还是生疏了.

具体做法是记录每个数的位置, 问题转化为每次操作交换相邻两数, 使得数组单调递增. 经典求逆序对数量. 使用归并排序或者树状数组即可.

代码

GitHub/c.cpp)

D Drunk Passenger

分析

这道题花了不少时间, 还是太菜了.

考虑 DP. 假设当前已经坐了 $i$ 个人, 一个显然的结论是 $2$ 到 $i$ 的座位已经坐了人, 而 $i + 1$ 到 $n$ 的座位在当前状态是等价的, 还有第一个座位比较特殊. 所以定义 $f_i$ 表示坐了 $i$ 个人后本就不应坐人的座位 (也就是 $i + 1$ 到 $n$ 的座位) 坐人的概率, $g_i$ 表示坐了 $i - 1$ 个人后第一个座位坐人的概率. 有如下转移:

当然, 你也可以推式子. 用题解的话说就是

推出答案之數學式子 $\frac{n}{2n - 1}$ 直接算答案。

~台湾的题解挺有意思.~

代码

GitHub/d.cpp)

E Eatcoin

分析

python 题.

首先求自然数五次方和公式, 可以用拉格朗日手推, 也可以写前几项高斯消元.

然后二分法求最小的天数.

代码

没有, 谁愿意拿 python 写写吧, 二分模板题.

F Flip

分析

和动态区间和最值很像.

维护区间左右端点的值, 从左和从右开始满足条件最长长度, 区间内答案数就可以用线段树维护了.

代码

GitHub/f.cpp)

G Garden Park

分析

正解 DP. 找官方题解吧.

我拿点分治做的, 模板题.

统计经过当前树根的答案数, 点分治换树根即可.

核心在于求经过当前树根的答案数. 对每个儿子 dfs, 找出所有单调递减和单调递增的路径数, 然后分别用乘法原理算贡献. 复杂度 $O(n\log^2{n})$.

代码

GitHub/g.cpp)

H A Hard Problem

分析

显然要分开每一位考虑. 然后要求满足条件的代价最小的染色方法.

跟所有的网络流题目一样, 然后它就是最小割了.

虽然对于会网络流的这是模板题, 但上次写网络流是一年前, 所以等于不会.

代码

以后补.

补好了.

GitHub/h.cpp)

G ICPC Kingdom

以后补

J JavaScript

分析

签到题, 判断是不是全是数字.

代码

GitHub/j.cpp)

高等数学

前言

高等数学课堂笔记及课后习题解答。

版本为东北大学数学系编写,高等教育出版社出版的《高等数学》.

第一章 极限与连续