题解：P2456 [SDOI2006] 二进制方程

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define f(n) for(int i=1;i<=n;i++)
int var[27],n,f[270010],ans;
string l,r;
string cl(string x)//拉伸等号两侧 
{
	string ls;
	ls.clear();
	f(x.length())
		if(x[i-1]=='1'||x[i-1]=='0')ls+=x[i-1];
		else for(int j=1;j<=var[x[i-1]-'a'];j++)ls+=x[i-1];
	return ls;
}
int fd(int now)//合并并查集 
{
	if(f[now]==now)return now;
	return f[now]=fd(f[now]);
}
void d(int now,int nw)//将每个var转为记录对应变量在f中第一位的位置 
{
	if(now==n+1)
	{
		n=nw-1;//end
		return;
	}
	d(now+1,var[now]+nw);
	var[now]=nw;
}
int v(char c)//统一处理字符到f的转换 
{
	if(c=='1'||c=='0')return c-'0';
	return var[c-'a'];
}
int high[1000001]={0,1},hl=1;//高精度 
int main()
{
	f(270009)f[i]=i;
	ios::sync_with_stdio(0);
	cin>>n;
	f(n)cin>>var[i-1];
	cin>>l>>r;
	l=cl(l);
	r=cl(r);
	d(0,2);
	//下方为 
	int ls=0,rs=0,lf,rf;
	//ls记录当前位是对应变量中的第几位，rs同理但是记录等号右侧 
	f(l.length())
	{
		if(i>1)
		{
			if(l[i-1]==l[i-2])ls++;
			else ls=0;
			if(r[i-1]==r[i-2])rs++;
			else rs=0;
		}
		lf=fd(v(l[i-1])+ls);
		rf=fd(v(r[i-1])+rs);
		//lf，rf为两方所在并查集根节点 
		if(lf+rf==1)//以防万一存在无解情况 
		{
			cout<<0;
			return 0;
		}
		if(lf<rf)f[rf]=f[lf];
		else f[lf]=f[rf];
	}
	//计算独立位的数量 
	f(n-1)if(f[i+1]==i+1)ans++;
	//高精度 
	int jc;
	f(ans)
	{
		jc=0;
		for(int j=1;j<=hl;j++)
    	{
			high[j]=high[j]*2+jc;
			jc=high[j]/10;
			high[j]%=10;
		}
		if(jc!=0)high[++hl]=jc;
	}
	f(hl)cout<<high[hl-i+1];
	return 0;
}