#算法

分享算法思考、训练复盘与日常交流。

rail题解

temp 2026-10-2 21:58:49

#算法#题解

#include<bits/stdc++.h> #define int long long using namespace std; int n,L,s,S; char d; signed main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); freopen("rail.in","r",stdin); freopen("rail.out","w",stdout); cin>>n>>L>>s>>d; for(int i=1;i<=n;i++){ int x; cin>>x; S+=x; } if(s==0&&d=='L') d='R'; if(s==L&&d=='R') d='L'; int z; if(d=='R') z=s; else z=2*L-s; int ans=(z+S)/L-z/L; int t=(z+S)%(2*L); if(t<=L) s=t; else s=2*L-t; if(t<L) d='R'; else d='L'; cout<<ans<<" "<<s<<" "<<d; return 0; }

42 浏览0 点赞0 收藏0 评论

rankdiff题解

temp 2026-10-2 21:57:16

#算法#题解

水题不说废话了首先，这道题用到了排序但是需要用到多个参数如

id,rank

等这时可以用

sort

函数来解决sort(first,end,cmp);这么一个形式于是我想到了一个用STL的

pair

来解决这个问题pair<type1,type2> p;这里，我们可以用

.first

和

.second

来访问完整代码#include <bits/stdc++.h> using namespace std; const int N = 2e5+10; using LL = long long; const int inf = 1e9, N2 = 1e3, mod = 998244353; #define PII pair<int,int> int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; auto compare = [](int a, int b){ return a > b; }; PII a[N]; bool cmp(PII a,PII b){ if(a.first != b.first)return a.first > b.first; return a.second < b.second; } void solve(){ freopen("rankdiff.in","r",stdin); freopen("rankdiff.out","w",stdout); int n,p,q; cin>>n>>p>>q; for(int i = 0;i < n;i++){ cin>>a[i].first; a[i].second = i; } sort(a,a+n,cmp); cout<<abs(a[p-1].second-a[q-1].second); } int main(){ int _ = 1; while(_--){ solve(); } return 0; }

39 浏览0 点赞0 收藏0 评论

P12544 \[UOI 2025\] Boys and Girls

YIZHIYANG初来乍到 2026-9-27 8:21:21

#算法

P12544 [UOI 2025] Boys and Girls思路将问题转化为图论模型。把每个女孩看成一个点，每种男孩看成一条边：

男孩类型

i

对应边

(a_i,b_i)

；

边权为

c_i

。

题目要求选择最大的男孩集合，使得任意两个被选择的男孩至少喜欢同一个女孩。等价于：

在一张带权图中，选择一个最大权边集，使得任意两条边都有公共端点。

关键性质对于一个简单图，如果一个边集合中的任意两条边都有公共端点，那么这个集合只有两种情况。情况 1：所有边经过同一个点例如：1 /|\ / | \ 2 3 4所有边都有公共点

1

。这种情况对应：选择某个女孩，所有喜欢她的男孩都可以加入。设女孩

i

的贡献为：

sum_i=\sum_{e\ni i}w_e

直接统计所有女孩即可。情况 2：三角形例如：1 / \ 2---3三条边：

(1,2),(2,3),(1,3)

任意两条边都有公共点。因此还需要考虑所有三角形的边权和。三角形枚举直接枚举三个点会超时。采用经典的按度数定向。定义：

(deg_u,u)<(deg_v,v)

将边从较小的点指向较大的点。对于一个点

u

，枚举：

u\rightarrow v

然后枚举：

v\rightarrow x

如果存在：

u\rightarrow x

则：

(u,v,x)

构成三角形。复杂度设边数为

m=n

。统计所有星形：

O(n)

枚举三角形：

O(n\sqrt n)

空间复杂度：

O(n)

