首页 > 其他分享 >线性基相关模板

线性基相关模板

时间：2024-10-21 22:22:18浏览次数：6  
标签：include return int ll 线性 相关 fo 模板 define

[ABC236F] Spices

有 \(2 ^ N - 1\) 个数字，分别编号为 \(1, 2, \dots, 2 ^ N - 1\)，想获得编号为 \(i\) 的数字需要支付 \(c_i\) 的代价。

现在你可以从这些数字中选出一些数，使得你可以通过你选择的某些数的编号的异或和来表示出 \([1, 2 ^ N - 1]\) 中的所有数。

请你求出最少需要支付多少代价。

线性基的基本贪心，按照\(c_i\)从小到大排序后，依次插入，可以插入的就是加入答案中的数。

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=5e5+5;
const int M=2e6+5;
struct Base{
	ll p[35];
	bool ins(ll x){
		fd(i,31,0) {
			if ((x>>i)&1) {
				if (!p[i]) {
					p[i]=x;
					return 1;
				}
				else x^=p[i];
			}
		}
		return 0;
	}
};
Base t;
ll n;
struct node{
	ll i,c;
};
node a[N];
int main(){
//	freopen("data.in","r",stdin);
	
	scanf("%lld",&n);
	n=(1<<n)-1;
	fo(i,1,n) {
		scanf("%lld",&a[i].c);
		a[i].i=i;
	}
	sort(a+1,a+n+1,[](node a,node b){
		return a.c<b.c;	
	});
	
	ll ans=0;
	fo(i,1,n) {
		if (t.ins(a[i].i)) ans+=a[i].c;
	}
	printf("%lld",ans);

	
	return 0;
}

[WC2011] 最大XOR和路径

给出所有边权，问从1-n的最大XOR和路径是多少。

本质上就是随便选取一条路径的xor和，以及其它所有的环，全部丢到线性基里面。
然后就是贪心取最大值。

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=5e5+5;
const int M=2e6+5;
const ll mo=1e9+7;
struct Base{
	ll p[100];
	ll rank=0;
	bool ins(ll x){
		fd(i,60,0) {
			if ((x>>i)&1) {
				if (!p[i]) {
					p[i]=x;
					rank++;
					return 1;
				}
				else x^=p[i];
			}
		}
		return 0;
	}
};
Base t;

