题解 | #牛牛去买球#

I We Love Strings

链接：https://ac.nowcoder.com/acm/contest/57361/I

solve

分治：

首先，观察范围，可以按照将字符串分成两类：

1. 小于等于20 ， 暴力枚举符合条件的字符串进行统计。
2. 大于20 ， 这种字符串最多有20个，用容斥技巧处理：

2. 解决细节

直接枚举字符串的选择情况：

枚举出选择情况之后，很容易就能计算出它们能够共同表达的字符串集合：

1. 一个位置上可以匹配： 贡献一：
2. 一个位置上全为'?' ： 当前匹配的前缀总数乘上2：
3. 一个位置上不同 ： 匹配串为0

容斥原理

1. 只选择一个： +
2. 选择两个， 得到的必然是1步骤中贡献的交集； -
3. 选择三个， 得到的结果，对应2步骤中结果的交集： +

... 奇数则贡献， 偶数则减去：

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

#define int ll
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

const int inf = 1E9 + 7;;
const ll INF = 1E18 + 7;
const int N = 1E6 + 10;
const int mod = 998244353;

void add(int& a , int b) {
	a += b;
	if (a >= mod) a -= mod;
}
void dec(int&a , int b) {
	a -= b;
	if (a < 0) a += mod;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	map<int , vector<string>> mp;
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		mp[sz(s)].push_back(s);
	}
	int ans = 0;
	for (auto &[len , s] : mp) {
		int n = sz(s);
		if (len <= 20) {
			for (int msk = 0; msk < (1 << len); msk++) {
				for (int i = 0; i < n; i++) {
					bool flag = true;
					for (int j = 0; j < len; j++) {
						if (s[i][j] != '?' && (s[i][j] - '0') != (msk >> j & 1)) {
							flag = false;
							break;
						}
					}
					if (flag) {
						ans++;
						break;
					}
				}
			}
		} else {
			for (int msk = 1; msk < (1 << n); msk++) {
				int cnt = 1;
				for (int j = 0; j < len; j++) {
					bool f1 = false , f0 = false;
					for (int i = 0; i < n; i++) {
						if (msk >> i & 1) {
							if (s[i][j] == '0') f0 = true;
							if (s[i][j] == '1') f1 = true;
						}
					}
					if (f0 && f1) {
						cnt = 0;
						break;
					}
					if (not f0 && not f1) {
						cnt = cnt * 2 % mod;
					}
				}
				if (__builtin_popcount(msk) % 2) {
					ans = (ans + cnt) % mod;
				} else {
					ans = ((ans - cnt) % mod + mod) % mod;
				}
			}
		}
	}
	cout << ans << "\n";
}