C++代码#include <bits/stdc++.h> using namespace std; using ll = long long; struct Edge { int a, b; ll c; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; int m = 2 * n; vector<Edge> e(n); vector<int> deg(m + 1); vector<ll> sum(m + 1); for (int i = 0; i < n; i++) { int a, b; ll c; cin >> a >> b >> c; e[i] = {a, b, c}; deg[a]++; deg[b]++; sum[a] += c; sum[b] += c; } ll ans = 0; for (int i = 1; i <= m; i++) ans = max(ans, sum[i]); auto cmp = [&](int a, int b) { if (deg[a] != deg[b]) return deg[a] < deg[b]; return a < b; }; vector<vector<pair<int,ll>>> g(m + 1); for (auto [a, b, c] : e) { if (cmp(b, a)) swap(a, b); g[a].push_back({b, c}); } vector<ll> vis(m + 1, -1); for (int u = 1; u <= m; u++) { vector<int> tmp; for (auto [v, w] : g[u]) { vis[v] = w; tmp.push_back(v); } for (auto [v, w1] : g[u]) { for (auto [x, w2] : g[v]) { if (vis[x] != -1) ans = max(ans, w1 + w2 + vis[x]); } } for (int x : tmp) vis[x] = -1; } cout << ans << '\n'; } return 0; }

49 浏览0 点赞0 收藏0 评论

P1850 [NOIP 2016 提高组] 换教室

YIZHIYANG初来乍到 2026-7-5 8:06:05

#算法

P1850 [NOIP 2016 提高组] 换教室知识点Floyd 最短路 + 概率期望 + 动态规划题意概括牛牛每节课原本在教室

c_i

，可以申请换到教室

d_i

。第

i

节课申请成功的概率为

k_i

，最多申请

m

节课。需要选择申请哪些课程，使相邻课程教室之间最短路长度总和的期望最小。解题思路首先，牛牛在两个教室之间一定选择体力消耗最小的路径，因此使用 Floyd 算法求出任意两个教室之间的最短距离。接下来考虑动态规划。申请第

i

节课程后，实际上课教室有两种可能：

以

1-k_i

的概率在教室

c_i

；

以

k_i

的概率在教室

d_i

。

相邻两节课之间的期望距离，只和这两节课是否申请有关，与更早的选择无关。因此可以将当前课程是否申请作为状态。设：

f_{j,0}

表示处理完当前课程，共申请了

j

节，并且当前课程没有申请时的最小期望体力值。设：

f_{j,1}

表示处理完当前课程，共申请了

j

节，并且当前课程申请了时的最小期望体力值。下面考虑从第

i-1

节课转移到第

i

节课。当前课程不申请当前课程一定在教室

c_i

。如果上一节课也没有申请，上一节课一定在教室

c_{i-1}

，新增体力值为：

dis(c_{i-1},c_i)

对应转移为：

f_{j,0}+dis(c_{i-1},c_i)

以

1-k_{i-1}

的概率在教室

c_{i-1}

；

以

k_{i-1}

的概率在教室

d_{i-1}

。

新增期望体力值为：对应转移为：两种情况取最小值。当前课程申请当前课程有两种可能：

以

1-k_i

的概率在教室

c_i

；

以

k_i

的概率在教室

d_i

。

c_{i-1}

，新增期望体力值为：

(1-k_i)dis(c_{i-1},c_i) +k_i dis(c_{i-1},d_i)

对应转移为：如果上一节课也申请了，那么相邻两节课分别有两种可能，共有四种组合。新增期望体力值为：对应转移为：由于每一层只依赖上一层，可以使用滚动数组将空间复杂度降为

O(m)

。最后枚举申请数量

0

到

m

。题目要求至多申请

m

节，因此答案是所有合法状态的最小值，而不是只计算恰好申请

m

