## Xóa số

Gọi $s_i$ là tổng tiền tố đến vị trí $i$ của số.

Để số mới chia hết cho $3$, tức là ta phải xóa đi một đoạn $[l,r]$ sao cho $s_r - s_{l-1} \equiv s_n$ $(mod$ $3)$

Như vậy, nếu ta cố định $r$, ta cần đếm số $l$ sao cho $s_r - s_n \equiv s_{l-1}$ $(mod$ $3)$

Lúc này, bài toán quy về đếm phân phối cơ bản, lưu ý do đây là phép $mod$, và $s_r \le s_n$ nên có thể ta $mod$ ra bị âm, cần lấy $((s_r - s_n) \% 3 + 3) \% 3$.

Chú ý tồn tại trường hợp ta không xóa số nào.

<details>
<summary> Code</summary>

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e5 + 5;

int pre[maxn];
int cnt[3];
string s;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> s;
    s = '>' + s;

    for(int i = 1; i < s.size(); i++){
        pre[i] = pre[i - 1] + s[i] - '0';
        pre[i] %= 3;
    }

    int ans = 0;
    cnt[0]++;
    for(int i = 1; i < s.size(); i++){
        ans += cnt[(pre[i] - pre[s.size() - 1] + 3) % 3];
        cnt[pre[i]]++;
    }

    cout << ans - 1 + (pre[s.size() - 1] == 0);
}

</details>

## Xóa Phần Tử

Ta sẽ giải bài toán này bằng quy hoạch động.

Gọi $f(i,j)$ là số cách xóa dãy khi xét tới vị trí thứ $i$, và dãy đang có kết thúc là giá trị $j$.

Đầu tiên, gán $f(i,0) = 1$

Như vậy, ta có công thức truy hồi như sau:
- Đầu tiên, xét trường hợp ta không lấy số thứ $i$, tăng $f(i,j)$ lên một lượng $f(i-1,j)$
- Đối với trường hợp ta lấy phần tử $i$:
- Nếu $a_i = 1$: tăng $f(i,1)$ lên một lượng $f(i,0)$.
- Nếu $a_i = 2$:
- Giả sử trước đó dãy kết thúc bằng $1$: tăng $f(i,2)$ lên một lượng $f(i-1,1)$
- Giả sử trước đó dãy kết thúc bằng $2$: tăng $f(i,2)$ lên một lượng $f(i-1,2)$
- Nếu $a_i = 3$: tăng $f(i,3)$ lên một lượng $f(i,2)$.

Đáp án của bài toán là $f(n,3)$.

<details>
<summary> Code</summary>

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end());
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

const int maxn = 1e6 + 5;

int dp[maxn][4];
int n;

inline void inc(int &a, int b){
    if((a += b) >= mod) a -= mod;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        inc(dp[i][t], dp[i - 1][t - 1]);
        if(t == 2) inc(dp[i][t], dp[i - 1][t]);
        for(int j = 0; j <= 3; j++)
            inc(dp[i][j], dp[i - 1][j]);
}
    
    cout << dp[n][3];
}

</details>

## Chia Xâu Đối Xứng

Đặt $f(i)$ là số đoạn con ít nhất có thể chia ở dãy từ $1$ tới $i$ sao cho chúng đều là palindrome.

Dễ thấy, công thức truy hồi của ta sẽ là:
- $f(i) = min(f(j) + 1)$, $\forall j \in[0,i-1]$ thỏa mãn $[j+1,i]$ là một xâu đối xứng.

Giờ nếu có cách kiểm tra nhanh xem một đoạn $[l,r]$ bất kì có phải xâu đối xứng hay không, ta có thể giải quyết bài toán này trong $O(n^2)$.

Gọi $dp(i,j) = true$ nếu đoạn $[i,j]$ là một xâu đối xứng, ngược lại $dp(i,j) = false$:
- Đầu tiên khởi tạo $dp(i,j) = true$ với mọi $i > j$ và $0 \le i \le n+1$.
- Với $i \le j$, nếu $s_i = s_j$ và $dp(i+1,j-1) = true$ thì ta suy ra $dp(i,j) = true$.

Như vậy, ta có thể tính được mảng $dp(i,j)$ trong $O(n^2)$. Tuy nhiên, lưu ý rằng cần tính theo thứ tự độ dài đoạn tăng dần, vì nếu ta duyệt $i$ rồi duyệt $j$ như bình thường, thì khi tính $dp(i,j)$, ta chưa tính $dp(i+1,j-1)$. Chi tiết trong code mẫu.

Quay lại với bài toán gốc, giờ ta chỉ cần lưu thêm mảng truy vết là có thể hoàn thành.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n;
string s;
int f[N][N], d[N], trace[N];
void out(int n){
	if (trace[n] > 0)
		out(trace[n]);
	cout<<n<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    cin>>s;
    s.insert(0," ");
    for (int i=1; i <= n; i++)
        f[i][i]=1;
    for (int i=1; i < n; i++)
        if (s[i] == s[i+1])
            f[i][i+1]=1;
    for (int len=3; len <= n; len++)
        for (int i=1; i <= n-len+1; i++)
            {
                int j=i+len-1;
                if ((s[i] == s[j])&&(f[i+1][j-1] == 1))
                    f[i][j]=1;
            }
    for (int i=1; i <= n; i++) {
    	if (f[1][i] == 1) d[i]=1;
	}
    for (int i=1; i <= n; i++){
        if (d[i] == 0)
            d[i]=n+1;
        for (int j=1; j <= i; j++)
            if (f[j][i] == 1){
                if (d[i] > d[j-1]+1)
                    trace[i]=j-1;
					d[i]=min(d[i],d[j-1]+1);
				}
        }
    cout<<d[n]<<'\n';
    out(n);
    return 0;
}

