题解 | #和与或#

和与或

和与或 (nowcoder.com)

solve

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

1. 当前位置为1时 ， 那么就要有一个A提供1。其它地位置提供0。

2. 这样一直枚举下去。由乘法计数原理，所有情况都考虑齐全。 在此过程中 ， 观察是否有一些可以重复利用地信息。在枚举地过程中，对于一$a_{i}a\_i$有两种属性——是否被限制（是否贴着上界走。）这样意味着这些数字是是否0 ， 1随便取。 那么这时可以感受到， 后面地选择和当前地0 ， 1相关。（形象地看，就是子树是相同的。这样我们可以记录这些解。）

3. 状态设计 $d{p}_{i,j}dp\_\{i\; ,\; j\; \}$ 表示当前在枚举第i位情况下 ，j 表示限制情况（状态压缩的方法，如果某i位上为0表示被限制。反之）初

4. 始化： 初始化为-1。并且从开始$dfs(62,0)dfs(62\; ,\; 0)$开始搜索。

5. 状态转移 如果sum当前的位置上选择0.通通选0. 如果sum当前位置上选择1. 下面两种情况

   1. 非限制数字选择1.
      1. 此时原本被限制的 且 上界的当前位上为1的 数字不再被限制。
   2. 限制位数字且上界该位置上本来就有1。
      1. 同上 。

生长思考

1. 那么神奇，怎么思考？
2. 体会到了数位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
*/