节的情况。参考代码/* 题意：最多申请更换 m 节课，每次申请有独立的成功概率，求相邻课程教室间最短路长度总和的最小期望。思路：先用 Floyd 求任意教室间最短路。设 f[j][0/1] 表示处理完当前课程，申请 j 次，且当前课程不申请或申请时的最小期望。根据相邻两节课是否申请，计算两种或四种位置组合的期望。使用滚动数组优化空间。 */ #include<bits/stdc++.h> using namespace std; using ll=long long; const int N=2005; const int V=305; const int inf=1e9; const double INF=1e100; int c[N],d[N],g[V][V]; double k[N],f[N][2],h[N][2]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m,v,e; cin>>n>>m>>v>>e; m=min(m,n); for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=n;i++) cin>>d[i]; for(int i=1;i<=n;i++) cin>>k[i]; for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ g[i][j]=(i==j?0:inf); } } while(e--){ int a,b,w; cin>>a>>b>>w; g[a][b]=min(g[a][b],w); g[b][a]=min(g[b][a],w); } for(int t=1;t<=v;t++){ for(int i=1;i<=v;i++){ for(int j=1;j<=v;j++){ g[i][j]=min(g[i][j],g[i][t]+g[t][j]); } } } for(int j=0;j<=m;j++){ f[j][0]=INF; f[j][1]=INF; } f[0][0]=0; if(m) f[1][1]=0; for(int i=2;i<=n;i++){ for(int j=0;j<=m;j++){ h[j][0]=INF; h[j][1]=INF; } int up=min(i,m); for(int j=0;j<=up;j++){ h[j][0]=min( f[j][0]+g[c[i-1]][c[i]], f[j][1]+(1-k[i-1])*g[c[i-1]][c[i]] +k[i-1]*g[d[i-1]][c[i]] ); if(!j) continue; h[j][1]=min( f[j-1][0]+(1-k[i])*g[c[i-1]][c[i]] +k[i]*g[c[i-1]][d[i]], f[j-1][1] +(1-k[i-1])*(1-k[i])*g[c[i-1]][c[i]] +(1-k[i-1])*k[i]*g[c[i-1]][d[i]] +k[i-1]*(1-k[i])*g[d[i-1]][c[i]] +k[i-1]*k[i]*g[d[i-1]][d[i]] ); } for(int j=0;j<=m;j++){ f[j][0]=h[j][0]; f[j][1]=h[j][1]; } } double ans=INF; for(int j=0;j<=m;j++){

103 浏览0 点赞0 收藏0 评论

B4050 [GESP202409 五级] 挑战怪物

YIZHIYANG初来乍到 2026-5-17 13:50:34

#算法

#include<bits/stdc++.h> using namespace std; using ll = long long; bool f[100005]; void mkk() { fill(f + 2, f + 100005, true); for (int i = 2; i * i <= 100000; i++) { if (f[i]) { for (int j = i * i; j <= 100000; j += i) f[j] = false; } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); mkk(); int t; cin >> t; while (t--) { int h; cin >> h; int ans = 1e9; for (int k = 0; k <= 17; k++) { int p2 = 1 << k; if (h + 1 == p2) { ans = min(ans, k); } int x = h + 1 - p2; if (x >= 2 && x <= h && f[x]) { ans = min(ans, k + 1); } } if (ans > 1e8) cout << -1 << "\n"; else cout << ans << "\n"; } return 0; }

91 浏览1 点赞0 收藏0 评论

精华

什么是 NTT

YIZHIYANG初来乍到 2026-5-16 0:04:17

#算法

什么是 NTTNTT，全称是 Number Theoretic Transform，中文通常叫“数论变换”。它可以理解为：

在模意义下进行的 FFT，用来快速计算多项式乘法，也就是卷积。

普通的多项式乘法是

O(n^2)

的，而 NTT 可以把复杂度降到

sort

。NTT 解决什么问题假设有两个多项式：

A(x)=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}

B(x)=b_0+b_1x+b_2x^2+\cdots+b_{m-1}x^{m-1}

它们的乘积为：

C(x)=A(x)B(x)

其中

C

的第

k

项系数是：

c_k=\sum_{i+j=k}a_i b_j

这就是卷积。如果直接枚举

i,j

，复杂度是

O(nm)

。当

n,m

很大时会很慢。NTT 的作用就是快速求出所有

c_k

。NTT 和 FFT 的关系FFT 是快速傅里叶变换，它利用复数单位根来加速多项式乘法。NTT 的思想和 FFT 很像，但它不使用复数，而是在模意义下使用“原根”构造出来的单位根。可以粗略理解为：

