题解 | #和与或#

和与或

solve

我们不断地枚举最终和地数字地前缀：对于任意二进制串前缀：

当前位置为1时，那么就要有一个A提供1。其它地位置提供0。
这样一直枚举下去。由乘法计数原理，所有情况都考虑齐全。在此过程中，观察是否有一些可以重复利用地信息。在枚举地过程中，对于一 $a_{i}$ 有两种属性——是否被限制（是否贴着上界走。）这样意味着这些数字是是否0 ， 1随便取。那么这时可以感受到，后面地选择和当前地0 ， 1相关。（形象地看，就是子树是相同的。这样我们可以记录这些解。）
状态设计 $dp_{i , j }$ 表示当前在枚举第i位情况下，j 表示限制情况（状态压缩的方法，如果某i位上为0表示被限制。反之）初
始化：初始化为-1。并且从开始 $d f s (62, 0)$ 开始搜索。
状态转移如果sum当前的位置上选择0.通通选0. 如果sum当前位置上选择1. 下面两种情况
1. 非限制数字选择1.
  1. 此时原本被限制的且上界的当前位上为1的数字不再被限制。
2. 限制位数字且上界该位置上本来就有1。
  1. 同上。

生长思考

~~那么神奇，怎么思考？~~
体会到了数位dp中贴上界问题一直存在。在特殊的统计问题中也是一个难点。

code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1E6 + 10;
const int mod = 1E9 + 9;

ll a[N] , dp[100][1050];
int n;

ll dfs(int pos , int limit) {
	if (pos == -1)return 1;
	if (dp[pos][limit] != -1) return dp[pos][limit];

	ll& res = dp[pos][limit];
	res = 0;
	//记录拿一些a在当前的pos上为1
	int rec = 0;
	for (int i = 0; i < n; i++)
		if (a[i] & (1LL << pos)) {
			rec |= 1LL << i;
		}
	res += dfs(pos - 1 , limit | rec);
	//考虑的当前pos上取1的情况。
	//枚举哪一一个1在这个位置上可以做出贡献
	for (int i = 0; i < n; i ++)
		if (limit & (1LL << i))
			res = (res + dfs(pos - 1 , limit | rec)) % mod;
		else if (rec & (1LL << i))
			res = (res + dfs(pos - 1 , (limit | rec) ^ (1LL << i))) % mod;
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	memset(dp , -1 , sizeof dp);
	cout << dfs(61 , 0) << '\n';
}

/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/