exgcd,二元一次丢番图方程

1.定理

对于任意整数$a,b$，存在一对整数$x,y$,满足$ax + by = gcd(a,b)$.

2.证明

int gcd(int a,int b) {
    if (b == 0)
        return a;
   	return gcd(b,a % b);
}

这是辗转相除法求gcd的代码。

我们可以发现当$b = 0$时，有一组$x = 1,y = 0$，使得$ax + by = a \times 1 + b \times 0 = gcd(a,b) = a$。

对于任意一组$a,b$，假设存在一对整数$x,y$使得$bx + (a % b)y = gcd(b,a % b) = gcd(a,b)$，对它变形：
$$
bx + (a % b)y = gcd(b,a % b) = gcd(a,b)\bx + (a - b \times \lfloor a / b \rfloor)y = gcd(a,b)\ya + (x - y \times \lfloor a / b \rfloor)b = gcd(a,b)
$$
所以我们有了一对$x’ = y,y’ = x - y * \lfloor a / b \rfloor$使得$ax’ + by’ = gcd(a,b)$。

3.代码

#include<iostream>
#include<cstdio>

using namespace std;

int a,b,x,y,gcd;

int exgcd(int a,int b,int &x,int &y) {
	if (b == 0) {
		x = 1,y = 0;
		return a;
	}	
	int d = exgcd(b,a % b,x,y);
	int z = x;
	x = y,y = z - (a / b) * y;
}

int main() {
	scanf("%d%d",&a,&b);	
	gcd = exgcd(a,b,x,y);
	printf("%d %d\n",x,y);
	return 0;
}

4.求通解

上文中我们求出了一对$x_0,y_0$满足$ax_0 + by_0 = gcd(a,b)$,现在来求通解。

取一组解$(x_1,y_1)$，再任取一组解$(x_2,y_2)$，有：
$$
ax_1 + by_1 = ax_2 + by_2 = gcd(a,b)\a(x_1 - x_2) = b(y_2 - y_1)\两边同时除以gcd(a,b),设a / gcd(a,b) = a’,b / gcd (a,b) = b’\a’(x_1 - x_2) = b’(y_2 - y_1)\此时gcd(a’,b’) = 1\所以x_1 - x_2 = kb’,y_2 - y_1 = ka’
$$

5.另外一个定理

关于整数$x,y$的方程$ax + by = c$有解的充要条件是$gcd(a,b)|c$。

Acwing299题解

发表于 2023-06-15 更新于 2025-01-28

Acwing 299 裁剪序列（也许它能帮到你）

1.题意：

给定一个长度为 $N$ $(N \le 1e5)$的序列 $A$ ，要求把该序列分成若干段，在满足“每段中所有数的和”不超过M的前提下，让“每段中所有数的最大值”之和最小。

试计算这个最小值。

2.分析

朴素DP：

状态：设$f[i]$ 表示将前 $i$ 个数分为若干段，每段和不超过 $m$ 时，最大值之和的最小值。
转移方程：
$$
f[i] = min(f[j] + max(a[j + 1],a[j + 2],……a[i])) \ \ \ \ (\sum_{k = j + 1}^na_k \le m)
$$
其中的区间最大值和区间和分别可以用ST表和前缀和完成。

复杂度$O(n^2)$.

接下来来考虑优化。

若$j$可能作为$f[i]$的唯一最优决策，那么$j$必须满足下面两个条件之一：

$a[j]$是$a[j],a[j + 1],……,a[i]$中的最大值

$\sum_{k = j}^i a_k > m$

证明：

若$j$对上述两个条件都不满足，那么对于决策$j - 1$：

因为$\sum_{k = j}^i a_k \le m$，所以决策$j - 1$是合法的。

同时因为$a[j]$不是$a[j],a[j + 1],……,a[i]$中的最大值，所以

$$
\max(a[j + 1],a[j + 2],……a[i]) = \max(a[j],a[j + 1],a[j + 2],……a[i])
$$

又因为$f[i]$单调不减，所以：
$$
f[j - 1] + max(a[j],a[j + 1],a[j + 2],……a[i])\le f[j] + max(a[j + 1],a[j + 2],……a[i])
$$
即决策$j - 1$比决策$j$更优或相等，所以决策$j$不会是唯一的最优决策。