FFT：在复数域里做快速变换；

NTT：在模质数意义下做快速变换。

NTT 的好处是没有浮点误差，结果天然是整数取模后的结果。为什么需要特殊的模数NTT 不能随便选模数。为了能做长度为

n

的 NTT，通常需要模数

p

满足：

p = c \cdot 2^k + 1

这样模

p

意义下才容易找到足够多的

2^k

次单位根。竞赛中最常用的模数是：

998244353 = 119 \cdot 2^{23} + 1

它的原根通常取：

g = 3

所以

998244353

非常适合做 NTT，最大可以支持长度不超过

2^{23}

的变换。NTT 的核心思想多项式有两种表示方式。第一种是系数表示：

A(x)=a_0+a_1x+a_2x^2+\cdots

第二种是点值表示：

(x_0,A(x_0)),(x_1,A(x_1)),\ldots

如果两个多项式都变成点值表示，那么乘法非常简单。因为：

C(x_i)=A(x_i)B(x_i)

也就是说，每个点对应的值直接相乘即可。所以多项式乘法可以分成三步：

把

A

和

B

从系数表示变成点值表示；

对每个位置做乘法；

再把结果从点值表示变回系数表示。

NTT 做的就是第

1

步和第

3

步。NTT 的大致流程设需要计算的长度为

len

，其中

len

是

2

的幂，并且要满足：

len \ge n+m-1

流程如下：

把两个多项式的系数数组补零到长度

len

；

对数组

A

做 NTT；

对数组

B

做 NTT；

每一项相乘，得到点值形式的

C

；

对

C

做逆 NTT；

得到答案系数。

复杂度是：

O(len\log len)

正变换和逆变换NTT 有两个方向。正变换把系数变成点值，逆变换把点值变回系数。正变换使用单位根

w

，逆变换使用

w

的逆元。最后逆变换结束后，还要把每一项乘上

len

的逆元。也就是：

a_i \leftarrow a_i \cdot len^{-1}

这一步非常重要，否则答案会整体多乘一个

len

。为什么 NTT 可以做到

O(n\log n)

NTT 和 FFT 一样，使用分治思想。一个多项式可以按照下标奇偶拆成两部分：

A(x)=A_0(x^2)+xA_1(x^2)

其中：

A_0

是偶数下标项组成的多项式；

A_1

是奇数下标项组成的多项式。

通过单位根的性质，可以把长度为

n

的问题拆成两个长度为

n/2

的问题。所以复杂度满足：

T(n)=2T\left(\frac n2\right)+O(n)

因此总复杂度为：

O(n\log n)

NTT 常见用途NTT 最常见的用途是快速卷积。也就是快速计算：

c_k=\sum_{i+j=k}a_i b_j

它经常出现在这些问题里：

多项式乘法；

生成函数；

组合计数；

分治优化卷积；

多项式求逆、开根、取对数、指数；

大整数乘法的取模版本。

和普通卷积的区别普通卷积直接枚举每一对

i,j

：

c_{i+j} \mathrel{+}= a_i b_j

复杂度是

O(n^2)

。NTT 通过变换后逐项相乘，把复杂度降到

O(n\log n)

。所以当数据规模很大，比如

n

达到

10^5

或更大时，NTT 就非常有用。一句话总结NTT 是一种在模质数意义下进行的快速变换，可以把多项式乘法，也就是卷积，从

O(n^2)

优化到

O(n\log n)

。它本质上是 FFT 在整数取模环境下的版本，常用于生成函数和多项式相关题目。

165 浏览0 点赞0 收藏0 评论

精华

两类斯特林数

YIZHIYANG初来乍到 2026-5-15 23:59:39

#算法

什么是两类斯特林数斯特林数是组合数学中用来描述“把元素组织成若干部分”的一类计数工具，常见的有两类：第一类斯特林数和第二类斯特林数。它们名字相近，但数的对象完全不同：

第一类斯特林数：数的是排列可以分成多少个循环；

第二类斯特林数：数的是集合可以分成多少个非空子集。

