本蒟蒻比赛时想到了gcd约分求最简相似序列，但是只有50分(后来拿了性质A的20分)，看了题解，不明白大佬们的思路与本蒟蒻的不同(或者说怎么优化)

附上比赛的巨长代码：

#include <bits/stdc++.h>
#define N 5000005
using namespace std;

//char *p1, *p2, buf[1 << 14];
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, (1 << 14), stdin), p1 == p2) ? EOF : *p1++)
template <typename T>
inline void read(T& x) {
    x = 0;
    register int t = 1;
    register char ch = getchar(); 
    while (ch < '0' || ch > '9') {
        t |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9'){
        x = (x << 1) + (x << 3) + (ch ^ 48);  
        ch = getchar();
    }
    x *= t;
}

int n, m;
int nxt[N];
vector<int> a, b;
// 思路：处理所有与b相似的序列，用KMP分别统计每一个并且累加 

inline void get_next(vector<int>& s) {
	memset(nxt, 0, sizeof(nxt));
	// KMP的前缀表nxt
	nxt[0] = -1;
	register int j = -1;
	for (register int i = 1; i < n; i++) {
		while (j >= 0 && s[i] != s[j + 1]) j = nxt[j];
		if (s[i] == s[j + 1]) j++;
		nxt[i] = j;
	}
}

int kmp(vector<int>& source, vector<int>& target) {
	get_next(target);
	register int j = -1, cnt = 0;
	for (register int i = 0; i < n; i++) {
		while (j >= 0 && source[i] != target[j + 1]) j = nxt[j];
		if (source[i] == target[j + 1]) j++;
		if (j == target.size() - 1) cnt++;  // 匹配成功 
	}
	return cnt;
}

vector<pair<int, int>> bcntres;
void cntb() {
	// 给b作统计 
	register int i = 0;
	while (i < b.size()) {
		register int curcnt = 1, curitem = b[i];
		i++;
		while (i < b.size() && b[i] == curitem) i++, curcnt++;
		bcntres.push_back(make_pair(curitem, curcnt));
	}
}

void yuefen() {
	// 对bcntres约分
	register int ngcd = 0;
	for (register int i = 0; i < bcntres.size(); i++) {
		int n = bcntres[i].second;
		if (ngcd == 0) ngcd = n;
		else ngcd = __gcd(n, ngcd);
	} 
	for (register int i = 0; i < bcntres.size(); i++) {
		bcntres[i].second /= ngcd;
	} 
}

inline vector<int> generate() {
	// 根据bcntres生成目标相似数组
	vector<int> res;
	res.reserve(n);
	for (register int i = 0; i < bcntres.size(); i++) {
		for (register int j = 0; j < bcntres[i].second; j++) res.push_back(bcntres[i].first);
	} 
	return res;
}
/*
inline showv(vector<int>& arr) {
	for (register int i = 0; i < arr.size(); i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
}
*/

void xingzhiA() {
	// 拿带性质A的20分，过34 
	register int i = 0;
	register long long ans = 0;
	// 对a作分块 
	while (i < a.size()) {
		if (a[i] == b[0]) {
			register long long cnt = 0;
			while (i < a.size() && a[i] == b[0]) {
				i++;
				cnt++;
			}
			// 对于一个块区，cnt+(cnt-1)+...+2+1即为所求 
			ans += (cnt + 1) * cnt / 2; //可能爆int 
		}
		i++;
	}
	printf("%lld", ans);
}

void xingzhiB() {
	// 拿带性质B的20分，但没拿上 
	register int c1 = bcntres[0].first, c2 = bcntres[1].first;
	register int d1 = bcntres[0].second, d2 = bcntres[1].second;
	//cout << c1 << " " << c2 << endl;
	register int i = 0;
	register int ans = 0;
	while (i < a.size()) {
		if (a[i] == c1) {
			register int cnt1 = 0, cnt2 = 0;
			while (i < a.size() && a[i] == c1) {
				i++;
				cnt1++;
			}
			while (i < a.size() && a[i] == c2) {
				i++;
				cnt2++;
				//cout << cnt1 << ", " << cnt2 << endl;
				if (cnt1 / cnt2 == d1 / d2) ans++;
			}
			i--;  // 抵消 
		}
		i++;
	}
	printf("%d", ans);
}
 
int main() {
	read(n); read(m);
	a.reserve(n); b.reserve(m);
	for (register int i = 0; i < n; i++) {int k; read(k); a.push_back(k);}
	for (register int i = 0; i < m; i++) {int k; read(k); b.push_back(k);}
	
	// 先约分，然后扩倍通分 
	// 时间复杂度O(n^2/m) 
	// 能拿50分，过12789
	cntb();
	
	if (bcntres.size() == 1) {
		xingzhiA();
		return 0;
	}
	if (bcntres.size() == 2) {
		xingzhiB();
		return 0;
	}
	
	yuefen();
 	
//	for (register int i = 0; i < bcntres.size(); i++) {
//		cout << bcntres[i].first << ", " << bcntres[i].second << " ";
//	} 

	register int res = 0;
	for (register int k = 1; k <= n; k++) {
		for (register int i = 0; i < bcntres.size(); i++) {
			// 抵消上一次影响 
			if (k != 1) bcntres[i].second = bcntres[i].second / (k - 1) * k;
			else bcntres[i].second = bcntres[i].second * k;
		} 
		vector<int> target = generate();
		//showv(target);
		if (target.size() > a.size()) break;
		res += kmp(a, target);
	}
	printf("%d", res);
	return 0;
}