问题：求 a x+b y=g c e l(a, b)- 组整数解
当 b=0 时 a x+b y=a ，故而 x=1, y=0
当 b \neq 0 时由欧几里得算法， \operatorname{gcd}(a, b)=\operatorname{gcd}(b, a \% b)
由裴蜀定理 \operatorname{gcd}(a, b)=a x+b y
x=x_{0}+\frac{b}{\operatorname{gcd}(a, b)} \times k \\\\
y=y_{0}+\frac{a}{\operatorname{gcdl}(a, b)} \times k
\end{array}
矩阵
定义
一个 n m 的矩阵可看作一个 n m 的二维数组。矩阵的加法和减法就是把两个矩阵对应位置上的数相加减，即 C=A \pm B \Leftrightarrow \forall i \in[1, n], \forall j \in[1, m], C_{i, j}=A_{i, j} \pm B_{i, j} ，其中 A, B, C 都是 n * m 矩阵。
矩阵乘法
$~~~~$矩阵乘法满足结合律，即 $ (A * B) * C=A *(B * C) $ ，满足分配律，即 (A+B) * C= A * C+B * C ，不满足交换律，即 A * B 不一定等于 B * A 。
$~~~~$考虑矩阵乘法中一种特殊的情形， F 是 1 * n 矩阵， A 是 n * n 矩阵，则 $ F^{\prime}=F * A $ 也是 $1 * n $ 矩阵。 F 和 $ F^{\prime} $ 可看作一维数组，省略它们的行下标 1。按照矩阵乘法的定义，$ \forall j \in[1, n] $ ，有 $ F_{j}^{\prime}=\sum_{k=1}^{n} F_{k} * A_{k, j} $ 。它的含义是，经过一次与 A 的矩阵乘法运算后， F 数组中的第 k 个值会以 $ A_{k, j} $ 为系数累加到 F^{\prime} 数组的第 j 个值上，等价于在一个向量的 k, j 两个状态之间发生了递推。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e4;
int n,k;
struct matrict{
int a[5][5];
matrict(){
memset(a,0,sizeof a);
}
};
matrict operator *(matrict A,matrict B){
matrict c;
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
for(int x=1;x<=2;x++){
c.a[i][j]=(c.a[i][j]+A.a[i][x]*B.a[x][j])%M;
}
}
}
return c;
}
signed main(){
while(cin>>n && n!=-1){
if(n==0 || n==1){
cout<<n<<'\n';
continue;
}
matrict a,ans;
a.a[1][1]=a.a[1][2]=a.a[2][1]=1;
for(int i=1;i<=2;i++){
ans.a[i][i]=1;
}
int k=n-2;
while(k){
if(k&1)ans=ans*a;
a=a*a;
k>>=1;
}
cout<<(ans.a[1][1]+ans.a[1][2])%M<<'\n';
}
return 0;
}
```
#### 单位矩阵
定义：对角线为1，其余部分为0的n*n的矩阵叫做单位矩阵。
性质：任意能与他相乘的矩阵与他相乘后都会回到本身。
### 高斯消元
#### 定义
消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。
而高斯消元核心在于：
- 两方程互换，解不变；
- 一方程乘以非零数 𝑘，解不变；
- 一方程乘以数 𝑘 加上另一方程，解不变。
#### 高斯消元的过程可以分为以下几步：
1. 增广矩阵行初等行变换为行最简形；
2. 还原线性方程组；
3. 求解第一个变量；
4. 补充自由未知量；
5. 列表示方程组通解。
```cpp
#include <bits/stdc++.h>
using namespace std;
int n;
double a[100][100];
double eps=1e-4;
bool gauss(){
for(int i=1;i<=n;i++){
for(int k=i;k<=n;k++)if(fabs(a[k][i])>eps){swap(a[k],a[i]);break;}
if(fabs(a[i][i])<eps)return 0;
for(int j=n+1;j>=i;j--)a[i][j]/=a[i][i];
for(int k=i+1;k<=n;k++){
for(int j=n+1;j>=i;j--){
a[k][j]-=a[k][i]*a[i][j];
}
}
}
for(int i=n-1;i>=1;i--){
for(int j=i+1;j<=n;j++)
a[i][n+1]-=a[i][j]*a[j][n+1];
}
return 1;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n+1;j++){
cin>>a[i][j];
}
}
if(gauss()){
for(int i=1;i<=n;i++)printf("%.2lf\n",a[i][n+1]);
}
else cout<<"No Solution";
return 0;
}
```
### 矩阵求逆
矩阵求逆，即求矩阵的逆矩阵。矩阵是线性代数的主要内容，很多实际问题用矩阵的思想去解既简单又快捷。逆矩阵又是矩阵理论的很重要的内容，逆矩阵的求法自然也就成为线性代数研究的主要内容之一。
设A是数域上的一个n阶方阵，若在相同数域上存在另一个n阶矩B，使得： AB=BA=E。 则我们称B是A的逆矩阵，而A则被称为可逆矩阵。其中，E为单位矩阵。
典型的矩阵求逆方法有：利用定义求逆矩阵、初等变换法、伴随阵法、恒等变形法等。
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e9+7;
int n;
int a[405][810];
int ksm(int a,int b){
int ans=1;
while(b){
if(b&1)ans=ans*a%M;
a=a*a%M;
b>>=1;
}
return ans;
}
bool gauss(){
for(int i=1;i<=n;i++){
for(int k=i;k<=n;k++)if(a[k][i]){swap(a[k],a[i]);break;}
if(!a[i][i])return 0;
int kk=ksm(a[i][i],M-2);
for(int j=1;j<=n;j++){
if(j==i)continue;
int p=a[j][i]*kk%M;
for(int k=i;k<=n<<1;k++){
a[j][k]=((a[j][k]-p*a[i][k])%M+M)%M;
}
}
for(int j=1;j<=n<<1;j++) a[i][j]=a[i][j]*kk%M;
}
for(int i=1;i<=n;i++){
for(int j=n+1;j<n<<1;j++) printf("%lld ",a[i][j]);
printf("%lld\n",a[i][n<<1]);
}
return 1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];a[i][i+n]=1;
}
}
if(!gauss()) cout<<"No Solution";
return 0;
}
```
# 组合计数基础
#### 在组合计算方案数时有两种基本原理：
- 加法原理 $\ \ $ 完成一件事的方法有 n 类，其中第 i 类方法包括 $a_{i}$ 种不同的方法，且这些方法互不重合，则完成这件事共有 $a_{1}+a_{2}+\cdots+a_{n} $ 种不同的方法。
- 乘法原理$~~~~$若完成一件事需要 n 个步骤，其中第 i 个步骤有 $ a_{i} $ 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有 $a_{1} * a_{2} * \cdots * a_{n} $ 种不同的方法。
#### 在组合计数中有组合与排列两种方式：
- 排列：$ A_n^m $是组合的数学表示，意思是从n个中选m个出来进行排列。$ ~A_n^m= \frac {n!}{(n-m)!}=n *(n-1) * \cdots * (n-m+1) $。之所以$ A_n^m $它能够表达排列的意思，是因为在选出来的m个位置中，第一个有n种选法，第二个有n-1种选法......以此类推，第m个就有n-m+1种选法，再用乘法原理将它们相乘就是排列。
- 组合：$ C_n^m $是排列的数学表示，意思是从n个中选m个但不进行排列(不考虑顺序)。$~ C_{n}^{m}=\frac{n!}{m!(n-m)!}=\frac{n *(n-1) * \cdots *(n-m+1)}{m *(m-1) * \cdots * 2 * 1} $。之所以$ C_n^m $它能够表达组合的意思,是因为在排列中，有多种所选数字相同，但顺序不同的区别，所以会有重复项，将重负部分除掉即可(就是m!)。
#### 性质
- $ C_{n}^{m}=C_{n}^{n-m}
由组合数的定义，对于从 n 个不同元素中取出 m 个组成的每个集合，剩余未取出的元素也构成一个集合，两个集合一一对应，所以性质 1 成立。
从 n 个不同元素中取出 m 个组成一个集合有两类方法：取 n 号元素，不取 n 号元素。若取 n 号元素，则应在剩余 n-1 个元素中选出 m-1 个，有 C_{n-1}^{m-1} 种取法。若不取 n 号元素，则应在剩余 n-1 个元素中选出 m 个，有 C_{n-1}^{m} 种取法。根据加法原理，性质 2 成立。
从 n 个不同元素中取出若干个元素组成一个集合，有 n+1 类方法，分别是取出 0,1,2, \cdots, n 个。根据加法原理，共有 C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+\cdots+C_{n}^{n} 种方法。从另一个方面去想， n 个元素每个元素可以取或不取，总方法数为 2^{n} ，二者相等，故性质 3 成立。
组合数的求法
根据性质 2，用递推法可求出 0 \leq y \leq x \leq n 的所有组合数 C_{x}^{y} ，复杂度 O\left(n^{2}\right) 。组合数的结果一般较大，若题目要求出 C_{n}^{m} 对一个数 p 取模后的值，并且 1 \sim n 都存在模 p 乘法逆元，则可以先计算分子 n!\bmod p ，再计算分母 m!(n-m)!\bmod p 的逆元，乘起来得到 C_{n}^{m} \bmod p ，复杂度为 \mathrm{O}(n) 。
若在计算阶乘的过程中，把 0 \leq k \leq n 的每个 k!\bmod p 及其逆元分别保存在两个数组 j c 和 j c_{-} i n v 中，则可以在 \mathrm{O}(n \log n) 的预处理后，以 \mathrm{O}(1) 的时间回答 0 \leq y \leq x \leq n 的所有组合数 C_{x}^{y} \bmod p=j c[x] * j c_{-} i n v[y] * j c_{-} i n v[x-y] \bmod p 。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int p;
int a,b;
int f[N],g[N];
int ksm(int a,int b){
int c=1;
while(b){
if(b&1)c=c*a%p;
a=a*a%p;
b>>=1;
}
return c;
}
int ask(int n,int m,int p){
int mb=1,ma=1;
for(int i=1;i<=m;i++)mb=mb*i%p;
for(int i=n-m+1;i<=n;i++)ma=ma*i%p;
return ma*ksm(mb,p-2)%p;
}
signed main(){
int T;cin>>T;
while(T--){
cin>>a>>b>>p;
cout<<ask(a,b,p)<<'\n';
}
return 0;
}
若随机变量 X 的取值有 x_{1}, x_{2}, \cdots ，一个随机事件可表示为 X=X_{i} ，其概率为 P\left(X=X_{i}\right)=p_{i} ，则称 E(X)=\sum p_{i} x_{i} 为随机变量 X 的数学期望。通俗地讲，数学期望是随机变量取值与概率的乘积之和。
例如在掷两枚骰子的点数实验中，样本空间是由 36 个样本点构成的集合，每个样本点可写作 (a, b) ，其中 1 \leq a ; b \leq 6 。随机变量有多种，不妨以＂掷出的点数之和 X ＂为例，则随机变量 X 的取值为 2 \sim 12 。随机事件可描述为＂掷出 X 点＂，即由 a+b=X 的样本点 (a, b) 构成的子集。掷出 8 点的概率 P(X=8)=5 / 36 。掷出的点数的数学期望为：