首页 > 其他分享 >洛谷 P4869 albus就是要第一个出场 题解

洛谷 P4869 albus就是要第一个出场 题解

时间:2023-07-11 14:55:43浏览次数:51  
标签:P4869 洛谷 pw int 题解 线性 xor operatorname rk

洛谷 P4869 albus就是要第一个出场

题意

给定一个长度为 \(n\) 的序列 \(A\),设可重集合 \(S=\left\{\operatorname{xor}_{i=1}^nA_ix_i\mid x_i\in\{0,1\}\right\}\),即 \(S\) 为 \(A\) 的所有子集的异或和构成的集合。

给定一个数 \(k\),求 \(k\) 在 \(S\) 中的排名。如果 \(S\) 中有多个 \(k\),取最小的排名。

\(1\le n\le10^5\),其他输入不超过 \(10^9\)。

思路

首先构造 \(A\) 的线性基 \(B\),设 \(\operatorname{span}(B)=\operatorname{span}(A)=S\)。由于可以一个数都不选,所以 \(0\in S\)。

如果集合 \(S\) 不可重,给定一个数 \(k\),如何求出它在 \(S\) 中的排名?保证 \(k\) 在 \(S\) 中出现。

我们从低到高考虑每一位。如果 \(B_i\) 不为空,并且 \(k\) 的第 \(i\) 位为 \(1\),说明我们需要取出 \(B_i\) 以构造出 \(k\)。根据线性基的性质,\(B_i\) 的高位为 \(0\),且 \(B\) 中其他数的第 \(i\) 位为 \(0\),所以必须取出 \(B_i\),且取出 \(B_i\) 不影响之前和之后的操作。至于其他没考虑到的位,由于保证可以构造出 \(k\),因此可以不用管。

求排名 \(rk\) 的具体代码如下:

int rk = 0, pw = 1;
f(i, 0, 30) if (B[i]) {
    if (k >> i & 1) rk += pw;
    pw <<= 1;
}

取出第 \(i\) 个线性基,对应的贡献是 \(2^{i-1}\)。可以对照一个例子:

  • 线性基为 \(\{00100,01001,10011\}\),能构造出的数的集合为 \(\{00100,01001,01101,10011,10111,11010,11110\}\)。

现在考虑集合 \(S\) 可重的情况。设 \(f(s)=\operatorname{xor}_{s}x\),其中 \(s\) 为某个集合。

考虑插入线性基的过程,插入线性基失败即是出现了重复。

