I-We Love Strings_2023牛客暑期多校训练营7
题意
做法：根号分治+容斥原理
将字符串分为两类：
- len<=20直接位运算枚举出可能的所有答案，看是否存在符合的
- len>20采用容斥原理，计算出所有长度为 i 的字符串中（假设为n个），1个字符串可以表示的 ( 1个元素的交集 ) ，2个字符串可以表示的（ 2个元素的交集 ），.......，n个字符串可以表示的（ n个元素的交集 ）
- 贡献就是 这 n 个长度为 i 的字符串的并集， 根据容斥原理选了奇数个字符串的应该加上，偶数个应该减去
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;
const int N=405;
const int mod=998244353;
void add(int &a,int b){
a+=b;
if(a>=mod)a-=mod;
}
void del(int &a,int b){
a-=b;
if(a<0)a+=mod;
}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
int n;cin>>n;
map<int,vector<string>>mp;
for(int i=1;i<=n;i++){
string s;cin>>s;
mp[(int)s.size()].push_back(s);
}
int ans=0;
for(auto [len,s]:mp){
int sz=(int)s.size();
if(len<=20){
for(int i=0;i<(1<<len);i++){
for(int j=0;j<sz;j++){
bool ok=true;
for(int k=0;k<len;k++){
if(s[j][k]=='?')continue;
if(s[j][k]-'0'!=(i>>k&1)){
ok=false;
break;
}
}
if(ok){
add(ans,1);
break;
}
}
}
}else{
for(int i=1;i<(1<<sz);i++){
int cnt=1;
for(int j=0;j<len;j++){
bool ok1=false,ok0=false;
for(int k=0;k<sz;k++){
if((i>>k)&1){
if(s[k][j]=='0')ok0=true;
if(s[k][j]=='1')ok1=true;
}
}
if(ok0&&ok1){
cnt=0;
break;
}
//当当前位上全是"？"，答案就乘2，意思是当前为可以全部取0或者全部取1
if(!ok0&&!ok1)add(cnt,cnt);
}
if(__builtin_popcount(i)&1)add(ans,cnt);
else del(ans,cnt);
}
}
}
cout<<ans<<endl;
return 0;
}