数论与线性代数模板（持续更新）
大数取模
问题：两个longlong的数a，b相乘并取模，仅仅只用同余定理不行了，(a%mod)*(b%mod)是有可能溢出的，下面的模板在一定程度上解决这个问题
typedef long long ll;
ll mul(ll a, ll b, ll mod)
{
a = a % mod;
b = b % mod;
ll ans = 0;
while (b > 0)
{
if (b & 1)ans = (ans + a) % mod;
a = (a + a) % mod;//需要保证a+a不会溢出
b >>= 1;
}
return ans;
}
原理：
为了不直接计算a%b，改为计算(a* 2 )*(b/2)，其中a *2基本不会溢出，b/2不会溢出。连续执行a *2和b/2，直到b减少为0为止，结束计算。不过因为b为整数，需要判断一下奇偶，奇数时会向下取整，丢弃一个1。
- b是偶数，(a*2) *(b/2)等于a *b
- b是奇数，a*b等于（a *2) *(b/2+1)= (a * 2) *(b/2)+a *2
注意，使用此代码时，若mod足够大也可能会出错
快速幂
这里只写取模版本了
整数快速幂取模版本
求一个数a的b次方
ll fastPow(ll a, ll n,ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans + a) % mod;
a = (a * a) % mod;
n >> 1;
}
return ans;
}
矩阵快速幂取模版本
求斐波那契数列第n项
struct martix
{
int m[2][2]={0};
martix operator*(const martix& a)
{
martix c;
memset(c.m, 0, sizeof(c.m));
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
c.m[i][j] += (m[i][k]%10000)*(a.m[k][j]%10000)%10000;
return c;
}
};
martix martixPow(int n, int mod)
{
martix ans = { {1,0,0,1} }, a = { {1,1,1,0} };
n += 1;
while (n)
{
if (n & 1)ans = ans * a;
a = a * a;
n >>= 1;
}
return ans;
}
高斯—约当消元法
参考：P3389 【模板】高斯消元法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
对于高斯消元呢，我们从一个例子讲起。
我们首先确定一个方程组作为例子
x-2y+3z=6
4x-5y+6z=12
7x-8y+10z=21
先将它转化为矩阵
1 -2 3 6
4 -5 6 12
7 -8 10 21
解决这个方程组
我们会希望它变成如下形式
1 0 0 a
0 1 0 b
0 0 1 c
这样就可以表示为x=a,y=b,z=cx=a,y=b,z=c
我们使用高斯消元，就要一步一步将每个未知数约去。
这种方法是以列为单位消去的
首先我们将第一列转化为1 0 0的形式
在这里要注意一下，我们往往是将这个系数绝对值最大的方程转移到被减的这一行，这样就可以减小误差
所以我们先将矩阵变成这样
7 -8 10 21
4 -5 6 12
1 -2 3 6
然后将正在处理的方程式化简，让正被处理的系数化1
1 -8/7 10/7 3
4 -5 6 12
1 -2 3 6
然后使用加减法将第二个与第三个方程组的第一个系数化0
1 -8/7 10/7 3
0 -3/7 2/7 0
0 -6/7 11/7 3
然后这时候第一列就被化简完成
同理我们化去第二行与第三行，步骤如下：
1.化简第二行
1 -8/7 10/7 3
0 1 -2/3 0
0 -6/7 11/7 3
2.用第一行减第二行×(-8/7),第三行减第二行×(-6/7)
1 0 2/3 3
0 1 -2/3 0
0 0 1 3
3.不需要化简第三行，所以直接用第一行减去第三行×2/3，第二行减去第三行×(-2/3)
1 0 0 1
0 1 0 2
0 0 1 3
最后我们就得到了一组解x=1,y=2,z=3。
#include<stdio.h>
#include<math.h>
const double EPS=1E-8;
double B[110][110];
int n;
int main(){
scanf("%d",&n);
for (register int i=0;i<n;i++){
for (register int j=0;j<n;j++)
scanf("%lf",&B[i][j]);//读入系数
scanf("%lf",&B[i][n]);//读入值
}
for (register int i=0;i<n;i++){
int pivot=i;
for (register int j=i;j<n;j++)//选择一个当前位置系数绝对值最大的调换过来，防止误差
if (fabs(B[j][i]-B[pivot][i])<=EPS) pivot=j;
for (register int j=0;j<=n;j++){//交换操作，要将所有的全部交换过来
double t=B[i][j];
B[i][j]=B[pivot][j];
B[pivot][j]=t;
}
if (fabs(B[i][i])<=EPS){//如果该位置系数等于零，则0x=a，一定无解
printf("No Solution\n");
return 0;
}
for (register int j=i+1;j<=n;j++) B[i][j]/=B[i][i];//将该位的系数变为1
for (register int j=0;j<n;j++)
if (i!=j)
for (register int k=i+1;k<=n;k++) B[j][k]-=B[j][i]*B[i][k];//将其他方程用加减法减去系数值
}
for (register int i=0;i<n;i++) printf("%.2lf\n",B[i][n]);//最后输出结果。
return 0;
}
异或空间线性基（高能）
给定 n个整数（数字可能重复），求在这些数中选取任意个，使得他们的异或和最大。二进制数的异或(XOR，用符号^表示）。
例：给定三个数{2,3,4,}，取其任意个数做异或可得{2,3,4，2^ 3,2^ 4,3^ 4,2^ 3^ 4}={2,3,4,1,6,7,5}。其中最大的为3^7=7
解答较长，耐心看完：
异或空间线性基的概念
“取其中任意个数”,如果简单地组合出所有情况,n个数的任意组合共有2^n种,n一大,不可能计算出来。
不过,虽然有2^n种组合,但是所有组合的异或结果(值域)却少得多。
设n个数中最大的数有m位,那么“在n个数中取任意个数作异或”的结果最多只有2^m种。例如,最大的数是8764,二进制为10001000111100,共14位,则m=14,原因很简单:任意两个数a、b作异或计算c=a ^ b,c的位数不大于a、b中最大的位数。所以,2 ^ n种组合的异或结果为0~2 ^m-1,最多有2 ^m种。例如,设n个数字都是64位的long long型,其中最大的数有m=63位,那么异或的计算结果最多有2 ^63种有没有可能把2^n种组合缩小到2^m种组合?这就是用线性基求解异或问题的思路:把对n个数的组合求异或,缩小到对m个数(线性基)的组合求异或,从而把2^n规模的问题缩小到2^m规模的问题。设原数字的集合为A=(a1,a2……an),求得线性基P=(p1,p2……pk)。在A和P上分别对任意组合求异或,结果是一样的,换句话说,对A异或与对P异或是等价的。注意,这里的“等价”不包括0,A的异或计算可能有0,而P的异或计算没有0。例如,A=(2,3,5,6,7),n=5,它的任意组合有2^ 5 -1 =31种,注意这里不是2^ 5,去掉了空集的情况。对A中元素的所有组合作异或计算,结果是(0,1,2,3,4,5,6,7)。A中最大的数有k=3位,用后面的方法计算得到线性基P=(5,2,1),有2^3-1=7种组合,异或结果也是(1,2,3,4,5,6,7),正好7种。注意,线性基不是唯一的,如A=(2,3,5,6,7)的线性基有(7,2,1)、(7,3,1)、(5,2,1)等,它们的个数都是3个
异或空间线性基的性质
异或空间线性基P具有以下性质：
等价性。在原数组A上进行异或计算,与在线性基P上进行异或计算结果相同。最小性(最优性)。P是满足性质(1)的所有集合中元素个数最少的。最小性隐含了线性无关性,即P中不同的组合,其异或结果也不同。以上两条是线性基的基本要求。从性质(2)可以推出性质(3)。线性基P中不存在异或和为0的子集。如果存在异或和为0的子集,如pa^ pb^ pc^ px=0,pa^ pb^ px=px^ px可以用pa，pb，pc组合得到，px是多余的,这与性质(2)矛盾。但是,P中不存在异或为0的子集,A中却可能有。例如,A=(1,2,3),P=(1,2),1^ 2^3=0。构造线性基P时遵循一个规则:P中每个元素的二进制位数均不相同。这实际上也是性质(2)的要求。P中元素的最少位数为1,最大位数为m,那么P的所有元素个数不会超过m个,这保证了P的最小性。而且,这个规则也保证了P的所有元素都是线性无关的,满足这个规则的P的任意组合的异或和都不会相同。进一步推导出,P能组合出的异或和有2^k-1种,不包括空集,其中k为P的元素个数。
异或线性基的构造
1.基本原理
如何计算出集合A的线性基P?
分析两种情况。
- (1)首先分析一个特例:若A中所有元素的二进制位数都不同,那么A就是它自己的一个线性基。例如,A=(1,3,9),它的一个线性基是它自己P=(1,3,9)。A也有其他线性基,如(1,2,9)、(1,2,8)等。A的3个元素(1,3,9)的二进制是(1,11,1001),长度分别为1位,2位4位。构造线性基P时,P中应该有一个4位的元素,否则无法通过其他不同长度的元素异或出一个第4位为1的数1001;同理,P中也需要一个2位、1位的元素,否则无法通过其他不同长度的元素异或出来。既然如此,直接把A看成自己的线性基即可。
- (2)另一种情况是A中有位数相同的元素。前面已经提到,为满足线性基的最小性,构造P的规则是“P中每个元素的二进制位数均不相同”。在A中把相同位数的元素选一个(如第1个)直接复制到P中,相同位数的其他元素不能再放人P中,如何处理?
先讨论有两个相同位数元素的线性基构造。设A=(a1,a2),且两个元素位数相同,它的一个线性基是P=(a1,a1^ a2)。下面证明P与A在异或空间等价。a1 ^ a2比a1，a2的长度短,因为a1,a2的最高位被异或计算去掉了。(a1,a2)与(a1,a1 ^ a2)的异或计算结果相同,因为(a1,a2)的异或组合是(a1,a2,a1 ^ a2),而(a1,a1^ a2)的组合是(a1,a1 ^a2,a1 ^ a1^ a2)= (a1,a1 ^a2,0 ^a2)= (a1,a1 ^a2,a2)。
这样就解决了A中有两个相同位数元素的问题。当A中相同位数的元素超过两个时,连续处理即可。例如,A=(8,13,15),用二进制表示为A=(1000,1101,1111),都有4位,处理过程如下。
①把第1个数1000放人P中,P=(1000)。
②第2个数1101与P中的1000异或,1101^1000=101,放人P中,P=(1000,101)。
③第3个数1111与P中的1000异或,1111^ 1000=111,继续与P中的101异或,111^101=10,P=(1000,101,10)。计算结束,线性基用十进制表示为P=(8,5,2)。
分析构造线性基的计算复杂度:A中有n个数,每个数最多与当前P的每个元素异或一次,P最多有m个元素,总复杂度为O(nm)。
最后,复述前面提到的一个结果: P能组合出的异或和有2^k-1种,不包括空集,其中k为P的元素个数。
高斯消元法求线性基
上述构造线性基的过程,如果用高斯消元法解释会更清晰,而且借助高斯消元法也能更透彻地理解线性基应用问题。
设原集合A=(a1,a2……an),最大位数为m,求线性基P=(p1,p2……pn),其中p1>p2>……pn
把A的每个整数看作m位二进制数,写成一个n行m列的0/1矩阵,矩阵的第i行,从左到右依次是ai，的第m-1,m-2,…,1,0位。把这个矩阵看作异或方程组的系数矩阵,用高斯消元法求解异或方程组,最后把它转换为简化阶梯矩阵,简化阶梯矩阵的非零整数行就是A的线性基。简化阶梯矩阵中包含一个单位矩阵,即只有对角线上是1。
其正确性讨论如下。
(1)初始系数矩阵的各行的任意组合对应了A中元素的任意组合。
(2)初始系数矩阵能变换得到简化阶梯矩阵;反过来,简化阶梯矩阵也能变换得到初始系数矩阵,两者是等价的。
(3)简化阶梯矩阵的每行的位数不同,符合线性基的要求,它是一个线性基。
求A=(8,13,15)的线性基。高斯消元过程如下。
1000 1000 1000
1101→ 0101 → 0101
1111 0111 0010
在第1个矩阵上做第1次消元：第1行与第2、3行异或,得中间的矩阵。在中间矩阵上做第2次消元：第2行与第3行异或，得最后一个简化阶梯矩阵，即线性基P=(8,5,2)。注意简化阶梯矩阵的前3列是一个单位矩阵。
求A=(2,3,5,6,7)的线性基。下面概要给出高斯消元过程,最后一个矩阵是简化阶梯矩阵 ,前3行是一个单位矩阵,线性基P=(4,2,1)。在简化阶梯矩阵中有两个全为0的行,这说明初始矩阵可以组合出0,即A中有等于0的异或和,如3^ 5^6=0。
010 111 111 100
011 010 010 010
101→ 011→ 001→ 001
110 101 000 000
111 110 000 000
线性基的应用
得到线性基后,能高效率处理以下异或问题。
最小异或和
由前面的高斯消元示例可知,若简化阶梯矩阵中有全0的行,说明A的最小异或和为0。除了0以外,A的最小异或和就是P的最小元素,即位数最小的元素。因为这个元素与P的其他元素异或,必然会增大。由于最小异或和只有一个值,所以P中最小的元素是唯一的。
最大异或和
从大到小对P的所有元素运用贪心法,若异或某个元素使结果变大,则异或它,否则忽略它。为什么这样操作是对的?以最大元素为例,它必然用在最大异或值的计算中,因为它的位数比其他元素都多,无论其他所有元素如何组合,其异或结果的位数都不会大于最大元素。再以第2大元素为例,如果它能使异或结果变大,就使用它,因为比它小的元素的任意组合的异或都不会比它大。
若使用高斯消元求得的简化阶梯矩阵计算最大异或和,则更简单,直接异或P中所有元素即可。因为只有对角线上是1,这一行所表示的元素必须选中作异或,否则在最后的异或结果中这一位就是0了。
下面是上面这个题的代码,求最大异或和。Insert()函数逐个加入A的元素,计算线性基P。这段代码没有用高斯消元,生成的线性基不是形如简化阶梯矩阵的。高斯消元需要离线操作,即读完A的所有元素后才能建立异或方程组。
数组P[]存储生成的线性基,P[i]表示最高位在第i位的元素。例如,生成用二进制表示的线性基P=(1,11,1001),P[3]=1001,P[1]=11,P[0]=1。
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 63;
ll p[maxn];//线性基
bool flag;
void insert(ll x)
{
for (int i = maxn; i >= 0; i--)
if (x >> i == 1)//x的最高位
if (p[i] == 0)
{
p[i] = x;
return;//p[i]还没有，直接让p[i]=x
}
else
x ^= p[i];//p[i]有了，逐个异或
flag = true;//有异或和为0的组合
}
ll get_max()
{
ll ans = 0;
for (int i = maxn; i >= 0; i--)
ans = max(ans, ans ^ p[i]);
return ans;
}
int main()
{
ll x, n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &x), insert(x);
printf("%lld\n", get_max());
return 0;
}
第k大（小）异或和
如果利用高斯消元得到的简化阶梯矩阵,求第k大异或和问题变得极为简单。例如,用简化阶梯矩阵表示的一个线性基P,共有4个元素,每行表示一个元素,如下：
10001
01000
00101
00011
最大异或和:异或P所有的元素。4行表示的4个元素全都异或,用1111表示全选。
第2大异或和:异或前3行,用1110表示选前3行。
第3大异或和:用1101表示选第1、2、4行的3个元素。以此类推……
综上所述,设P有t个元素,即简化阶梯矩阵有t行,第k大异或和就是选2^ t-k的二进制对应的那些行。例如上面的例子,k=1,选2^ t-k=16-1=15=1111(二进制); k=2,选2^t-k=16-2=14=11102;等等。
01分数规划
给n组数据ai,bi，定义累计平均值为：
现给出一个整数k，要求从这n个数中去掉k个数后，最大累计平均值能有多大？(四舍五入到整数)
思路
取n−k个数，使得累计平均值最大。
定义C(x)表示能否取得n−k个数，使得累计平均值≥x。然后二分搜索最大的x。
可以这样判断可行性：
由上面的式子我们可以得到我们最后要求的是让sum>=0的x的最大值，具体细节可自行将ai-x*bi(100这个系数放到最后乘也不会对结果产生影响，所以可以先不乘100)的各个直线画出来。
很容易发现每一条直线与x轴的交点的横坐标（即直线的横截距）就是最大的可行的x值.
改变竖线x=M的M值,让这条竖线在x轴上左右移动,就能找到那个最大的M。当这条竖线在M的右侧时,f<0;当竖线在M的左侧时,f>0; f=0时,对应M。f的变化情况说明它满足了应用二分法所需要的单调性。注意,做上述操作有一个前提,必须对直线排序,然后选最大的前k条直线,这样才能满足单调性。
#include<iostream>
#include<algorithm>
using namespace std;
struct Line {
long long a, b;
double y;
bool operator<(const Line& x)
{
return y > x.y;
}
}line[1001];
long long n, k;
bool check(double x)
{
for (int i = 0; i < n; i++)
line[i].y = line[i].a * 1.0 - x * line[i].b;//计算每个直线在x=m的值y
sort(line, line + n);//对y值排序
double sum = 0;
for (int i = 0; i < k; i++)
sum += line[i].y;//对前k条直线的y值求和
return sum < 0;//小于0，答案在右侧
}
int main()
{
while (scanf("%lld%lld", &n, &k) != EOF && n+k)
{
k = n - k;
for (int i = 0; i < n; i++)
scanf("%lld", &line[i].a);
for (int i = 0; i < n; i++)
scanf("%lld", &line[i].b);
double l = 0, r = 0;
for (int i = 0; i < n; i++)
r += line[i].a;
for (int i = 0; i < 100; i++)//次数可根据题目精度来定
{
double mid = l+(r-l)/2;
if (check(mid))
r = mid;
else
l = mid;
}
printf("%lld\n", (long long)(100*(l+0.005)));
}
return 0;
}