对于考虑满足第二个条件的决策，我们可以预处理出$c[i]$，表示满足$\sum_{k = j}^ia_k \le m$的最小的$j$。然后对于$f[i]$，执行f[i] = min(f[i],f[c[i] - 1]+max(a[c[i]],a[c[i] + 1],a[c[i] + 2],……,a[i]))

对于考虑满足第一个条件的决策，我们可以考虑用单调队列来优化DP。

循环变量$i$，循环开始先从队头剔除不合法的决策（即状态转移中的条件）

然后将$i$入队，同时维护单调队列元素$x$的$a[x]$单调不增，保证单调队列中的决策都是可能的最优决策。

但是这样我们还是需要循环整个单调队列枚举所有决策。

接下来我们来集中解决这个问题。

我们先建立一个used数组。

我们再建立一个小根堆，其中的元素为(id,x)，按x作为比较的依据。表示对于决策$id$，x表示$f[id] + max(a[id + 1],a[id + 2],……a[id])$。

每次向单调队列中插入一个新决策$j$时，同时也向堆中插入这个决策$(j,f[j] + max(a[j + 1],a[j + 2],……,a[i]))$。当从单调队列中删除一个决策$j$时，令$used[j] = 1$。以后从堆顶取数时，需要判断$used[top().id]$是否为1，若是1，需要将其弹出，重新取堆顶。

我们能这样做的一个原因在于一旦决策$j$被丢弃，以后该决策就不可能再次出现在单调队列中了。

现在我们还需要一个问题要解决：当$i$变成$i + 1$时，有可能
$$
\max(a[j + 1],a[j + 2],……,a[i]) \neq \max(a[j + 1],a[j + 2],……,a[i],a[i + 1])
$$
即对于每个$i$，我们都需要将堆中的元素重新更新一遍。

为了方便起见，我们称呼$max(a[j + 1],a[j + 2],……,a[i])$为决策$j$对于$i$的**“决策值**，简写为$p(j,i)$。

我们观察一下何时$p(j,i) \neq p(j,i + 1)$.发现：将$i$入队后，在单调队列${q_1,q_2,……,q_s,i}$中，因为$a[q_1] \ge a[q_2] \ge …… a[i]$，所以对于决策$q_1,q_2,……,q_{s - 1}$，$p(q_1,i) = p(q_1,i + 1)$,$p(q_2,i) = p(q_2,i + 1)$,……,$p(q_{s - 1},i) = p(q_{s - 1},i + 1)$,只有$p(q_s,i)$可能不等于$p(q_s,i + 1)$.

所以$i$入队后，我们再将决策$(id = q_s,x = f[q_s]$ + $ max(a[q_s + 1],a[q_s + 2] ，……，a[i]))$重新入队，作为修正。可以发现，$max(a[q_s + 1],a[q_s + 2] ，…，a[i]) = a[i]$。

但是，决策$q_s$在堆里面原来的错误的值并没有被修改。为了解决这个问题，我们可以给堆的结构体中加一个变量$y$表示当前决策目前的”决策值”。取出堆顶的时候，如果发现堆顶决策的”决策值“不等于堆顶决策对于$i$应有的决策值时，就将该决策视为无效，重新取堆顶。

Code:

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<queue>

#define int long long
using namespace std;

const int maxn = 1e5 + 5,inf = 1e15;

struct node {
	int id,x,y;
	friend bool operator < (node a,node b) {
		return a.x + a.y > b.x + b.y;
	}	
};


int q[maxn << 3],t,w;

int a[maxn],n,m,sum[maxn],lg[maxn],st[maxn][30],c[maxn];
int f[maxn]; //f[i] 表示将前 i 个数分为若干段，每段和不超过 m 时，最大值之和的最小值。 
bool used[maxn];

priority_queue<node> h;

int query(int l,int r) {
	int len = lg[r - l + 1];
	return max(st[l][len],st[r - (1 << len) + 1][len]); 	
}

