CF1746D
CF1746F
随机化,随机赋权值,每次判断区间和是否满足。
只会把 NO 判成 YES。
当 k = 2,概率还是蛮高的,\(1/2\) 吧。
CF1750
C,考虑 \(a[i] ^ b[i]\) 必须相等。
那么两个串要么互补,要么相同。
只要考虑 \(00100\),\(00100\) 情况,这时取 \([1,i], [1,i-1]\) 就行。
D, 考虑球 \(\gcd(b[i], a[i-1]) = a[i]\) 的方案数。
那么即 \(\gcd(b[i] / a[i] = k, a[i-1] / a[i]) = 1\) 的方案数。
那么求的是 \(\sum_{i=1}^{m / a[i]} [\gcd(i, a[i-1] / a[i]) = 1]\)
简单莫反,得到 \(\sum_{p|(m/a[i])}\mu(p)(a[i-1]/a[i])/p\)
考虑无平方因子,只有 \(2^{\omega(m/a[i])}\) 种,最大是 \(2^9\)。
E, 直接考虑每个区间的答案是啥。
他说是 \(\max(s[r], s[l-1]) - \min(s[l], .. ,s[r])\)
标签:gcd,记录,要么,sum,随机化,考虑,00100 From: https://www.cnblogs.com/Lates/p/16865382.html