ll head[N],nex[M*2],to[M*2],tot=1;
ll w[M*2],val[N];
bool vis[N];
ll n,m,x,y,z;
void add(ll x,ll y,ll z){
	to[++tot]=y; nex[tot]=head[x]; head[x]=tot; w[tot]=z;
}
void dfs(int x){
	vis[x]=1;
	for(int i=head[x];i;i=nex[i]) {
		int v=to[i];
		if (vis[v]) {
			t.ins(w[i]^val[v]^val[x]);
		}
		else {
			val[v]=val[x]^w[i];
			dfs(v);
		}
	}
}
int main(){
//	freopen("data.in","r",stdin);
	
	
	scanf("%lld %lld",&n,&m);
	fo(i,1,m) {
		scanf("%lld %lld %lld",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	
	dfs(1);
	ll ans=val[n];
	fd(i,60,0) ans=max(ans, ans^t.p[i]);
	printf("%lld",ans);
	
	return 0;
}

P3292 [SCOI2016] 幸运数字

给定一棵树，每个节点有一个权值\(a_i\)，每次询问从x到y路径上所有点\(a_i\)组成的线性基。

每个点维护一个从它到根的线性基，并用一个vector记录这些点，计算当前点的线性基时，首先将自己的点插入，然后将父亲的线性基插入即可。

每次询问的时候，x,y的线性基中深度小于lca的全部插到一个新的线性基即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<iostream>
#include<queue>
#include<set>
//#define A puts("YES")
//#define B puts("NO")
//#define A puts("Yes")
//#define B puts("No")
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc (o<<1|1)
using namespace std;
typedef long long ll;
//typedef __int128 i128;
typedef double db;
const int N=1e5+5;
int f[21][N],d[N],n,x,y,q;
vector<int> e[N],v[N];
ll a[N];
struct lb{
	lb(){
		fo(i,0,60) p[i]=0;
	}
	ll p[61];
	
	bool ins(ll x){
		fd(i,60,0) {
			if ((x>>i)&1) {
				if (p[i]) x^=p[i];
				else {
					p[i]=x;
					return 1;
				}
			}
		}
		return 0;
	}
	
	ll askmax() {
		ll ans=0;
		fd(i,60,0) ans=max(ans, ans^p[i]);
		return ans;
	}
};
vector<int> get(vector<int> t,int x){
	vector<int> temp;
	temp.clear();
	
	lb r;
	if (r.ins(a[x])) temp.push_back(x);
	for (int i:t) if (r.ins(a[i])) temp.push_back(i);
	return temp;
}
void dfs(int x,int y){
	v[x]=get(v[y], x);
	for (int v:e[x]) {
		if (v==y) continue;
		f[0][v]=x;
		d[v]=d[x]+1;
		dfs(v,x);
	}
}
int lca(int x,int y){
	if (d[x]<d[y]) swap(x,y);
	fd(k,20,0) if (d[f[k][x]]>=d[y]) x=f[k][x];
	fd(k,20,0) {
		if (f[k][x]^f[k][y]) x=f[k][x],y=f[k][y];
	}
	if (x!=y) return f[0][x];
	return x;
}
void work(int x,int y){
	lb t;
	
	int l=lca(x,y);
	for (int i:v[x]) if (d[i]>=d[l]) t.ins(a[i]);
	for (int i:v[y]) if (d[i]>=d[l]) t.ins(a[i]);
	
	cout<<t.askmax()<<"\n";
}
int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
	
	
	std::ios::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	
	cin>>n>>q;
	fo(i,1,n) cin>>a[i];
	fo(i,1,n-1) {
		cin>>x>>y;
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}

	f[0][1]=1;
	v[1].emplace_back(1);
	dfs(1,0);

	fo(j,1,20) fo(i,1,n) f[j][i]=f[j-1][f[j-1][i]];
	
	while (q--) {
		cin>>x>>y;
		work(x,y);
	}

	return 0;
}

[ABC223H] Xor Query

题面翻译

  • 给定一个长度为 \(N\) 正整数序列 \(A\)，\(Q\) 次询问。
  • 每次询问给出三个正整数 \(L\)、\(R\)、\(X\)，请你判断能否从原序列 \(A_L\)，\(A_{L+1}\)，... ,\(A_R\) 中选出若干个数使其异或和为 \(X\)。

首先需要注意的是，线性基的合并是n(logn)^2，而且这个log是60的级别，所以是不太能像上一道题一样，维护一个vector的，然后暴力插入的。

我们仍然像上一道题一样，记录一个1-i组成的线性基，并且其中的数尽量靠右。
具体来说，我们复制前一个数的线性基，然后我们插入\(a_i\)，使用一个贪心的策略
如果当前的数在i这一位有1，并且\(p_i\)不为0，则比较id的大小，让大的放在这一位，小的继续往后做，

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define eb emplace_back
#define pi pair<ll,ll>
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define fi first
#define se second
using namespace std;
typedef long long ll;
const ll inf = 1ll << 60;
const int N = 5e5 + 10;
struct lb {
    ll p[61], id[61];

    lb() {
        memset(p, 0, sizeof(p));
    }
    void clr() {
        memset(p, 0, sizeof(p));
    }

    void ins(ll x, ll y) {
        fd(i, 60, 0) {
            if ((x >> i) & 1) {
                if (!p[i]) {
                    p[i] = x; id[i] = y;
                    return;
                }
                else {
                    if (y > id[i]) {
                        swap(x, p[i]); swap(y, id[i]);
                    }
                    x ^= p[i];
                }
            }
        }
    }

    bool ask(ll x, ll y) {
        fd(i, 60, 0) {
            if ((x >> i) & 1) {
                if (!p[i] || id[i] < y) return 0;
                x ^= p[i];
            }
        }
        return !x;
    }
};
lb t[N];
ll n, q, a[N], l, r, x;
void solve()
{
    cin >> n >> q;
    fo(i, 1, n) cin >> a[i];

    fo(i, 1, n) {
        t[i] = t[i - 1];
        t[i].ins(a[i], i);
    }

    while (q--) {
        cin >> l >> r >> x;
        if (t[r].ask(x, l)) cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
}
int main()
{
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}

Square Subsets

题面翻译

Petya 又迟到了...老师给了他额外的任务。对于一些数组 \(a\)，Petya 需要找到从中间选择非空子集，使所有数的乘积为完全平方数的方法的数量。如果这些方法所选择的元素的索引不同，则认为这两种是不同的方法。 因为结果可能很大，结果需要 \(\bmod ~ 10^9+7\)。

将这些数根据他们的质因子数的情况看作一个二进制数，然后就是选出一些数使得异或和为0，
答案就是ans=2^(n-线性基大小)-1(非空)

#include<bits/stdc++.h>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define lc (o<<1)
#define rc ((o<<1)|1)
#define mk(x,y) make_pair((x),(y))
#define eb emplace_back
#define A puts("Yes")
#define B puts("No")
#define fi first
#define se second
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef long long i64;
const ll inf=1ll<<60;
const ll mo1=1e9+9;
const ll mo2=1e9+7;
const ll P=131;
const ll Q=13331;
const int N=5e5+5;
const int M=2e6+5;
const ll mo=1e9+7;
struct Base{
	ll p[35];
	ll rank=0;
	bool ins(ll x){
		fd(i,31,0) {
			if ((x>>i)&1) {
				if (!p[i]) {
					p[i]=x;
					rank++;
					return 1;
				}
				else x^=p[i];
			}
		}
		return 0;
	}
};
Base t;
ll n,x;
int p[100],tot;
bool vis[N];
ll power(ll a,ll b){
	ll t=1,y=a;
	while (b) {
		if (b&1) t=t*y%mo;
		y=y*y%mo;
		b/=2;
	}
	return t;
}
int main(){
//	freopen("data.in","r",stdin);

	fo(i,2,70) {
		if (!vis[i]) {
			p[++tot]=i;
		}
		fo(j,1,tot) {
			if (i*p[j]>70) break;
			vis[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}

	fo(i,0,tot-1) p[i]=p[i+1];
	
	scanf("%lld",&n);
	fo(i,1,n) {
		ll z=0,cnt;
		scanf("%lld",&x);
		fo(j,0,tot-1) {
			cnt=0;
			while (x%p[j]==0) {
				x/=p[j]; cnt++;
			}
			if (cnt&1) {
				z|=(1<<j);
			}
		}
		t.ins(z);
	}
	
	ll ans=power(2ll, n-t.rank);
	ans=(ans-1)%mo;
	ans=(ans%mo+mo)%mo;
	printf("%lld",ans);
	

	
	return 0;
}

标签：include,return,int,ll,线性,相关,fo,模板,define
From： https://www.cnblogs.com/ganking/p/18491511

相关文章

  • 图论模板
    最短路（dijkstra）无法处理负边权，时间复杂度O(mlogn)#include<bits/stdc++.h>#definefo(i,a,b)for(ll(i)=(a);(i)<=(b);(i)++)#definefd(i,b,a)for(ll(i)=(b);(i)>=(a);(i)--)#definelc(o<<1)#definerc((o<<1)|1)#definemk(x,y)make_pair((x),(......
  • 超详细介绍bash脚本相关细节
            Bash（BourneAgainSHell）是一种广泛使用的Unixshell和命令语言，它提供了一套强大的功能用于脚本编写和自动化任务。1.编写脚本方式和运行脚本方式sudovi名称.sh例如编写一个名称为a的脚本：运行方式1：先给权限再运行sudochmod+x文件名./文件名例......
  • [20241021]使用gdb查看修改内存地址以及相关值.txt
    [20241021]使用gdb查看修改内存地址以及相关值.txt--//执行oradebugpoke报错，感觉oracle已经禁止这类hack操作。1.环境：SYS@book>@ver2==============================PORT_STRING                  :x86_64/Linux2.4.xxVERSION              ......
  • 六、栈————相关概念详解
    栈————相关概念详解前言一、栈(stack)1.1栈是什么?1.2栈的类比二、栈的常用操作2.1初始化栈2.2元素入栈2.3访问栈顶元素2.4元素出栈2.5获取栈的长度2.6判断是否为空三、栈的实现3.1基于数组实现栈3.1.1代码演示3.1.2上述代码不足3.2基于链表实现栈3.2......
  • 公司网站后台修改模板？php修改网站后台？
    备份现有模板在进行任何修改之前，确保备份现有的模板文件。这可以防止在修改过程中出现错误导致数据丢失。使用FTP工具或通过服务器管理面板复制模板文件到本地或另一个安全位置。确定需要修改的内容明确你需要修改的具体内容，比如布局调整、颜色更改、添加新功能等。列......
  • 网站模板的网页背景修改？
    1.登录后台管理系统打开浏览器，访问你的网站后台管理系统。输入用户名和密码，登录到后台管理系统。2.导航到主题或样式设置在后台管理系统的主界面，找到并点击“主题设置”、“样式设置”或“外观设置”等相关选项。这些选项通常位于左侧导航栏或顶部菜单中。3.选择背景......
  • 《微分几何讲义（陈省身）》读书笔记 第二章 多重线性代数
    第二章多重线性代数Note：本文默认了基本的向量空间和矩阵的相关知识。本文中所有的向量空间默认是有限维的，且定义在一个域\(\mathbb{F}\)上。本文采用Einstein求和约定。§1张量积[Def1.1]对于向量空间\(V_1,\cdots,V_r\)和\(Z\)，若映射\(f:V_1\times\cdots\timesV......
  • podman 无根用户分配系统CPU、内存等系统资源，提示cgroup相关权限不足
    问题：在使用Podman以无根用户（rootless）模式创建容器时，如果遇到分配系统CPU等资源时提示cgroup权限不足，这是因为无根用户没有直接访问cgroup相关资源的权限。以下是一些解决方法（目前采用的办法3临时解决，，主要是更改系统目录权限sudochown-R$USER:$USER/sys/fs/cgro......
  • 高等数学 7.4一阶线性微分方程
    @目录一、线性方程*二、伯努利方程一、线性方程方程\[\cfrac{\mathrm{d}y}{\mathrm{d}x}+P(x)y=Q(x)\tag{1}\]叫做一阶线性微分方程，因为它对于未知函数\(y\)及其导数是一次方程。如果\(Q(x)\equiv0\)，那么方程\((1)\)称为齐次的；如果\(Q(x)\not\equiv0\)，那么方......
  • 关于Window10激活相关（自用，过期了再来看看）
    第一步：关闭所有防毒软件，还有Windows防火墙，非常重要，具体的就是：电脑设置-windows安全中心-病毒威胁巴拉巴拉。关闭实时保护，另外下拉打开排除项-添加巴拉巴拉：添加文件就是可以选压缩包等等，添加文件夹就是文件夹那些，会看不见压缩包，各取所需。不然就会出现类似不准打开或者解......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99