signed main() {
	scanf("%lld %lld",&n,&m);
	for (int i=1; i<=n; i++) {
		scanf("%lld",&a[i]);
		if (a[i] > m) {
			puts("-1");
			return 0; 
		}
		sum[i] = sum[i - 1] + a[i];
		st[i][0] = a[i];
	}
	lg[0] = -1;
	for (int i=1; i<=n; i++)
		lg[i] = lg[i >> 1] + 1;
	
	for (int i=1; i<=lg[n]; i++)
		for (int j=1; j<=(n - (1 << i) + 1); j++)
			st[j][i] = max(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]);
			
	c[0] = 1;
	for (int i=1; i<=n; i++)
		for (int j=c[i - 1]; j<=n; j++)
			if (sum[i] - sum[j - 1] <= m) {
				c[i] = j;
				break;
			}
	
	// c[i] 表示 a[j] + a[j] + ……+ a[i] <= m的最小的j。
	// f[i] 表示将前 i 个数分为若干段，每段和不超过 m 时，最大值之和的最小值。 
	t = 1,w = 0;
	
	for (int i=1; i<=n; i++) {
		f[i] = inf;
		f[i] = min(f[i],f[c[i] - 1] + query(c[i],i)); //考虑条件2
		while (t <= w && sum[i] - sum[q[t]] > m) {
			used[q[t]] = 1;
			t++;
		} //从队头弹出非法决策
			
		while (t <= w && a[q[w]] < a[i]) {
			used[q[w]] = 1;
			w--;
		} //从队尾弹出不必要决策
		q[++w] = i;
		
		if (t < w) 
			h.push((node){q[w - 1],f[q[w - 1]],a[i]}); //修正“决策值”
		
		while (!h.empty() && (used[h.top().id] || h.top().y < query(h.top().id + 1,i)))
			h.pop();
		
		if (!h.empty())
			f[i] = min(f[i],h.top().x + h.top().y); 
	
	}
	printf("%lld\n",f[n]);
	return 0;
}

初心

发表于 2023-06-12 更新于 2023-11-15

希望能够幸福地做人，合理地度日，内心安定平和，即使身处逆境也始终保持追求。同时也希望能够通过文字与各位交流这方面的经验，于苦难中彼此慰藉。

机器学习笔记

发表于 2023-03-06 更新于 2025-01-28

机器学习笔记

1. 安装Pytorch

在这里选择你的选项，然后在命令行中打pytorch官网提供的命令，打完之后如果遇到了错误，那么考虑是不是你的python版本过高。访问Start Locally | PyTorch这里来确认pytorch是否支持你的python版本。

2. 《动手学深度学习》笔记

2.1 数据操作

注意：两个张量如果可以广播，那么：

每个张量至少有一个维度。
迭代维度尺寸时，从尾部的维度开始，维度尺寸
或者相等，
或者其中一个张量的维度尺寸为 1 ，
或者其中一个张量不存在这个维度

例如：

import torch

# 示例1：相同形状的张量总是可广播的，因为总能满足以上规则。
x = torch.empty(5, 7, 3)
y = torch.empty(5, 7, 3)


# 示例2：不可广播（ a 不满足第一条规则）。
a = torch.empty((0,))
b = torch.empty(2, 2)


# 示例3：m 和 n 可广播：
m = torch.empty(5, 3, 4, 1)
n = torch.empty(   3, 1, 1)
# 倒数第一个维度：两者的尺寸均为1
# 倒数第二个维度：n尺寸为1
# 倒数第三个维度：两者尺寸相同
# 倒数第四个维度：n该维度不存在


# 示例4：不可广播，因为倒数第三个维度：2 != 3
p = torch.empty(5, 2, 4, 1)
q = torch.empty(   3, 1, 1)

# 示例5：a 和 b 可广播：
m = torch.arange(12).reshape(2,2,3)
n = torch.tensor(1)

2.4 微积分

2.4.3的梯度没有懂，尤其是涉及矩阵的部分

2.5 自动微分

2.5.1 一个标量函数如何对一个向量求导？

标量 y 对 n 维列向量 $x = (x_1,x_2,…,x_n)^T$求导，其结果还是一个n维列向量，结果是$(\frac {\partial y} {\partial x_1}, \frac {\partial y} {\partial x_2} … \frac {\partial y} {\partial x_n})^T$

标量 y 对 n 维行向量 $x = (x_1,x_2,…,x_n)$求导，其结果还是一个n维行向量，结果是$(\frac {\partial y} {\partial x_1}, \frac {\partial y} {\partial x_2} … \frac {\partial y} {\partial x_n})$

plafle's blog

OI题单