A 宝石

开场看错题 1.5h ，一直以为不能拿连续 $k$ 个宝石，然后发现 15pts 都不会，直接导致 T3 暴力都没打。。

我们考虑找出第一个位置，使得这个位置的颜色在之前出现过了，那么如果想继续往后选择，就必须把这个位置丢掉。我们一直重复找这种位置的过程，知道找到了第 $k+1$ 个，此时我们就只会在前面的东西种选择 $k$ 个扔掉。具体来说，对于每个出现了大于等于 $2$ 次的颜色我们只会保留最大的。

由于 $k$ 很小，我们可以考虑暴力做上面那个过程。每次之需要找到后面第一个重复出现的颜色即可。具体来说，我们可以记一个 $nxt_i$ 表示下一个与 $i$ 颜色相同的位置，然后我们就只需要找到 $s\sim n$ 中 $nxt_i$ 最小的位置即可。这个可以用线段树来维护 $nxt$ 的区间最小值。

于是我们暴力跳，暴力维护所有出现大于等于 $2$ 次的元素即可。

复杂度 $O(mk\log n)$ 。

B 字串

考虑一种最为暴力的过程，我们建出 ACAM ，然后设 $dp[u]$ 为 $u$ 出发期望走多少次会停止，然后转移就是

$$dp[u] = 1 + \sum_{c} p_c dp[nxt[u][c]]$$

于是我们暴力高消，就有了一个 $O(n^3m^3)$ 的优秀做法。

收到 $n = 1$ 的启发，我们考虑把后面的 $\sum$ 用 $dp[fail]$ 代替掉，于是有：

$$dp[u] = dp[fail] + \sum_{c \in son[u]} (dp[son[u][c]] - dp[son[fail][c]])$$

考虑移一下项，有

$$dp[u] - dp[fail] = \sum_{c \in son[u]}(dp[son[u][c]] - dp[son[fail][c]])$$

于是设 $g[u] = dp[u] - dp[fail]$ ，那么有

$$g[u] = \sum_{c \in son[u]} g[son[u][c]]$$

于是我们考虑对每个叶子设一个元，然后每个点的 $g$ 都可以用 $x_{1 \dots n}$ 来表示。当然，根是没有 $g$ 的定义的。

然后我们考虑怎么列方程。由于对于所有叶子，有 $dp[u] = 0$ ，也就是说有 $g[u] + g[fail[u]] + g[fail[fail[u]]] + \cdots + dp[rt] = 0$ ，于是如果我们把 $dp[rt]$ 设成一个元，对每个叶子都可以列出一个方程，就有了 $n+1$ 个元和 $n$ 个方程。我们再考虑根的 $dp$ 值，有 $dp[rt] = \sum_{c\in son[rt]} p_c(g[son[rt][c]] + dp[rt]) + 1$ ，因此有

$$\sum_{c \in son[rt]} p_c g[son[rt][c]] + 1 = 0$$

于是就有了 $n + 1$ 个方程和 $n + 1$ 个元，可以解决这个问题。

C 数论

乱搞题，但是有正经做法。

期望情况下，可以看出这个玩意需要进行的操作次数是 $O(len)$ 的。

我们考虑单独拿出最后 $B$ 位。首先可以发现，我们可以不考虑除以 $2$ 操作，直接把每次 $+1$ 变成加 lowbit ，最后加上末尾零的个数即可。于是我们考虑进行 $O(B)$ 次操作把最后 $B$ 位清零的过程（因为每次 $\times 3 + \text{lowbit}$ 一定会使得末尾零增多）。我们可以把 $\times 3$ 的过程分开来看，也就是说后面 $B$ 位直接乘三再加上 lowbit ，前面的位打一个标记表示乘三了。直到当你发现最后 $B$ 位全是 $0$ 的时候，就丢掉最后 $B$ 位，然后给前面乘上之前打的标记，再把最后 $24$ 位进位的东西加上去。

考虑这样做的复杂度是啥，一共要进行 $O(\frac{len}{B})$ 次这样的操作，然后每次的复杂度都是 $O(\frac{len}{B})$ ，因此总复杂度是 $O(\frac{len^2}{B^2})$ 。我们来优秀取一下块大小。为了不让最后一个块的值炸出 long long ，可以发现最后一个块一共会乘上 $3^B$ ，而最开始它是 $2^B$ 的，因此最后一个块的大小会变成 $6^B$ ，可以发现前面的每个位乘完后达到的最大值也是 $6^B$ ，因此取 $B = 24$ 就不会炸 long long 了。这东西由于常数小跑的飞快。

实际上是有有理有据的做法的。我们可以把前面说的这个乱搞做法扩展到类似分治 FFT 的过程，本质上就是把 B 取到 $\frac n 2$ 来分治做。复杂度可以做到 $O(\frac{n \log^2n}{\omega})$ 。

实际上我这乱搞极限数据只跑了 0.3s 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 300006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
#define lb( x ) ( ( x ) & -( x ) )
int n , len;
char ch[MAXN];

ll A[MAXN] , lz;

void solve() {
	scanf("%s",ch + 1);
	len = strlen( ch + 1 );
	int cur = 0 , cw = 0;
	per( i , len , 1 ) {
		if( cw == 24 ) cw = 0 , ++ cur;
		A[cur] |= ( ch[i] - '0' << cw );
		++ cw;
	}
	cw = 0;
	int opt = 0;
	int all = ( 1 << 24 ) - 1;
	for( int k = cw ; k <= cur ; ++ k ) {
		lz = 1;
		while( A[k] & all ) {
			if( k == cur && __builtin_popcount( A[k] ) == 1 ) break;
			++opt , lz = lz * 3;
			A[k] = A[k] * 3 + lb( A[k] );
		}
		rep( t , k + 1 , cur ) {
			A[t] = A[t] * lz + ( A[t - 1] >> 24 );
			A[t - 1] &= all;
		}
		if( A[cur] >> 24 ) ++ cur , A[cur] = A[cur - 1] >> 24 , A[cur - 1] &= all;
		if( A[cur] >> 24 ) ++ cur , A[cur] = A[cur - 1] >> 24 , A[cur - 1] &= all;
	}
	opt += 24 * cur + __builtin_ctz( A[cur] );
	cout << opt << endl;
}

signed main() {
	freopen("number.in","r",stdin) , freopen("number.out","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
	solve();
}