2023第七场牛客多校-We Love Strings

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;
}