生日(数学,暴力折半搜)
题目描述
给定序列a,两种操作:
1:给定l,r,询问是否存在x,y两个【l,r】的子集满足两集合的权值和相等。
2:给定l,r,对\(i\in[l,r]\) , \(a_i\to a_i^3\mod V\).
n,q 1e5,v 1000
解析
注意到 \(v\) 很小。
所以子集权值只有 \(len\times v\) 种 。
但是子集个数很多,有 \(2^{len}\) 个。
根据抽屉原理,当 \(2^{len}>len\times v\) 就一定有解。
解得 \(len>14\) 然后 \(len <=14\) 折半搜。
对于操作二,线段树上打标记,然后\(len <=14\) 暴力递归就可以了。
评价
抽屉原理一般就就是用在这种解比较多的情况吧。
但是我想不到,自闭了。