设一个插入线性基失败的数为 \(x\),那么存在 \(B'\subseteq B\) 使得 \(f(B')\operatorname{xor}x=0\)。设 \(x\) 对应的 \(B'\) 为 \(B_x\)。

根据异或的性质,如果用线性基中的数能构造出 \(y\),设 \(y=f(Y)\)(\(Y\subseteq A\)),那么 \(y\) 也等于 \(f(Y)\operatorname{xor}f(B_x)\operatorname{xor}x\),其中 \(x\) 是某个插入线性基失败的数。

对于每个 \(y\),用线性基中的数构造的方案是唯一的(否则不符合线性基的定义);而 \(x\) 对应的 \(B_x\) 也是唯一的。因此对于每个 \(x\) 都可以用或不用,所以每个 \(y\) 的总方案数都要乘以 \(2^{n-|B|}\)。

于是答案为 \(rk\times2^{n-|B|}+1\)。

代码

\(2^{n-|B|}\) 可以在插入线性基的同时计算出来,这样就不需要用到快速幂了。

\(rk<2^{31}\),所以可以最后再取模。

#include <bits/stdc++.h>
#define f(x, y, z) for (int x = (y); x <= (z); ++x)
#define g(x, y, z) for (int x = (y); x >= (z); --x)
using namespace std;
int constexpr MOD = 10086;
int n, rk, pw = 1, B[32], c = 1;

void ins(int x) {
    g(i, 30, 0) if (x >> i & 1) {
        if (!B[i]) return B[i] = x, void();
        x ^= B[i];
        if (!x) return (c <<= 1) %= MOD, void();
    }
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    
    cin >> n;
    int x; 
    f(i, 1, n) cin >> x, ins(x);
    cin >> x;
    f(i, 0, 30) if (B[i]) {
        if (x >> i & 1) (rk += pw) %= MOD;
        (pw <<= 1) %= MOD;
    }
    cout << (rk * c + 1) % MOD << '\n';
    
    return 0;
}

标签:P4869,洛谷,pw,int,题解,线性,xor,operatorname,rk
From: https://www.cnblogs.com/f2021ljh/p/17544636.html

相关文章

  • AT_abc306_h 题解
    AT_abc306_hBalanceScale题解Links洛谷AtCoderDescription有\(N\)个编号为\(1,2,\dots,N\)的砝码。有\(M\)次比较操作,每次比较砝码\(A_{i}\)和\(B_{i}\),\(A_{i}\)在左侧。分为三种情况:左边的砝码更重。右边的砝码更重。两边的砝码重量相同。将每次比较的......
  • CF878E 题解
    CF878ENumbersontheblackboard题解Links洛谷CodeforcesDescription给出\(n\)个数字,每次询问一个区间\([l,r]\),对这个区间内部的点进行如下操作。每次操作可以合并相邻两个数\(x,y\),用\(x+2y\)替换它们。对于每次询问,输出当最后只剩下一个数字时,这个数字的最大......
  • 洛谷 P6109 - [Ynoi2009] rprmq1
    首先将修改操作差分为\(l_1\)时刻给\([l_2,r_2]\)中的值\(+v\),\(r_1+1\)时刻给\([l_2,r_2]\)中的值\(-v\)。这样第\(i\)行的状态相当于执行\(1\simi\)时刻的操作后的状态。猫树分治,把一个询问挂在线段树上满足\(l\lel_1\lemid\ler_1\ler\)的区间\([l,r]\)......
  • 洛谷P4715 【深基16.例1】淘汰赛
    写在前面这是本蒟蒻的第三篇题解。由于作者水平不高,本题解存在有数量庞大的错误。对于题解中的错误、可优化部分,欢迎各位大佬批评指正!不合适的部分,还请多多包涵!本题目来源于洛谷。网址https://www.luogu.com.cn/problem/P4715。本博客非营利性,如遇侵权,请联系作者删除,谢谢!题面......
  • CODE FESTIVAL 2017 Final J 题解
    problem&blog。萌萌点分治,积累个trick/qq。对于完全图\((V,E)\),将\(E\)分成\(E_1,E_2,\cdots,E_k\)(\(E_1\cupE_2\cup\cdots\cupE_k=E\))。对每个边集求MST,得到新边集\(E_1^{'},E_2^{'},\cdots,E_k^{'}\),再求MST。最终剩下的边集,等同于原边集的MST。......
  • P4016题解
    本题是一个比较经典的问题(环形均分纸牌问题),我也不知道为什么它在网络流24题里面出现。但是作为一道比较典的排序算法的题,还是放出来讲一下。solution假设\(a_1\)给\(a_n\)了\(x_1\)张纸牌,\(a_2\)给\(a_1\)了\(x_2\)张纸牌......(\(x_i\)可正可负)。因此操作数量为......
  • P2886题解
    题目大意给定起点\(S\)和终点\(T\),求从起点到终点恰好经过\(N\)(\(N\)给定)条边的最短路径。solution发现本题点数巨多,但是边数小到可怜,我们可以只保留了一部分点,先判断连通性,不连通直接输出即可。当\(S\)和\(T\)连通时,我们设\(G^k\)为经过\(k\)条边后最短路的邻......
  • Largest-Smallest-Cyclic-Shift题解
    题目链接本题码量不大,但是事实上是一道极其难想的思维题。题目描述你有\(a\)个a,\(b\)个b,\(c\)个c。要求用这\(a+b+c\)个字母拼接成一个字符串,使得这个字符串的最小表示法在所有能拼成的字符串中最大。补充:最小表示法,将一个字符串的最后一个字符放到首位,重复这个操作,......
  • AT-abc214-g题解
    题目描述给定两个排列\(p,q\),要求统计满足\(\foralli,r_i\not=p_i,r_i\not=q_i\)的排列\(r\)的数量。对\(1000000007\)取模数据范围\(n\le3000\)。solution本题要求统计数量,反正我想了半天没想到怎么正向统计(bushi),因此我们考虑容斥。设\(h_i\)为只看其中......
  • P3599题解
    本题是一道比较典的构造题,拿来扩宽扩宽大家的眼界吧。Task1试判断能否构造并构造一个长度为\(n\)的\(1\simn\)的排列,满足其\(n\)个前缀和在模\(n\)的意义下互不相同。很容易想到的一点是:\(n\)一定排在第一位,因为如果排在别的位,加上\(n\)后在模\(n\)意义下是不......