第一类斯特林数第一类斯特林数通常记作

c(n,k)

或者

\left[{n \atop k}\right]

表示：

将 $n$ 个不同元素排成一个排列，并且这个排列恰好分解成 $k$ 个循环的方案数。

这里的“循环”指的是排列的循环表示。例如

n=3

时，元素为

1,2,3

。恰好分成

1

个循环的排列有：

(1\ 2\ 3), (1\ 3\ 2)

所以

c(3,1)=2

恰好分成

j

个循环的排列有：

(1)(2\ 3), (2)(1\ 3), (3)(1\ 2)

所以

c(3,2)=3

恰好分成

3

个循环的排列只有：

(1)(2)(3)

所以

c(3,3)=1

因此第一类斯特林数关注的是：

一个排列的循环结构。

它的递推式是：

c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)

解释如下：考虑第

n

个元素。如果

n

单独成为一个循环，那么前

n-1

个元素需要形成

k_{i-1}

个循环，贡献为

c(n-1,k-1)

。如果

n

插入到已有循环中，那么前

n-1

个元素已经形成

k

个循环。一个排列的循环表示中，总共有

n-1

个位置可以插入

n

，所以贡献为

(n-1)c(n-1,k)

。初始条件为：

c(0,0)=1

并且当

n>0

时：

c(n,0)=0

当

k>n

时：

c(n,k)=0

需要注意的是，有些资料会使用带符号第一类斯特林数，记作

s(n,k)

。它和无符号第一类斯特林数的关系是：

s(n,k)=(-1)^{n-k}c(n,k)

竞赛中如果只是计数排列循环，通常用的是无符号第一类斯特林数。第二类斯特林数第二类斯特林数通常记作

m

或者

\left\{{n \atop k}\right\}

表示：

将 $n$ 个不同元素划分成 $k$ 个非空集合的方案数。

这里的

k

个集合之间没有顺序。例如

n=3

时，元素为

1,2,3

。划分成

1

个非空集合，只有：

\{1,2,3\}

所以

S(3,1)=1

划分成

2

个非空集合，有：

\{1\},\{2,3\}

\{2\},\{1,3\}

\{3\},\{1,2\}

所以

S(3,2)=3

划分成

3

个非空集合，只有：

\{1\},\{2\},\{3\}

所以

S(3,3)=1

因此第二类斯特林数关注的是：

把不同元素分成若干个没有顺序的非空组。

它的递推式是：

S(n,k)=S(n-1,k-1)+kS(n-1,k)

解释如下：考虑第

n

个元素。如果

n

单独组成一个新集合，那么前

n-1

个元素需要分成

k-1

个非空集合，贡献为

S(n-1,k-1)

。如果

n

放入已有集合，那么前

n-1

个元素已经分成

k

个非空集合，

n

可以放进其中任意一个集合，所以贡献为

kS(n-1,k)

。初始条件为：

S(0,0)=1

并且当

n>0

时：

S(n,0)=0

当

k>n

时：

S(n,k)=0

两类斯特林数的区别

类型

常用记号

计数对象

关键词

第一类斯特林数

c(n,k)

或

\left[{n \atop k}\right]

n

个元素的排列分解成

k

个循环

排列、循环

第二类斯特林数

S(n,k)

或

\left\{{n \atop k}\right\}

n

个元素划分成

O(n^2)

个非空集合

集合划分、分组

一个简单的记忆方式是：

第一类斯特林数和排列有关；

第二类斯特林数和集合划分有关。

和多项式的关系两类斯特林数还可以看成普通幂和阶乘幂之间的转换系数。第一类斯特林数和下降幂有关。下降幂定义为：

x^{\underline n}=x(x-1)(x-2)\cdots(x-n+1)

它可以展开成：

x^{\underline n}=\sum_{k=0}^{n}s(n,k)x^k

这里的

s(n,k)

是带符号第一类斯特林数。第二类斯特林数则可以把普通幂展开成下降幂：

x^n=\sum_{k=0}^{n}S(n,k)x^{\underline k}

