洛谷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
#include
#include 
#include

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228