贪心+二分+DP+矩阵快速幂：CF461E

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133316261

https://codeforces.com/contest/461/problem/E

第一步：捕捉题目信息

  1. 四种字符 →\to 矩阵

  2. n≤1018→n\le 10^{18}\to 矩阵快速幂 →\to dp

  3. 最小值最大 →\to 二分

第二步：分析性质

ss 未知？那如果已知怎么做，肯定是每次暴力选最长的。

那么若 ss 被分成很多段，每段末尾必然不能接下一段开头成为 tt 的子串。

所以其实就和开头和结尾有关。那么我们就可以预处理 G[a][b]G[a][b] ，表示 aa 开头 bb 结尾的最短长度。

第三步：综合分析

那么接下来dp就很明显了， dpx,a,bdp_{x,a, b} 有 xx 串，开头为 aa ，结尾为 bb （不含 bb ）的最短长度，通过预处理的 GG 进行转移。

外面套个二分，里面拿个快速幂优化即可

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
//#define mo 
int pw(int a, int b) {
	int ans=1; 
	while(b) {
		if(b&1) ans*=a; 
		a*=a; b>>=1; 
	}
	return ans; 
}
int n; 
struct Martix {
	int a[5][5]; 
	void mem() {
		memset(a, 0, sizeof(a)); 
	}
	void mxx() {
		memset(a, 0x3f, sizeof(a)); 
	}
	void init() {
		mem(); 
		for(int i=0; i<4; ++i) a[i][i]=1; 
	}
//	void print()
	Martix operator *(const Martix &A) const {
		Martix B; B.mxx(); 
		int i, j, k; 
		for(i=0; i<=3; ++i) for(j=0; j<=3; ++j) for(k=0; k<=3; ++k)
			B.a[i][j]=min(B.a[i][j], a[i][k]+A.a[k][j]); 
		return B; 
	}
	int pan() {
		for(int i=0; i<=3; ++i)
			for(int j=0; j<=3; ++j) if(a[i][j]<n) return 0; 
		return 1; 
	}
	void print() {
		printf("---\n"); 
		for(int i=0; i<=3; ++i, printf("\n"))
		 	for(int j=0; j<=3; ++j) printf("%lld ", a[i][j]); 
	}
	int check(int b)  {
		Martix ans; ans.init(); 
		while(b) {
			if(b&1ll) {
				ans=ans*(*this); 
				if(ans.pan()) return 0; 
			}
			(*this)=(*this)*(*this); b>>=1ll; 
		}
//		ans.print();  
		return 1; 
	}
}G, F;
int m, i, j, k, T;
int l, r, mid, c[5][5]; 
char s[N]; 
unsigned long long sum[N], p[N], g; 
map<unsigned long long, int>mp; 

signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}
	n=read(); scanf("%s", s+1); m=strlen(s+1);
//	printf("== %lld\n", m); 
	for(i=1; i<=m; ++i) s[i]=s[i]-'A'; 
	for(i=p[0]=1; i<=m; ++i) sum[i]=sum[i-1]*5+s[i], p[i]=p[i-1]*5;  
	G.mem(); 
	int cnt=0; 
	for(l=2; cnt<16; ++l) {
		mp.clear(); 
		for(i=0; i<=3; ++i) for(j=0; j<=3; ++j) c[i][j]=0; 
		for(i=1; i+l-1<=m; ++i) {
			g=sum[i+l-1]-sum[i-1]*p[l]; 
			if(mp[g]) continue; mp[g]=1; 
			c[s[i]][s[i+l-1]]++; 
		}
		k=pw(4, l-2); 
//		printf("%lld %lld\n", k, cnt); 
//		printf("# %lld\n", l); 
//		for(i=0; i<=3; ++i, printf("\n"))
//		 	for(j=0; j<=3; ++j) printf("%lld ", c[i][j]); 
		for(i=0; i<4; ++i) for(j=0; j<4; ++j) 
			if(G.a[i][j]==0 && c[i][j]<k) G.a[i][j]=l-1, ++cnt; 
	}

//	for(i=0; i<4; ++i) for(j=0; j<4; ++j) 
//		printf("G[%c][%c]=%lld\n", i+'A', j+'A', G.a[i][j]); 
	l=0; r=n; 
	while(l<r) {
		mid=(l+r+1)/2; F=G; 
//		printf("[[%lld %lld]] %lld\n", l, r, mid); 
		if(F.check(mid)) l=mid; 
		else r=mid-1; 
	}
	printf("%lld", l+1);  
	return 0;
}