这说明第二类斯特林数可以理解为：

把 $n$ 个独立选择整理成若干个非空组的计数系数。

和满射的关系第二类斯特林数还有一个常用解释。把

n

个不同元素分到

k

个有编号的盒子里，并且要求每个盒子非空，这就是从

n

个元素到

k

个盒子的满射数量。先把

n

个元素分成

k

个非空集合，有

S(n,k)

种方法。再把这

k

个集合分配给

k

个有编号的盒子，有

k!

种方法。所以满射数量为：

k!S(n,k)

因此：小例子对比当

n=3

时，两类斯特林数分别为：第一类斯特林数：

k

c(3,k)

1

2

2

3

3

1

第二类斯特林数：

k

S(3,k)

1

2

3

3

1

虽然这里有些数看起来一样，但它们的含义完全不同。

c(3,1)=2

数的是

3

个元素构成一个循环的排列数量。

S(3,1)=1

数的是

3

个元素全部放进同一个集合的划分数量。一句话总结第一类斯特林数数的是：

n

个不同元素的排列可以分解成

k

个循环的方案数。第二类斯特林数数的是：

n

个不同元素可以划分成

k

个非空无序集合的方案数。

类型	常用记号	计数对象	关键词
第一类斯特林数	$c(n,k)$ 或 $\left[{n \atop k}\right]$	$n$ 个元素的排列分解成 $k$ 个循环	排列、循环
第二类斯特林数	$S(n,k)$ 或 $\left\{{n \atop k}\right\}$	$n$ 个元素划分成 $k$ 个非空集合	集合划分、分组

$k$	$c(3,k)$
$1$	$2$
$2$	$3$
$3$	$1$

$k$	$S(3,k)$
$1$
$2$	$3$
$3$	$1$

122 浏览0 点赞0 收藏0 评论

矩阵基础知识

YIZHIYANG初来乍到 2026-5-10 9:40:36

#算法

矩阵基础知识一、矩阵是什么矩阵可以简单理解成一个“按行和列排列的数字表”。例如：

A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}

这个矩阵有

2

行、

.second

列，所以它是一个

2\times 3

的矩阵。矩阵中的每一个数叫作矩阵的元素。通常用

1,2,3

表示矩阵

A

中第

i

行第

j

列的元素。比如：

A= \begin{bmatrix} 1&2&3\\ 4&5&6 \end{bmatrix}

那么：

A_{11}=1,\quad A_{12}=2,\quad A_{23}=6

矩阵的大小通常写成：

行数\times 列数

例如：

\begin{bmatrix} 1&2\\ 3&4\\ 5&6 \end{bmatrix}

有

3

行、

2

列，所以它是一个

3\times 2

的矩阵。在算法中，矩阵常常用二维数组存储：int a[105][105];如果矩阵有

n

行、

m

列，就可以用：for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> a[i][j]; } }来读入整个矩阵。二、几种常见矩阵最常见的是普通矩阵，也就是任意行列大小的数字表。例如：

\begin{bmatrix} 2&5&7\\ 1&0&3 \end{bmatrix}

如果一个矩阵的行数和列数相同，就叫作方阵。例如：

\begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}

这是一个

n-1

方阵。再比如：这是一个

3\times 3

方阵。方阵在算法中非常重要，因为只有方阵才能自然地做幂运算，例如矩阵快速幂中的：

M^k

还有一种很重要的矩阵叫单位矩阵。单位矩阵是一个方阵，它的主对角线都是

1

，其他位置都是

0

。例如

2\times 2

单位矩阵是：

I= \begin{bmatrix} 1&0\\ 0&1 \end{bmatrix}

3\times 3

单位矩阵是：单位矩阵在矩阵中的作用类似于普通乘法里的

1

。对于合适大小的矩阵

A

，有：

c(n,k)=0

IA=A

还有一种矩阵叫零矩阵，也就是所有元素都是

0

的矩阵。例如：

\begin{bmatrix} 0&0&0\\ 0&0&0 \end{bmatrix}

