)
不是题解不是教学！！！！！
9.24
洛谷 P4310
题目给定一个长度为 n 的数组，选取一个子序列，使子序列相邻的数之间的 AND 不为 0， 问子序列最长为多少。
很容易想到对于第 i 个数，可以找到之前子序列长度最大的一个和自己 AND 不为零的数，并把 i 的每个为 1 的位都更新为这个长度 + 1，dp 即可。第一次写的时候没有把所有的 1 都更新，挂了两发，检查后很快通过。
洛谷 P7970
题目给出一个矩阵左上角和右下角，给这个矩阵中 i AND j 不为 0 的格子涂黑，问矩阵内有多少个联通块。思考了半个小时，打了表看到一些规律，但基本没什么思路，然后看了题解。题解主要给出了一个关键信息：对于一个黑格 (x, y)，两个格子 (x, y - 1) 和 (x - 1, y) 有且只有一个涂黑，y 不变同理。
证明如下：设 x 小于 y 且 x AND y 为 0，故 y - 1 = y - (lowbit(y) - 1) + lowbit(y)，也就是把 y 的最后一位 1 后面的全部变为 1，那么 y - 1 一定有 lowbit(x) 位为 1。而 x - 1 = x - lowbit(x) + (lowbit(x) - 1)，显然 lowbit(y) 位不受影响仍为 0。
同时观察打表结果，可以注意到联通块的个数是矩形上边和左边与打表结果相切的个数。那么就可以用数位 dp 去求，当一个数所有与 x OR (x - 1) 的 AND 为 0 时，也就是这个数与 x 和 x - 1 的 AND 都为 0，那么这是一个和上边相交的点，横向同理。
注意这道题目需要特判 0 的情况，以及数位 dp 时去判断这一位是否取 AND 为 0 时要注意 1 改为 long long，以及判断不是等于 1 而是非零。