2021.11.15模拟赛部分题解

2021.11.15模拟赛部分题解 字典树

solution：

正面硬搞发现是不太可能的，所以我们利用trie树的性质，节点数=不同的前缀数量。所以我们想到用容斥来处理多个串之间的前缀所做的贡献。
处理?时，对于几个串同一位都是?时，那么会对后面的位提供2的贡献，并且未讨论到的？每一个也会对当前做出2的贡献。

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include
#define ll long long
using namespace std;
const int N = 1e5+10;
const ll mo = 1e9+7;
int n,m,sum;
ll ans,p[1005];
char a[25][55];
void init(){p[0]=1;for(int i=1;i<=1e3;i++)p[i]=2ll*p[i-1]%mo;}
signed main(){
//	freopen("ex_trie3.in","r",stdin);
	init();scanf("%d",&n);
	for(int i=0;i>j)&1)num[++cnt]=j;
		for(int l=0;;l++){
			int tmp=-1,flag=1;
			for(int j=1;j<=cnt;j++){
				if(tmp==-1&&a[num[j]][l]!='?')tmp=a[num[j]][l]-'0';
				if(!a[num[j]][l]||(a[num[j]][l]!='?'&&a[num[j]][l]-'0'!=tmp)){flag=0;break;}
				if(a[num[j]][l]=='?')ct++;
			}if(!flag)break;
			if(tmp==-1)pre++;
			res+=p[pre+sum-ct];if(res>mo)res%=mo;
		}if(cnt&1)ans+=res;
		else ans-=res;ans%=mo;
	}
	printf("%lldn",((ans+p[sum])%mo+mo)%mo);
	return 0;
}