Atcoder abc274

發表於 2022-10-22 更新於 2024-10-23 分類於 Atcoder ， ABC Disqus：文章字數： 3.1k 所需閱讀時間 ≈ 10 分鐘

G(网络流)Ex(rolling hash,Nim积,Nimber(TODO证明),二分)

https://atcoder.jp/contests/abc274/tasks

G - Security Camera 3

给定 h行W列, 一些地方是障碍

问最少安装多少摄像头, 能监控所有非障碍区域,

一次安装在一个非障碍区域并监控它自身和朝向(4向)的一段连续的非障碍区域

同一个地方可以安装多个不同向的

范围

h,w 300

1024mb

我的思路

把连续一段横着或者竖着看作一个单位

那么对于(i,j) 所在的横的r_x, 和竖的c_y

有关系r_x+c_y >= 1

所有 r和c的取值只能1/0

要所有r+c 的和最小

似乎是个线性规划?

题解

就是网络流最小割

S和行一起表示选行(所以行到 T 容量1), T和行一起表示不选行

T和列一起表示选列(所以 S 到列容量1), S和列一起表示不选列

如果(i,j) 对应的行列同时不选则不合法, 列->行容量无限大

代码

https://atcoder.jp/contests/abc274/submissions/36107290

#include <bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
int read(){int r;scanf("%d",&r);return r;}
char s[310][310];
int main(){
  int h=read();
  int w=read();
  rep(i,0,h)scanf("%s",s[i]);
  auto x=vector(h,vector(w,0)); // 以首个为行标识
  auto y=vector(h,vector(w,0)); // 以首个+hw为列标识
  const int S=2*h*w;
  const int T=S+1;
  atcoder::mf_graph<int>g(T+1);
  rep(i,0,h)rep(j,0,w)if(s[i][j]=='.'){
    int curi=i*w+j;
    int curj=curi+h*w;
    x[i][j]=(i&&s[i-1][j]=='.')?x[i-1][j]:curi;
    y[i][j]=(j&&s[i][j-1]=='.')?y[i][j-1]:curj;
    if(x[i][j]==curi)g.add_edge(S,curi,1);
    if(y[i][j]==curj)g.add_edge(curj,T,1);
    g.add_edge(x[i][j],y[i][j],1000000000);
  }
  printf("%d\n",g.flow(S,T));
}

Ex - XOR Sum of Arrays

S(B,C) = 按位xor B和C 得到的序列(B和C长度相同)

给定非负长n序列A

q个询问

每次问 S(A[l0..r0],A[l1..r1]) 的字典序是否严格小于 A[l2..r2]

范围

n 5e5

ai [0,1e18]

r0-l0=r1-l1

1024mb

我的思路

感觉可以先干掉 r,

