注意到子串的权值在其中一个端点固定时随着另一个端点向外扩展而单调递增，可以使用双指针统计答案。

将原序列反转，改为匹配子序列 $\{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$，分别维护子序列 $\{\texttt 2\}, \{\texttt 2, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3\}, \{\texttt 2, \texttt 3, \texttt 3, \texttt 3\}$ 的出现次数即可实现双指针移动时对权值的实时计算。

最终的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，其中输入的字符串 $S$ 不计入空间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 12;
inline __int128 read()
{
	__int128 x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
inline std::string readline()
{
	std::string x = "";
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x += c;
		c = getchar_unlocked();
	}
	return x;
}
void write(__int128 x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void writeline(__int128 x)
{
	write(x);
	putchar_unlocked('\n');
}
int main()
{
	freopen("sorrow.in", "r", stdin);
	freopen("sorrow.out", "w", stdout);
	__int128 n = read(), k = read();
	string s = readline();
	reverse(s.begin(), s.end());
	s = ' ' + s;
	__int128 r = 0, ans = n * (n + 1) / 2;
	__int128 c3 = 0, c2 = 0, c23 = 0, c233 = 0, c2333 = 0;
	for (int i = 1; i <= n; i++)
	{
		while (c2333 < k && r <= n)
		{
			r++;
			if (s[r] == '2') c2++;
			if (s[r] == '3')
			{
				c3++;
				c2333 += c233;
				c233 += c23;
				c23 += c2;
			}
		}
		ans -= (r - i);
		if (s[i] == '3') c3--;
		if (s[i] == '2')
		{
			c2--;
			c2333 -= c3 * (c3 - 1) * (c3 - 2) / 6;
			c233 -= c3 * (c3 - 1) / 2;
			c23 -= c3;
		}
	}
	writeline(ans);
	return 0;
}