大佬教程收集整理的这篇文章主要介绍了【题解】牛客练习赛41-D 最小相似度，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
题目链接
(text{Solution:})
首先考虑我们到底要求啥，实际就是要快速求出对于一个数 (x,) 所有数与它异或后的 SIM 值。
一种 naive 的想法是直接枚举 (T,) 显然复杂度爆炸，因为 (n) 太大了，是 (O(2^mtimes n)) 的。
考虑把 (n) 干掉，倒着想。题目的描述引导我们去二分答案。
设当前答案是 (mid,) 目标就是看是否存在一个 (x) 满足最大 SIM 不超过 (x.)
考虑设 (f_x) 表示 (x) 在二进制下 (0) 的个数，寻找一个逆向的突破口：
不能直接枚举 (x,) 考虑什么情况下我们可以知道存在这样一个 (x.)
那么发现，每个数 (v_i) 在经过变换后的值就是 (v_itext{ xor } x,) 那不妨从这个最终状态出发。
考虑预处理出所有二进制下 (0) 的个数等于 (i) 的数，那么设 (g_x) 表示 (x) 这个数是否有贡献，那么把 (cntleq mid) 的贡献都算上，现在我们就有了两个多项式：
那么设 (c,c_x=sum_{itext{ xor }j=x}f_itimes g_j)
那么存在一个 (x) ，就意味着 (c_x=n,) 因为这就等价于它对每个数都有贡献。
从上述做法就可以二分答案了。复杂度 (O(m2^mtimes log m))
以上是大佬教程为你收集整理的【题解】牛客练习赛41-D 最小相似度全部内容，希望文章能够帮你解决【题解】牛客练习赛41-D 最小相似度所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。