【位运算】解题报告：luoguP4310绝世好题（位运算优化DP）

题目链接&＃xff1a;luoguP4310 绝世好题

这是链接

因为答案只能是由两个在二进制表示下至少有一位同是1的a序列里的数&得到的,最后求子序列的个数
f[i]存的是对于a序列中当前遍历到的数中有几个在二进制表示下第i位为1&＃xff0c;因为求的是子序列的个数而非方案&＃xff0c;所以发现当前的数可以与之前的数&之后得到1满足题目要求&＃xff0c;答案就只&＃43;1

#include
#include
#include
#include
#include
#include
//#define ls (p<<1)
//#define rs (p<<1|1)
#define over(i,s,t) for(register int i &＃61; s;i <&＃61; t;&＃43;&＃43;i)
#define lver(i,t,s) for(register int i &＃61; t;i >&＃61; s;--i)
//#define int __int128
//#define lowbit(p) p&(-p)
using namespace std;typedef long long ll;
typedef pair<int,int> PII;
const ll INF &＃61; 1e18;
const int N &＃61; 5e5&＃43;7;
const int M &＃61; 5e4&＃43;7;
//因为答案只能是由两个在二进制表示下至少有一位同是1的a序列里的数&得到的,最后求子序列的个数
//f[i]存的是对于a序列中当前遍历到的数中有几个在二进制表示下第i位为1&＃xff0c;因为求的是子序列的个数而非方案&＃xff0c;所以发现当前的数可以与之前的数&之后得到1满足题目要求&＃xff0c;答案就只&＃43;1int a[N];
int n,m,ans;
int f[N];
int main(){cin>>n;over(i,1,n)scanf("%d",&a[i]);over(i,1,n){int maxn &＃61; -1;over(j,1,32)//ai <1e9 ≈ 2^32if(a[i] & (1<<j))maxn &＃61; max(maxn,f[j] &＃43; 1);//寻找最大答案over(k,1,32)if(a[i] & (1<<k))f[k] &＃61; maxn;//更新当前f数组ans &＃61; max(maxn,ans);//更新当前答案}printf("%d\n",ans);return 0;
}