</details>

## Xóa số

Để xây dựng dãy $A(n)$, đầu tiên ta cần sàng nguyên tố.

Sau khi có dãy $A(n)$, gọi $a$ là dãy miêu tả $A(n)$ với $a_i$ là chữ số thứ $i$, ta có thể tham lam bằng cách, nếu $a_i$ lớn hơn số kề với nó về bên trái và còn lượt xóa, ta sẽ xóa số kề với nó đi và xét tới số kề với nó về bên trái tiếp theo. Việc này có thể dễ dàng thực hiện bằng $stack$.

Sau khi thực hiện các thao tác trên mà vẫn còn lượt xóa, ta sẽ $pop$ dần các phần tử của $stack$ ra cho đến khi nào hết lượt.

Các chữ số của kết quả sẽ nằm trong $stack$, lưu ý cần in thứ tự ngược lại.

<details>
<summary>Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6+5;
int p[N];
int a[N],cnt;
int m,k;
void sieve () {
	int n = 1e6;
	for (int i=2; i<=n; i++) {
		p[i] = i;
	}
	int num = 0;
	for (int i=2; i<=n; i++) {
		if (p[i] == i) {
			int x = i;
			vector<int> v;
			while (x > 0) {
				v.push_back(x%10);
				x /= 10;
			}
			reverse(v.begin(),v.end());
			for (auto u : v) a[++cnt] = u;
			for (int j=i*i; j<=n; j+=i) p[j] = i;
			num++;
			if (num == m) break;
		}
	}
}
signed main () {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> k;
	sieve();
	stack<int> st;
	int cur = k;
	for (int i=1; i<=cnt; i++) {
		while (cur && st.size() && st.top() < a[i]) {
			cur--;
			st.pop();
		}
		st.push(a[i]);
	} 
 	while (cur > 0) {
 		st.pop();
 		cur--;
	 }
	vector<int> res;
	while (st.size()) {
		res.push_back(st.top());
		st.pop();
	}
	reverse(res.begin(),res.end());
	for (auto u : res) cout << u;
}

</details>

## XorSecond

Thay vì đi tính kết quả của mọi đoạn $[l,r]$, ta sẽ đi tính mọi kết quả có thể xảy ra.

Giả sử với một $a_i$, tồn tại một đoạn $[l,r]$ để nó là $MaxSecond(l,r)$, thì $Max(l,r)$ có thể chọn chỉ có thể là số gần nhất về bên trái với $a_i$ và lớn hơn $a_i$ hoặc số tương tự nhưng gần nhất về bên phải. Như vậy ta dễ dàng tìm được kết quả bài toán bằng $stack$ (kĩ thuật $stack$ đơn điệu giống bài trên).

Để chứng minh điều này, giả sử gọi $a_j$ là số gần nhất về bên trái với $a_i$ và lớn hơn $a_i$, $a_k$ là số gần thứ hai về bên trái với $a_i$ và lớn hơn $a_i$, sẽ không thể có đoạn $[l,r]$ nào thỏa mãn $a_i$ là $MaxSecond(l,r)$ và $a_k$ là $Max(l,r)$, bởi $k < j$. Tương tự với vế bên phải.

Ví dụ cho dãy:
- 1 5 2 4 3 6 7

- Giả sử như có một đoạn $[l,r]$ nào đó chứa $a_5 = 3$ là $MaxSecond(l,r)$, ta có thể thấy rằng $Max(l,r)$ của đoạn đó chỉ có thể là $a_4 = 4$ hoặc $a_6 = 6$.

- Không thể có chuyện tồn tại dãy $[l,r]$ nào đó chứa $MaxSecond(l,r) = 3$ mà $Max(l,r) = a_2 = 5$ được, bởi khi đó $MaxSecond(l,r)$ phải có giá trị bằng $a_4 = 4$.

- Tương tự ta có thể chứng minh rằng không thể có chuyện $Max(l,r) = a_7 = 7$ được, bởi khi đó $MaxSecond(l,r)$ phải bằng $a_6 = 6$.

Như vậy, ta sẽ duyệt qua toàn bộ $MaxSecond(l,r)$ có thể và tìm ra mọi $Max(l,r)$ tương ứng với nó, nghĩa là ta sẽ không bỏ sót cặp nghiệm nào cả và có thể tìm ra kết quả tối ưu.

<details>
<summary> Code</summary>

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 1e5+5;
int a[N];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i=1; i<=n; i++) cin >> a[i];
	stack<int> st;
	int res = 0;
	for (int i=1; i<=n; i++) {
		while (st.size() && st.top() < a[i]) st.pop();
		if (st.size()) res = max (res,st.top()^a[i]);
		st.push(a[i]);
	}
	reverse(a+1,a+n+1);
	while (st.size()) st.pop();
	for (int i=1; i<=n; i++) {
		while (st.size() && st.top() < a[i]) st.pop();
		if (st.size()) res = max (res,st.top()^a[i]);
		st.push(a[i]);
	}
	cout << res;
}

</details>