문제 목록 개인이 작성한 것이 아닌 요약입니다
P3812 [템플] 선형 기저
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int D = 64;
ll base[D];
bool flag;
bool insert(ll x) {
for (int i = D - 1; i >= 0; i--) {
if ((x >> i) & 1) {
if (base[i])
x ^= base[i];
else {
base[i] = x;
return true;
}
}
}
return false;
}
void simplify() {
for (int i = D - 1; i >= 0; i--) {
if (base[i]) {
for (int j = D - 1; j > i; j--)
if ((base[j] >> i) & 1)
base[j] ^= base[i];
}
}
}
ll val[D];
ll max_xor(ll k) {
int cnt = 0;
for (int i = 0; i < D; i++)
if (base[i] != 0)
val[cnt++] = base[i];
if (k >= (1ll << cnt))
return -1;
ll ans = 0;
for (int i = 0; i < cnt; i++)
if ((k >> i) & 1)
ans ^= val[i];
return ans;
}
int main() {
int n, m;
cin >> n;
for (int i = 1; i <= n; i++) {
ll x;
cin >> x;
flag |= (!insert(x));
}
simplify();
cin >> m;
for (int i = 1; i <= m; i++) {
ll k;
cin >> k;
if (flag)
k--;
cout << max_xor(k) << endl;
}
return 0;
}
LOJ114
문제의 핵심은 $n$개의 수와 $q$번의 쿼리, 각각 $k$에 대해 모든 부분집합의 XOR 값을 정제한 후 $k$번째 작은 값을 구하는 것입니다.
선형 기저를 보다 간단히 정리할 수 있습니다. 각 $i$에 대해 최상위 비트가 $i$인 수로 다른 모든 $i$ 비트가 0인 수를 XOR 처리합니다. 이로 인해 기저는 다음과 같은 속성을 갖게 됩니다:
- 모든 수의 최상위 비트가 서로 다릅니다.
- 각 $i$에 대해, $v_i$의 최상위 비트가 $i$이면 다른 수의 $i$ 비트는 반드시 0입니다. 이러한 기저 $B = {v_0, \dots , v_k}$를 통해 $span(B)$ 내의 모든 요소를 오름차순으로 정렬하면 $0, v_0, v_1, v_0 \oplus v_1, v_2, \dots$와 같이 나타나며, 이로써 $k$번째 작은 값 계산이 가능해집니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int D=64;
ll base[D];
bool flag;
bool insert(ll x){
for(int i=D-1;i>=0;i--){
if((x>>i)&1){
if(base[i]) x^=base[i];
else{
base[i]=x;
return true;
}
}
}
return false;
}
void simplify(){
for(int i=D-1;i>=0;i--){
if(base[i]){
for(int j=D-1;j>i;j--)
if((base[j]>>i)&1)
base[j]^=base[i];
}
}
}
ll val[D];
ll max_xor(ll k){
int cnt = 0;
for (int i = 0; i < D; i++)
if (base[i] != 0)
val[cnt++] = base[i];
if (k >= (1ll << cnt))
return -1;
ll ans = 0;
for (int i = 0; i < cnt; i++)
if ((k >> i) & 1)
ans ^= val[i];
return ans;
}
int main(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
flag|=(!insert(x));
}
simplify();
cin>>m;
for(int i=1;i<=m;i++){
ll k;
cin>>k;
if(flag) k--;
cout<<max_xor(k)<<endl;
}
return 0;
}
P4570 [BJWC2011] 요소
$n$개의 물건이 주어지며, 각 물건은 번호 $a_i$와 가치 $b_i$를 가집니다. 일부 물건을 선택하여 번호의 비어있지 않은 부분집합의 XOR 합이 0이 되지 않도록 하면서 가치 합을 최대화하세요. $1\leq n \leq 1000$, $1\leq a_i \le 10^{18}$, $1\leq b_i \le 10^4$.
가치가 높은 순서대로 처리하고, 새로운 요소를 삽입할 수 있는지 확인하면 됩니다. 선형 기저를 사용하여 판단할 수 있으며, 시간 복잡도는 $\mathcal{O}(n(log V + log n))$입니다. 증명은 벡터 공간과 그 독립 집합이 유사한 구조를 가진다는 점에서 설명할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int D=64,N=1005;
#define ll long long
ll base[D],n;
struct s{
ll a,b;
}a[N];
bool cmp(s a,s b){
return a.b>b.b;
}
bool insert(ll x){
for(int i=D-1;i>=0;i--){
if((x>>i)&1){
if(base[i]) x^=base[i];
else{
base[i]=x;
return true;
}
}
}
return false;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].a>>a[i].b;
}
sort(a+1,a+n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i++){
if(insert(a[i].a)) ans+=a[i].b;
}
cout<<ans<<endl;
return 0;
}
P4151 [WC2011] 최대 XOR 경로
$n$개의 정점과 $m$개의 무방향 간선이 주어지며, 간선 가중치 $w_i$가 있습니다. $1 \to n$ 경로 중 XOR 합이 가장 큰 값을 구하세요. $1 \le n \le 50000, 1 \le m \le 10^5, 0 ≤ w_i ≤ 10^{18}$
임의의 생성 트리 $T$와 루트 $r$을 선택하고, $f(u)$를 $u \to r$ 경로의 XOR 합으로 정의합니다. 임의의 $1 \to n$ 경로 $P$에 대해, XOR 합은 $f(1) \oplus f(n) \oplus \left ( \bigoplus_{(u_i,u)\notin T} f(u_i) \oplus f(u_{i+1}) \oplus w(u_i,u_{i+1}) \right )$로 표현됩니다. 이를 바탕으로 선형 기저를 구성하고, 최대 XOR 값을 계산합니다.
#include <bits/stdc++.h>
using namespace std;
const int N=50005,M=200005,D=64;
#define ll long long
ll h[N],e[M],ne[M],W[M],idx;
ll f[N],base[D];
bool vis[N];
bool insert(ll x){
for(int i=D-1;i>=0;i--) {
if((x>>i)&1){
if(base[i]) x^=base[i];
else{
base[i]=x;
return true;
}
}
}
return false;
}
void simplify(){
for(int i=D-1;i>=0;i--){
if(base[i]!=0){
for(int j=D-1;j>i;j--)
if((base[j]>>i)&1) base[j]^=base[i];
}
}
}
ll max_val(ll x){
ll ans=x;
for (int i=D-1;i>=0;i--)
ans=max(ans,ans^base[i]);
return ans;
}
void add(int u,int v,ll w){
e[idx]=v,W[idx]=w,ne[idx]=h[u],h[u]=idx++;
}
void dfs(int u,ll ans){
f[u]=ans,vis[u]=1;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!vis[j]) dfs(j,ans^W[i]);
else insert(ans^W[i]^f[j]);
}
}
int main(){
memset(h,-1,sizeof(h));
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
add(u,v,w);add(v,u,w);
}
dfs(1,0);
simplify();
cout<<max_val(f[n])<<endl;
return 0;
}
CF724G Xor-matic Number of the Graph
$n$개의 정점과 간선이 있는 무방향 그래프가 주어집니다. $u < v$인 쌍 $(u,v)$가 유효한 조건은 $u$에서 $v$로 가는 경로의 XOR 합이 $w$인 경우입니다. 모든 유효한 쌍의 $w$ 합을 $10^9+7$로 나눈 값을 구하세요.
$u$에서 $v$로 가는 모든 경로의 XOR 합은 $d_u \oplus d_v \oplus B$로 표현됩니다. 이를 바탕으로 각 비트별로 계산하여 결과를 합산합니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
const int D=64,N=100005,M=N*4,P=1e9+7;
ll h[N],e[M],ne[M],W[M],idx;
ll base[D],f[N],s[N],cnt,total;
bool vis[N];
bool insert(ll x){
for(int i=60;i>=0;i--){
if((x>>i)&1){
if(base[i]) x^=base[i];
else{
base[i]=x;
++cnt;
return true;
}
}
}
return false;
}
void add(int u,int v,ll w){
e[idx]=v,W[idx]=w,ne[idx]=h[u],h[u]=idx++;
}
void dfs(int u,ll ans){
f[u]=ans,vis[u]=1,s[++total]=u;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(!vis[j]) dfs(j,ans^W[i]);
else insert(ans^W[i]^f[j]);
}
}
signed main(){
memset(h,-1,sizeof(h));
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
ll u,v,w;
cin>>u>>v>>w;
add(u,v,w),add(v,u,w);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(vis[i]==0){
memset(base,0,sizeof(base));
cnt=total=0;
dfs(i,0);
for(int j=0;j<60;j++){
ll c=(1ll<<j)%P;
bool ok=0;
for(int k=60;k>=0;k--) if((base[k]>>j)&1) ok=1;
if(ok) ans=(ans+(ll)total*(total-1)/2%P*((1ll<<cnt-1)%P)%P*c)%P;
else{
int x=0;
for(int i=1;i<=total;i++) if((f[s[i]]>>j)&1) ++x;
ans=(ans+(ll)x*(total-x)%P*((1ll<<cnt)%P)%P*c)%P;
}
}
}
}
cout<<ans%P<<endl;
return 0;
}
선형 기저와 데이터 구조의 결합
- 선형 기저 삽입 시간 복잡도: $\mathcal{O}(\log V )$.
- 선형 기저 병합 시간 복잡도: $\mathcal{O}(\log^2 V )$, 한쪽의 모든 요소를 다른 쪽에 삽입하는 방식.
CF1100F Ivan and Burgers
길이 $n$의 배열 $a$가 주어지고, $q$개의 쿼리가 있습니다. $a_l$부터 $a_r$까지의 요소 중 일부를 선택하여 XOR 합이 최대가 되는 값을 구하세요. $1 \le n, q \le 5 × 10^5, 0 \le a_i \le 10$.
선형 기저를 사용하여 해결할 수 있습니다. 직접 세그먼트 트리로 구현할 경우 시간 복잡도는 $O((n+q)\log^3 n)$이 되며, 이는 효율적이지 않습니다. 분할 정복 기법을 사용하여 중간 지점을 기준으로 처리합니다.
#include <bits/stdc++.h>
using namespace std;
const int N=500005;
struct ss{
int s[20];
void insert(int x){
if(x)
for(int i=19;i>=0;i--)
if(x>>i&1){
if(!s[i]) {s[i]=x;break;}
x^=s[i];
}
}
void clear(){
memset(s,0,sizeof(s));
}
}d[N];
int merge(ss a,ss b){
for(int i=19;i>=0;i--) a.insert(b.s[i]);
int res=0;
for(int i=19;i>=0;i--)
res=max(res,res^a.s[i]);
return res;
}
int a[N],n,q[N],qL[N],qR[N],ans[N],m;
void solve(int l,int r,int L,int R){
if(L>R) return;
if(l==r){
for(int i=L;i<=R;i++) ans[q[i]]=a[l];
return;
}
static int tmpL[N],tmpR[N];
int tL=0,tR=0,mid=l+r>>1;
d[mid].clear();d[mid].insert(a[mid]);
for(int i=mid-1;i>=l;i--) (d[i]=d[i+1]).insert(a[i]);
for(int i=mid+1;i<=r;i++) (d[i]=d[i-1]).insert(a[i]);
for(int i=L;i<=R;i++){
if(qL[q[i]]<=mid){
if(qR[q[i]]>mid) ans[q[i]]=merge(d[qL[q[i]]],d[qR[q[i]]]);
else tmpL[++tL]=q[i];
}
else tmpR[++tR]=q[i];
}
for(int i=1;i<=tL;i++)q[L+i-1]=tmpL[i];
for(int i=1;i<=tR;i++)q[L+tL+i-1]=tmpR[i];
solve(l,mid,L,L+tL-1);
solve(mid+1,r,L+tL,L+tL+tR-1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)cin>>qL[i]>>qR[i],q[i]=i;
solve(1,n,1,m);
for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
return 0;
}
P3292 [SCOI2016] 행운의 숫자
이중 증가의 아이디어를 사용하여 $g_{i,j}$는 $i$가 $2^j$만큼 올라간 선형 기저를 나타냅니다. DP 과정에서 두 $g_{i,j-1}$와 $g_{fa_{i,j-1},j-1}$를 병합합니다. 시간 복잡도는 $\mathcal{O}(N\log N\times 64)$입니다.
#include<bits/stdc++.h>
using namespace std;
const int M=20005,D=64;
typedef long long ll;
ll a[100005],n;
struct s{
ll w[64];
s(){ memset(w,0,sizeof(w)); }
void insert(ll x){
for(int i=D-1;i>=0;i--){
if(!((x>>i)&1)) continue;
if(!w[i]){w[i]=x;return ;}
x^=w[i];
}
}
ll mx(){
ll ans=0;
for(int i=D-1;i>=0;i--)
ans=max(ans,ans^w[i]);
return ans;
}
};
s merge(s u,s v){
for(int i=D-1;~i;i--)
if(v.w[i]) u.insert(v.w[i]);
return u;
}
int idx,ne[2*M],h[2*M],e[2*M];
void add(int x,int y){
e[++idx]=y,ne[idx]=h[x],h[x]=idx;
}
int f[M][21],dep[M];
s g[M][21];
void dfs(int u,int fa){
f[u][0]=fa;
g[u][0].insert(a[fa]);
dep[u]=dep[fa]+1;
for(int i=h[u];i;i=ne[i]){
int to=e[i];
if(to!=fa) dfs(to,u);
}
}
ll query(int x,int y){
if(dep[x]>dep[y])swap(x,y);
s t;
t.insert(a[x]),t.insert(a[y]);
for(int i=20;i>=0;i--){
if(dep[f[y][i]]>=dep[x]) t=merge(t,g[y][i]),y=f[y][i];
}
if(x==y)return t.mx();
for(int i=20;i>=0;i--){
if(f[x][i]!=f[y][i]){
t=merge(t,g[x][i]);
t=merge(t,g[y][i]);
x=f[x][i],y=f[y][i];
}
}
t=merge(t,g[x][0]);
return t.mx();
}
int main(){
int q;
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
int x,y;
cin>>x>>y;
add(x,y),add(y,x);
}
dfs(1,0);
for(int j=1;j<=20;j++){
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
g[i][j]=merge(g[f[i][j-1]][j-1],g[i][j-1]);
}
}
while(q--){
int x,y;
cin>>x>>y;
cout<<query(x,y)<<endl;
}
return 0;
}
P5607 [Ynoi2013] 돌아올 수 없는 NOI2017
구간 정보를 유지하기 위해 세그먼트 트리로 구간 선형 기저를 유지합니다. 차분을 사용하여 구간 수정을 두 개의 단일 수정으로 변환합니다. 시퀀스 $b$는 $b_i = a_i \oplus a_{i-1}$를 만족하며, $a_x = b_1 \oplus b_2 \oplus ... \oplus b_x$입니다. 구간 $[l,r]$의 경우, $a_l$과 $b_{l+1}, ..., b_r$의 선형 기저를 사용합니다.
세그먼트 트리에서 두 선형 기저 병합 시간 복잡도는 $O(\log^2V)$이며, 총 시간 복잡도는 $O(n\log + n\log^2V)$입니다.
#include <bits/stdc++.h>
#define L(u) (u<<1)
#define R(u) (u<<1|1)
#define mid ((l+r)>>1)
using namespace std;
const int N = 50050;
struct XOR {
int d[30], s;
void init() {memset(d, 0, sizeof d);}
void insert(int x) {
for(int i = 29; i >= 0; --i)
if((x >> i) & 1) {
if(d[i]) x ^= d[i];
else {d[i] = x; break;}
}
}
} t[N << 2]; int a[N], n, m;
XOR merge(XOR a, XOR b) {
XOR res; res.init();
for(int i = 29; i >= 0; --i) if(a.d[i]) res.d[i] = a.d[i]; else res.d[i] = b.d[i];
for(int i = 29; i >= 0; --i) if(a.d[i] && b.d[i]) res.insert(b.d[i]);
res.s = a.s ^ b.s; return res;
}
void P(int u) {t[u] = merge(t[L(u)], t[R(u)]);}
void build(int u, int l, int r) {
if(l == r) {t[u].insert(t[u].s = a[l]); return;}
build(L(u), l, mid); build(R(u), mid+1, r); P(u);
}
void modify(int u, int l, int r, int p, int x) {
if(l == r) {t[u].init(), t[u].insert(t[u].s ^= x); return; }
p <= mid ? modify(L(u), l, mid, p, x) : modify(R(u), mid+1, r, p, x); P(u);
}
int finds(int u, int l, int r, int p) {
return l == r ? t[u].s : (p <= mid ? finds(L(u), l, mid, p) : finds(R(u), mid+1, r, p) ^ t[L(u)].s);
}
XOR findi(int u, int l, int r, int tl, int tr) {
if(tl <= l && r <= tr) return t[u];
if(tl > mid) return findi(R(u), mid+1, r, tl, tr);
if(tr <= mid) return findi(L(u), l, mid, tl, tr);
return merge(findi(L(u), l, mid, tl, tr), findi(R(u), mid+1, r, tl, tr));
}
int main() {
cin>>n>>m;
for(int i = 1; i <= n; ++i) cin>>a[i];
for(int i = n-1; i; --i) a[i+1] ^= a[i];
build(1, 1, n);
for(int opt, l, r, x; m--; ) {
cin>>opt>>l>>r>>x;
if(opt == 1) {
modify(1, 1, n, l, x);
if(r < n) modify(1, 1, n, r+1, x);
} else {
int tmp = finds(1, 1, n, l);
if(l == r) cout<<max(x, x^tmp)<<endl;
else {
XOR t = findi(1, 1, n, l+1, r); t.insert(tmp);
for(int i = 29; i >= 0; --i) x = max(x, x ^ t.d[i]);
cout<<x<<endl;
}
}
}
}
P3389 [템플] 가우스 소거법
#include<bits/stdc++.h>
using namespace std;
int n,pl;
double a[1001][1001];
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++){
pl=i;
for(int j=i;j<=n;j++)
if(fabs(a[j][i])>fabs(a[pl][i])) pl=j;
if(a[pl][i]==0) {cout<<"No Solution";return 0;}
for(int j=1;j<=n+1;j++)
swap(a[i][j],a[pl][j]);
double k=a[i][i];
for(int j=1;j<=n+1;j++)
a[i][j]=a[i][j]/k;
for(int j=1;j<=n;j++){
if(i!=j){
double ki=a[j][i];
for(int m=1;m<=n+1;m++)
a[j][m]=a[j][m]-ki*a[i][m];
}
}
}
for(int i=1;i<=n;i++)
printf("%.2lf\n",a[i][n+1]);
return 0;
}
P2447 [SDOI2010] 외성 천족충
선형 기저를 사용하면 방정식의 유일한 해는 $rk(S) =n$인 경우입니다. 행렬의 계수는 모든 요소를 선형 기저에 삽입한 후 선형 기저에 포함된 요소의 수와 같습니다. 따라서 방정식을 선형 기저에 차례로 삽입하면 됩니다. 시간 복잡도는 $\mathcal{O}(\frac{n^2m}{ω})$입니다.
#include <bits/stdc++.h>
using namespace std;
char s[1010];
bitset<1010> a[2010];
int f(int n, int m){
int ans = -1;
for (int i = 1; i <= n; i++){
int cur = i;
while (cur <= m && !a[cur].test(i)) cur++;
if (cur > m) return 0;
ans = max(ans, cur);
if (cur != i)swap(a[cur], a[i]);
for (int j = 1; j <= m; j++)
if (i != j && a[j].test(i))
a[j] ^= a[i];
}
return ans;
}
int main(){
int n, m;
cin>>n>>m;
for (int i = 1, res; i <= m; i++){
cin>>s>>res;
for (int j = 0; j < n; j++)
a[i].set(j+1,s[j]=='1');
a[i].set(0, res);
}
int ret = f(n, m);
if (ret){
cout<<ret<<endl;
for (int i = 1; i <= n; i++)
cout<<(a[i].test(0) ? "?y7M#" : "Earth") <<endl;
}
else cout<<"Cannot Determine\n"<<endl;
return 0;
}
CF24D 깨진 로봇
$n$행 $m$열의 행렬에서 $(x,y)$에 위치해 있으며, 각각 왼쪽, 오른쪽, 아래로 이동하거나 원래 위치에 머무를 수 있습니다. 마지막 행에 도달하는 기대값을 구하세요. $1\le n,m\le 10^3$, $1\le x\le n$, $1\le y\le m$.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int N = 1010;
int n, m;
int x, y;
double f[N][N];
double a[N][N];
void gauss()
{
for (int i = 1; i <= m; i ++ )
{
double t = a[i + 1][i] / a[i][i];
int d[3] = {i, i + 1, m + 1};
for (int j = 0; j < 3; j ++ )
a[i + 1][d[j]] -= t * a[i][d[j]];
a[i + 1][i] = 0;
}
for (int i = m; i; i -- )
{
a[i - 1][m + 1] -= a[i - 1][i] / a[i][i] * a[i][m + 1];
a[i - 1][i] = 0;
}
}
int main()
{
cin >> n >> m;
cin >> x >> y;
if (m == 1) printf("%.4lf\n", 2.0 * (n - x));
else
{
for (int i = n - 1; i >= x; i -- )
{
a[1][1] = 2.0 / 3, a[1][2] = -1.0 / 3, a[1][m + 1] = f[i + 1][1] / 3 + 1;
a[m][m] = 2.0 / 3, a[m][m - 1] = -1.0 / 3, a[m][m + 1] = f[i + 1][m] / 3 + 1;
for (int j = 2; j < m; j ++ )
{
a[j][j - 1] = -1.0 / 4, a[j][j] = 3.0 / 4, a[j][j + 1] = -1.0 / 4;
a[j][m + 1] = f[i + 1][j] / 4 + 1;
}
gauss();
for (int j = 1; j <= m; j ++ ) f[i][j] = a[j][m + 1] / a[j][j];
}
cout.setf(std::ios::fixed);
cout << setprecision(4) << f[x][y];
//cout << f[x][y];
}
return 0;
}