CF981E Addition on Segments

\(\text{Solution}\)

一道有思维的\(hash\)题，考虑先确定了\(r0\)的长度，那么\(r1\)的长度也就确定了，这样我们可以用\(O(|T|)\)来确定每个\(0\)和\(1\)对应的字符串，可以用字符串\(hash\)来\(O(1)\)判断。乍一看这样时间复杂度是\(O(|S||T|)\)，但\(r0\)和\(r1\)中必有一个的长度是小于\(\frac{|S|}{|T|}\)，枚举它，时间复杂度为\(O(|S|)\)。

\(\text{Code}\)

#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int N = 1e6 + 5, P1 = 1e9 + 7, P2 = 1e9 + 9;
char s[N], t[N]; int S, T;

struct nd{LL x, y;}h[N], pw[N];
nd gets(int l, int r) {
	return nd{(h[r].x - h[l - 1].x + P1) % P1 * pw[l - 1].x % P1, (h[r].y - h[l - 1].y + P2) % P2 * pw[l - 1].y % P2};
}
nd work(int fl, int l0, int l1) {
	for (int j = 1, pos = 0; j <= T; j++) {
		if ((t[j] - '0') == fl) return gets(pos + 1, pos + (fl ? l1 : l0));
		pos += (t[j] == '0' ? l0 : l1);
	}
}
int main()
{
	scanf("%s",t + 1), T = strlen(t + 1);
	scanf("%s",s + 1), S = strlen(s + 1), pw[0] = nd{1, 1};
	for (int i = 1; i <= S; i++) h[i].x = (h[i - 1].x * 29LL % P1 + (LL)(s[i] - 'a' + 1)) % P1, pw[i].x = pw[i - 1].x * 29LL % P1;
	for (int i = 1; i <= S; i++) h[i].y = (h[i - 1].y * 31LL % P2 + (LL)(s[i] - 'a' + 1)) % P2, pw[i].y = pw[i - 1].y * 31LL % P2;
	int c0 = 0, c1 = 0;
	for (int i = 1; i <= T; i++) 
		if (t[i] == '0') c0++; else c1++;
	if (c0 < c1) {
		swap(c0, c1);
		for (int i = 1; i <= T; i++)
			if (t[i] == '0') t[i] = '1'; else t[i] = '0';
	}
	int ans = 0;
	for (int i = 1; i * c0 < S; i++) {
		int l0 = i, l1 = (S - c0 * i) / c1, flag = 1;
		if ((S - c0 * l0) % c1) continue;
		nd z0 = work(0, l0, l1), z1 = work(1, l0, l1), res;
		if (l0 == l1 && z0.x == z1.x && z0.y == z1.y) continue;
		for (int j = 1, pos = 0; j <= T; j++) {
			if (t[j] == '0') res = gets(pos + 1, pos + l0), pos += l0;
			else res = gets(pos + 1, pos + l1), pos += l1;
			nd u = (t[j] == '0' ? z0 : z1);
			if (res.x != u.x || res.y != u.y) {flag = 0; break;}
		}
		ans += flag;
	}
	printf("%d\n",ans);
}