因为可以先 [l.. 的后缀运算后, 再去r截断

那么其实会得到的就是 [l0... xor [l1... 与 [l2... 首个不等关系的长度

问题是这样的话其实是个三维状态 O(N^3)

虽然倒着算可以让均摊时间到O(1)

pos[l0][l1][l2] = (s[l0]^s[l1] != s[l2]) ? 1 : (pos[l0+1][l1+1][l2+1] + 1)

然后如果有r 其实就是和长度比就完了, O(1) 判断

那么有啥办法能让pos快速计算(而不是存储), 或者状态压缩呢

其实根据上面的来说, 每次计算是O(N) 每次暴力只需要O(NQ)

题解

如果不是 xor 而是加法

那么可以O(1) 算出任何H(S[l0..r0],S[l1..r1]) rolling hash

那么可以倍增/2分的思想找到两个结果首个不等的位置, 再做字符比较

原问题

关键就是如何计算 $H(B \oplus C)$ 以后的hash

用Nimber(Nim number)

不用Nimber

还是字符串hash, 但是把乘法变成不一定可逆的bit矩阵运算

$(v_0) \oplus (v_1 \cdot x) \oplus (v_2 \cdot x^2) \oplus \cdots$

也就是这里的$\cdot$需要能让$\mathrm{H}(A) ? \mathrm{H}(B) = \mathrm{H}(A \oplus B) $ 成立, 也就不能是数乘

这里考虑$v_i \cdot x^{t} = f_t(v_i)$

然后$f_t(v) = f_{2^{k_0}}(f_{2^{k_1}}(\cdots(v))), k_0 > k_1 > \cdots$, 其中$2^k$是对$t$的二进制从高到低拆分(唯一)

而每个$f_{2^k}(v) $ 是一个把数按照 bit 做线性变换(不一定可逆)的方案, 这样随机选方案就是一个办法

这里因为是hash ,其实完全对逆运算没有要求, 虽然也可以造 bit * bit的可逆轮换矩阵,再矩阵前缀, 缺点是这样要n个矩阵

而去掉可逆的需求, 直接二进制拆分+ 倍增想法就可以有上面的

所以实际需要的

快速: (O(1) /O(log n) 时间计算一段的hash
相等: 一个$\cdot$运算$(v_0) \oplus (v_1 \cdot x) \oplus (v_2 \cdot x^2) \oplus \cdots$
hash难hack

所以nimber有一点远大于要求了,

Nimber(Nim add(xor) 和 Nim product)

显然 xor 和数乘和数加不满足交换结合率

如果有 xor(nim add) 配套的 nim product, 那么就不需要使用数乘和数加

这里面运算的加为$\oplus$,乘为$\otimes$, 这样的field为Nimber

性质

$\oplus$ 加

xor 的性质老生长谈了, 可以看成按位拆开求和mod2 显然有交换,结合, $0$为零元

实际上 nim和 还可以写成递归定义 $x\oplus y=\text{mex}\lbrace\lbrace x’\oplus y|x’ < x\rbrace\cup\lbrace x\oplus y’|y’ < y\rbrace\rbrace$

两者等价, 首先$v = x \oplus y $ 一定不在集合中因为只有唯一的$y$能让$x \oplus y = v$, 因此

其次对所有 $0\le z < x\oplus y$, 计算所有对应 $w = x\oplus y \oplus z$,

考虑$w$的高位1来源,只可能和$x,y,z$中的(注来不一定是$x,y,z$的最高位)

又 $w\oplus z = x\oplus y > z$, 所以不可能来自$z$ (相当于从高到低做 bit xor, 而在w的高位时 xor后是0, z是1

那么显然$w\oplus x < x$ 或 $w\oplus y < y$ (在w高位以上相等, 在w位两个1 xor掉了

因此可以写成递归的形式

加的逆运算 $a \ominus b = a \oplus b$ 显然

$\otimes$ 乘

需要找一个field(Commutable field (Wikipedia)), $A$为包含$[0,2^{2^n})$的集合

$a \otimes b := \text{mex} \lbrace (a’ \otimes b) \oplus (a \otimes b’) \oplus (a’ \otimes b’) \vert 0 \le a’ \lt a, 0 \le b’ \lt b \rbrace.$

交换 $a\otimes b=b\otimes a$ 定义显然

零元 $0\otimes a=0$ 空集合 mex=0

乘法逆元 $a\otimes b = 1$ 任意$a\neq 0$存在$b$

单位元 $1\otimes a =a$ 因为一次取值$0$,另一测取值$[0,a-1]$, mex{0..a-1}=a

结合率 $a\otimes b \otimes c= a\otimes(b\otimes c)$

分配率 $(a\oplus b)\otimes c= (a\otimes c)\oplus(b \otimes c)$

大概想法是需要满足上面这些那么有

$a \otimes b \neq a’\otimes b, b\neq 0, \forall a’\neq a $

$a \otimes b \neq a\otimes b’, a\neq 0, \forall b’\neq b $

那么$(a\ominus a’)(b\ominus b’) \neq 0$, 非零元的乘运算非零(否则可以通过乘法逆元得出其中一个为零元)

$a\otimes b \neq (a’\otimes b)\oplus(a\otimes b’)\ominus(a’\otimes b’)$, emmm感觉还是有点模糊

而上面不等于和小于是等价的!(因为不等式是对称的, 同时不等于就是大于或小于)

$a \otimes b \neq a’\otimes b, b\neq 0, \forall a’ < a $

$a \otimes b \neq a\otimes b’, a\neq 0, \forall b’ < b $

计算

非负整数$k$满足$2^{2^k} > a$, 则$a\times 2^{2^k} = a\cdot 2^{2^k}$ (TODO proof

$2^{2^k} \times 2^{2^k} = \frac{3}{2} \cdot 2^{2^k} = 3 \cdot 2^{2^k-1}$ (TODO proof

对于 $a,b \in [0,2^{2^k})$

$a=a_0\cdot 2^{2^{k-1}}+a_1= a_0\otimes 2^{2^{k-1}} \oplus a_1,b=b_0\cdot 2^{2^{k-1}}+b_1= b_0\otimes 2^{2^{k-1}} \oplus b_1$其中$a_0,a_1,b_0,b_1\in[0,2^{2^{k-1}})$, 因为加的左侧低$n$位全为0

$a\otimes b=(a_0\otimes 2^{2^{k-1}}\oplus a_1)\otimes (b_0\otimes 2^{2^{k-1}}\oplus b_1)$

$=((a_0\otimes 2^{2^{k-1}})\otimes (b_0\otimes 2^{2^{k-1}}) ) \oplus ( (a_0\otimes 2^{2^{k-1}})\otimes b_1 ) \oplus (a_1\otimes (b_0\otimes 2^{2^{k-1}}) ) \oplus (a_1\otimes b_1 )$

$=((a_0\otimes b_0)\otimes (3 \cdot 2^{2^{k-1}-1})) \oplus (2^{2^{k-1}}\cdot ((a_0\otimes b_1)\oplus (a_1\otimes b_0))\ ) \oplus (a_1\otimes b_1)$

$=((a_0\otimes b_0)\otimes (2^{2^{k-1}-1}\oplus 2^{2^{k-1}})) \oplus (2^{2^{k-1}}\cdot ((a_0\otimes b_1)\oplus (a_1\otimes b_0))\ ) \oplus (a_1\otimes b_1)$

$=((a_0\otimes b_0)\otimes 2^{2^{k-1}-1})\oplus ((a_0\otimes b_0)\otimes 2^{2^{k-1}})) \oplus (2^{2^{k-1}}\cdot ((a_0\otimes b_1)\oplus (a_1\otimes b_0))\ ) \oplus (a_1\otimes b_1)$

$=((a_0\otimes b_0)\otimes 2^{2^{k-1}-1}) \oplus (2^{2^{k-1}}\cdot ((a_0\otimes b_0)\oplus(a_0\otimes b_1)\oplus (a_1\otimes b_0))\ ) \oplus (a_1\otimes b_1)$

也就是$k\to k-1$ 需要算6个nim乘

但实际上中间的 $=(a_0\oplus a_1)\otimes(b_0\oplus b_1) \ominus (a_1\otimes b_1)$

$=((a_0\otimes b_0)\otimes 2^{2^{k-1}-1}) \oplus (2^{2^{k-1}}\cdot ((a_0\oplus a_1)\otimes(b_0\oplus b_1) \ominus (a_1\otimes b_1))\ ) \oplus (a_1\otimes b_1)$

也就是$O(4^k)$, 而注意到$2^{2^k}$增长很快, 所以如果值不大,$k$不会太大

>>> 2**(2**0)
2
>>> 2**(2**1)
4
>>> 2**(2**2)
16
>>> 2**(2**3)
256
>>> 2**(2**4)
65536
>>> 2**(2**5)
4294967296
>>> 2**(2**6)
18446744073709551616

根据这个计算等式这里我们也可以得到性质 $[0,2^{2^k})$ 中的数做nim乘法结果也在$[0,2^{2^k})$中, 因此不需要mod p, 可以 [0,2^{2^6})

Rolling hash

hash(d) 比 d 有更高的熵entropy ???

就是这里想hash比较来代替直接比, 把O(n) 变成O(1)

hash函数

$R(A) = \left(\sum_{i=1}^N A_i x^{N-i} \right) \bmod{p}$, ?为啥要次方要倒过来? 字符串对称一下不就是正着的吗? 是因为这样的话就是前缀和只需要加减与乘法不需要除法, 而如果次方是正着, 要么就是需要除法或者搭配后缀而不是前缀使用

其中$x$是足够大的$[0,p)$中的质数, 运行时等概率

性质1: 预处理后快速计算区间hash, 其实就是前缀和同样的想法

R(A[l..r]) = R(A[0..r])-R(A[0..l-1])*x^l

性质2: 碰撞率

碰撞: 就是序列不等而hash相等

即需要从随机性上满足, 同时需要难以被找到一个碰撞(不然可以hack,或者出题人造数据)

两个长度$N$的hash相等也就是 $\sum_{i=1}^N(A_i-B_i)x^{N-i} \equiv 0 \pmod{p}$

p是质数,$x$的选取等价的有[1..p-1],每个产生的贡献都不同(因为p是质数), 数量很多, 并且如果是runtime随机,难以猜测x,就无法构造反例, 所以如果 N远小于p, 就概率很小了???

应该是均匀了, 所以很小? 任意取A,要得到与A相等都约为 1/p, 而去掉真正相等还是约为1/p?

代码

https://atcoder.jp/contests/abc274/submissions/36126910

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64; // 2^64 要用完
#define rep(i,a,n) for(u64 i=a;i<(u64)n;i++)
u64 read(){u64 r;scanf("%llu",&r);return r;}
const int N_MAX=1e6+10;
const int SP=1<<3;
const int SN=1<<SP;//预计算 cache大小
u64 A[N_MAX];
u64 pw[N_MAX]={1};//pw[i]=basis**i,pw[0]=1
u64 hs[N_MAX];//hw[i]=前i个的在nimber下的hash,不需要mod[0,2^{2^k})中的nimber做加乘结果还在[0,2^{2^k})中
u64 small[SN][SN];//预计算
template<bool is_pre=false> // 预计算
u64 nim_product(u64 a,u64 b,int p=1<<6){ // a < (1<<p), b < (1<<p), p=1<<k
  if(min(a,b)<=1)return a*b;
  if(!is_pre and p<=SP)return small[a][b];
  p>>=1;//2^k/2=2^{k-1}
  u64 a0=(a>>p),a1=a&((1ull<<p)-1); // a=a0*2^{2^{k-1}}+a1;
  u64 b0=(b>>p),b1=b&((1ull<<p)-1); // b=b0*2^{2^{k-1}}+b1;
  u64 a1b1=nim_product<is_pre>(a1,b1,p);
  // = ((a0\otimes b0)\otimes 2^{2^{k-1}-1})
  return nim_product<is_pre>(nim_product<is_pre>(a0,b0,p),1ull<<(p-1),p)^
    // \oplus (2^{2^{k-1}}\cdot ((a0\oplus a1)\otimes(b0\oplus b1)\ominus (a1\oplus b1))\ )
    ((nim_product<is_pre>(a0^a1,b0^b1,p)^a1b1)<<p)^
    // \oplus (a1\otimes b1)
    a1b1;
}
u64 get(int l,int r){return nim_product(hs[l],pw[r-l])^hs[r];} // hs[r]-hs[l]*(basis**(r-l))
int main(){
  int N=read();
  int Q=read();
  rep(i,0,N)A[i]=read();
  rep(i,0,SN)rep(j,0,SN)small[i][j]=nim_product<true>(i,j,SP);
  mt19937_64 rng(time(NULL));//runtime random
  u64 basis=rng();
  rep(i,1,N+1){
    pw[i]=nim_product(pw[i-1],basis);//pw[i]=pw[i-1]*b
    hs[i]=nim_product(hs[i-1],basis)^A[i-1];//hs[i]=hs[i-1]*b+a[i-1]
  }

  while(Q--){//(l,r]
    int l0=read()-1;
    int r0=read();
    int l1=read()-1;
    int r1=read();//l1-l0==r1-r0
    int l2=read()-1;
    int r2=read();
    int l=0;
    int r=min(r2-l2,r0-l0)+1;
    while(l+1<r){//二分找不等的点
      int m=(l+r)/2;
      ((get(l0,l0+m)^get(l1,l1+m)^get(l2,l2+m))?r:l)=m;
    }
    printf("%s\n",(l2+l!=r2 and(l0+l==r0 or (A[l0+l]^A[l1+l])<A[l2+l]))?"Yes":"No");
  }
  return 0;
}