题目大意

题解

这题给定的 n n n 大小和 s i s_i si​ 的总长度有玄机。
我们发现： 400 = 2 0 2 400=20^2 400=202，对于每一组数据 n n n 的个数每增加一个， s i s_i si​ 的平均值就会减小。
处理相同的 l l l 个 s i s_i si​
①：对于 s i ≤ 20 s_i\leq20 si​≤20 ，完全可以暴力，枚举所有的边，复杂度为 l ∗ 2 s i l*2^{s_i} l∗2si​
在 20 20 20 的范围内 最多有 20 ∗ （ s i z = 20 ) 20*（siz=20) 20∗（siz=20) 条边 ， 2 20 ∗ 20 2^{20}*20 220∗20 千万级别的计算。
②：对于 s i > 20 s_i>20 si​>20， n < 20 n<20 n<20，考虑答案的唯一性，
如果两条边相同，则他们的贡献只有 1 1 1 ，容易得出如果某一位发生 0 0 0 和 1 1 1 冲突了，
他们就不是同一条边 ，如果某一位全是“ ? ? ? ”则答案的贡献 ∗ 2 *2 ∗2 。
单独对于一条边，它的贡献就是 2 s u m i 2^{sum_i} 2sumi​ （sum为当前的问号个数）
由此我们发现了每两条边的匹配关系。总答案需要将他们去除。
即 a n s = a n s 1 − a n s 2 ans=ans_1-ans_2 ans=ans1​−ans2​ 。
显然的，这并不是最终答案，有一些边的贡献减了许多次。
这时候我们知道需要用容斥来计算结果了。
所以最终答案为 a n s = a n s 1 − a n s 2 + a n s 3 − . . . . . . ans=ans_1-ans_2+ans_3-...... ans=ans1​−ans2​+ans3​−......
它的复杂度为枚举每一条边是否存在 s i ∗ 2 l s_i*2^l si​∗2l。
观察复杂度得到：
对于不同大小的 s i s_i si​，我们进行分类讨论，用合适的算法计算。

参考代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int mod=998244353;
int n;
string s[405];
char c[500],s1[500];
map<string,int> mp;
ll ans;
int cmp(string a,string b)
{
    return a.size()<b.size();
}
void dfs(int id,int x,int len,char c[500])
{
    if(x==len)                  //枚举
    {
        if(!mp[c])
            mp[c]=1,ans++;
    }
    ll a=0;
    if(s[id][x]=='?')
    {
        c[x]='1';
        dfs(id,x+1,len,c);
        c[x]='0';
        dfs(id,x+1,len,c);
    }
    if(s[id][x]=='1')
    {
        c[x]='1';
        dfs(id,x+1,len,c);
    }
    if(s[id][x]=='0')
    {
        c[x]='0';
        dfs(id,x+1,len,c);
    }
}
void work(char s1[500],int siz)           //重复的个数
{
    ll sum=1;
    int sum1=0;
    for(int i=0;i<siz;i++)
    {
        int tot=2;
        for(int j=1;j<=n;j++)
        {
            if(s1[j]=='1')
            {
                if(i==0)
                    sum1++;
            }
            else
                continue;
            int a=s[j][i]=='?'?2:s[j][i]-'0';
            if(tot==2)
                tot=a;
            else
            {
            	if(a==2)
            		tot=tot;
            	else if(tot==1 && a==0)
            		sum=0;
            	else if(tot==0 && a==1)
            		sum=0;
            	else
            		tot=a;
			}
        }
        if(tot==2){
        	sum=sum*2%mod;
		}
    }
    if(sum1==0)
        return;
//    cout<<s1<<" "<<sum<<endl;
    if(sum1&1)                 //容斥
        ans+=sum;
    else
        ans-=sum;
    ans%=mod;
    ans=(ans+mod)%mod;
}
void dfs1(int x,int len,char s1[500],int siz)
{
    if(x==len+1)
    {
//    	cout<<s1<<" "<<siz<<endl;
    	work(s1,siz);       //填数字1/0表示是否存在
    	return;
	}
    s1[x]='0';
    dfs1(x+1,len,s1,siz);
    s1[x]='1';
    dfs1(x+1,len,s1,siz);
    s1[x]='0';
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    sort(s+1,s+n+1,cmp);
    int r=0,l=1;
    for(int i=0;i<=3;i++)
        s1[i]='0';
    for(int i=1;i<=400;i++)
    {
        while(r+1<=n && s[r+1].size()==i)     //找出长度
            r++;
        if(l>r)
        	continue;
//        cout<<l<<" "<<r<<endl;
 		if(i<=20)                 //分块
             for(int j=l;j<=r;j++)
 	           dfs(j,0,i,c);
 	    else
	        dfs1(l,r,s1,i);
        l=r+1;	 
    }
    printf("%lld\n",ans%mod);
    
}