它在矩阵加法中类似于普通加法里的

0

。三、矩阵加法、数乘和转置矩阵加法比较容易理解：两个大小完全相同的矩阵，可以对应位置相加。例如：

A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}

B= \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix}

那么：注意，矩阵加法要求两个矩阵的大小一样。一个

2\times 3

的矩阵和一个

3\times 2

的矩阵不能相加。矩阵数乘就是用一个数去乘矩阵中的每个元素。例如：矩阵转置是把矩阵的行和列互换。例如：

S(3,1)=1

它的转置是：原来的第

1

行：

1,2,3

变成了转置后的第

1

列。原来的第

2

行：

w

变成了转置后的第

2

列。转置在算法题中不一定经常直接出现，但它能帮助我们理解矩阵的“行列关系”。尤其是学习矩阵乘法时，转置能让人更清楚地意识到：矩阵乘法本质上是“行”和“列”的配合。四、矩阵乘法的定义矩阵乘法是矩阵基础中最重要的一部分，也是最容易一开始看不懂的部分。矩阵乘法不是对应位置相乘。例如：不是得到：真正的矩阵乘法规则是：

答案矩阵中的第 $i$ 行第 $j$ 列，等于左边矩阵第 $i$ 行和右边矩阵第 $j$ 列对应相乘后再相加。

设：

C=A\times B

那么：

C_{ij}=\sum_k A_{ik}B_{kj}

看一个具体例子。设：

A= \begin{bmatrix} 1&2\\ 3&4 \end{bmatrix}

B= \begin{bmatrix} 5&6\\ 7&8 \end{bmatrix}

要求：

C=A\times B

先算

C_{11}

。取左边矩阵第

1

行：

[1,2]

取右边矩阵第

1

列：

\begin{bmatrix} 5\\ 7 \end{bmatrix}

对应相乘再相加：

1\times 5+2\times 7=19

所以：

C_{11}=19

再算

C_{12}

。取左边矩阵第

1

行：

[1,2]

取右边矩阵第

2

列：

\begin{bmatrix} 6\\ 8 \end{bmatrix}

所以：

C_{12}=1\times 6+2\times 8=22

继续算：

C_{21}=3\times 5+4\times 7=43

C_{22}=3\times 6+4\times 8=50

因此：矩阵乘法有一个很重要的限制：如果

A

是

n\times m

的矩阵，

B

是

p\times q

的矩阵，那么只有当：

m=p

时，

A\times B

才能计算。也就是说，左边矩阵的列数必须等于右边矩阵的行数。最后结果矩阵的大小是：

n\times q

例如：

(2\times 3)\times(3\times 4)=(2\times 4)

但是：

(2\times 3)\times(2\times 4)

不能相乘，因为左边列数是

3

，右边行数是

2

，二者不相等。矩阵乘法代码通常是三重循环：for(int i = 1; i <= n; i++) { for(int j = 1; j <= q; j++) { c[i][j] = 0; for

154 浏览0 点赞1 收藏0 评论

#算法

P12544 [UOI 2025] Boys and Girls

思路

关键性质

情况 1：所有边经过同一个点

情况 2：三角形

三角形枚举

复杂度

C++代码

P1850 [NOIP 2016 提高组] 换教室

知识点

题意概括

解题思路

当前课程不申请

当前课程申请

参考代码

什么是 NTT

NTT 解决什么问题

NTT 和 FFT 的关系

为什么需要特殊的模数

NTT 的核心思想

NTT 的大致流程

正变换和逆变换

为什么 NTT 可以做到 O(nlog⁡n)O(n\log n)O(nlogn)

NTT 常见用途

和普通卷积的区别

一句话总结

什么是两类斯特林数

第一类斯特林数

第二类斯特林数

两类斯特林数的区别

和多项式的关系

和满射的关系

小例子对比

一句话总结

矩阵基础知识

一、矩阵是什么

二、几种常见矩阵

三、矩阵加法、数乘和转置

四、矩阵乘法的定义

登录

为什么 NTT 可以做到 $O(n\log n)$