洛谷P2456 二进制方程

传送门
题目描述
一个形如：

X1X2…Xn=Y1Y2…Ym

的等式称为二进制方程。

在二进制方程的两边：Xi和Yj （1<=i<=n；1<=j<=m）是二进制数字（0、1）或者一个变量（小写字母）。每个变量都是一个有固定长度的二进制代码，他可以在等式中取代变量的位置，称这个长度为变量的长度。为了解一个二进制方程，需要给其中的变量赋予适当的二进制代码，使得我们用他们替代等式中的相应的变量后（等式的两边都变成二进制代码），这个等式成立。

编程任务：

对于每一个给出的方程，计算一共有多少组解。已知变量最多有26个（26个英文小写字母），且等式的每一端的数字和变量的长度之和不超过10000。

输入格式
第一行：k（k<=26,变量的个数，规定使用小写英文字母中的前k个字母作为变量，如k=5，则变量a,b,c,d,e）。

第二行：k个正整数，中间用一个空格隔开，依次代表k个变量的长度。

第三行：等式左边的表达式。

第四行：等式右边的表达式。

输出格式
等式中出现的变量共有多少组解。

输入输出样例
输入 #1复制
2
4 2
1b1
a
输出 #1复制
4
输入 #2复制
5
4 2 4 4 2
1bad1
acbe
输出 #2复制
16
说明/提示
样例一：4组解

1 、a=1001； b=00

2、 a=1011； b=01

3、 a=1101； b=10

4、 a=1111； b=11）

样例二：K=5，变量：a,b,c,d,e。长度分别为：4 2 4 4 2。等式是：1bad1= acbe

输出16，即变量a,b,c,d,e共有16组解。

上代码：

#include<iostream>
#include<cstdio>
#include<cstring> 
#include<queue>

using namespace std;

int n,lm[30];//每个字母长度
int tolen;//真正表达式长度 
int maxnode,quan[20008];
long long toans;//贡献答案用的连通块的个数/快速幂的指数 

char s[2][10008];

struct equation{
    //存表达式 
	bool isnum;
	int mu,wei;
}equ[3][10008];

inline int init(int k)//字符串转表达式 
{
    
	int l=strlen(s[k]),step=1,m,w,r;
	for(int i=0;i<l;++i)
	{
    
		if(s[k][i]=='0'||s[k][i]=='1')
		{
    
			equ[k][step].isnum=1;
			equ[k][step++].mu=s[k][i]=='1';
		}
		else
		{
    
			m=s[k][i]-'a'+1;
			r=step+lm[m]-1,w=1;
			for(;step<=r;step++)
			{
    
				equ[k][step].mu=m;
				equ[k][step].wei=w++;
			}
		}
	}
	return step-1;
}

#define xb(k) equ[k][step].mu][equ[k][step].wei

int	fina[30][10008],lst[20008],nxt[100000],cnt,to[100000];

inline void addedge(int u,int v)
{
    
	nxt[++cnt]=lst[u];
	lst[u]=cnt;
	to[cnt]=v;
}

void ADDEDGE()
{
    
	int len=1;
	int *p;
	for(int step=1;step<=tolen;step++,len++)
	{
    
		addedge(len,len+tolen);
		addedge(len+tolen,len);
		if(!equ[1][step].isnum)
		{
    
			p=&fina[xb(1)];
			if(*p==0)
				*p=len;
			else
			{
    
				addedge(*p,len);
				addedge(len,*p);
				*p=len;
			}
		}
		else
			quan[len]=equ[1][step].mu;
		
	}
	for(int step=1;step<=tolen;step++,len++)
	{
    
		if(!equ[2][step].isnum)
		{
    
			p=&fina[xb(2)];
			if(*p==0)
				*p=len;
			else
			{
    
				addedge(*p,len);
				addedge(len,*p);
				*p=len;
			}
		}
		else
			quan[len]=equ[2][step].mu;
	}
	maxnode=len-1;
}

bool vis[20008];

queue<int>q;

inline int bfs(int sta,int key)
{
    
	vis[sta]=1;
	q.push(sta);
	int head,t;
	while(!q.empty())
	{
    
		head=q.front();
		q.pop();
		for(int e=lst[head];e;e=nxt[e])
		{
    
			t=to[e];
			if(!vis[t])
			{
    
				if(quan[t]!=-1&&(quan[t]!=key))
					return 1;
				quan[t]=key;
				vis[t]=1;
				q.push(t);
			}
		}
	}
	return 0;
}

const int P=10000;

struct gaojing{
    
	long long num[2600];
	int len;
	void qingling()
	{
    
		memset(num,0,sizeof num);
		len=0;
	}
}endans,c,with,di;

inline gaojing operator *(const gaojing &a,const gaojing &b)
{
    
	c.qingling();
	int ll;
	for(int i=1;i<=b.len;i++)
		for(int j=1;j<=a.len;j++)
		{
    
			c.num[i+j-1]+=b.num[i]*a.num[j];
		}
	for(ll=1;ll<=b.len+a.len;ll++)
	{
    
		if(c.num[ll]>=P)
		{
    
			c.num[ll+1]+=c.num[ll]/P;
			c.num[ll]%=P;
		}
	}
	while(ll>1&&c.num[ll]==0) --ll;
	c.len=ll;
	return c;
}

gaojing ksm(int mi)//高精快速幂 
{
    
	di.len=1;
	di.num[1]=1;
	with.len=1;
	with.num[1]=2;
	while(mi)
	{
    
		if(mi&1) di=di*with;
		with=with*with;
		mi>>=1;
	}
	return di;
}

void print(const gaojing &a)
{
    
	printf("%d",a.num[a.len]);
	int x;
	for(int i=a.len-1;i>=1;--i)
	{
    
		x=a.num[i];
		if(x<1000) putchar('0');//注意中间的0不能省略 
		if(x<100) putchar('0');
		if(x<10) putchar('0');
		printf("%d",x);
	}
}

int main()
{
    
	cin>>n;
	for(int i=1;i<=n;i++) cin>>lm[i];
	cin>>s[1]>>s[2];
	if(n<=0)
	{
    
		cout<<0;
		return 0;
	}
	tolen=init(1);
	if(tolen!=init(2))
	{
    
		cout<<0;
		return 0;
	}
	memset(quan,-1,sizeof quan);
	ADDEDGE();
	for(int i=1;i<=maxnode;i++)
		if(!vis[i]&&(quan[i]==1||quan[i]==0))
		{
    
			if(bfs(i,quan[i]))
			{
    
				cout<<0;
				return 0;
			}
		}
	int mi=0;
	for(int i=1;i<=maxnode;i++)
		if(!vis[i])
		{
    
			mi++;
			bfs(i,-1);
		}
	endans=ksm(mi);
	print(endans);
	return 0;
}