把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

2020西安EC-final A
题目大意：给一个长度为n(1e6)的字符串，包含大小写字母和0-9间的数字，问其中有多少个形如”namomo”的子序列（未必连续），也就是1234四个字母各不相同,56分别和34相同。

解：

由于字母有62个，硬dp的话至少需要662621e6的复杂度（你至少需要选择两个），但是考虑到结构问题，如果只是求出以a开头或是结尾时长度为b种类为c的序列数量是不需要储存和遍历n的，这样一来复杂度就是62^(c-1)b（因为第一种也就是排头或结尾的字母完不用储存而是直接运算并并入接下来的长度里，所以第二种字母可以直接储存）
在本题中namomo sequence有四种字母，即使用63^3n的算法依然过不了，所以考虑在这个dp里只关系到两个字母，另外两个字母用前缀和直接求出来。
显然选择momo这两个字母更加容易，因为na两个字母没有顺序问题的担忧，于是dp[m][o][3]来表示上述dp，因为是在从后往前推，所以表示的是m为m，并且当前位置就是m开头的位置时的方案数量，那么前面ab的数量可以用容斥原理求出。
即C(pos-1,2)的总量-两个字母相同的的量-一个字母是m一个不是的量-一个字母是o一个不是的量再加上两个字母分别是m和o的量，相乘即可。
由于题目的阴间卡常以及dp和容斥的常数存在，把模运算改成了快速的模加法运算才在cf上2300ms冲过去。
值得一提的是由于当前位置的m之后仅仅会以第3位的形式出现，当前位置的dp[m][o][0]不会再被用到，所以可以新建一个变量去计算，也可以每次都把dp[m][o][0]置0即可，复杂度并没有太大的变化，6.2e7的复杂度常数稍微高一点就会被T了，人菜常数大选手表示卑微。

代码

代码
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize(3)
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 1000005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define PI 3.14159265358979
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll getpos(int p, ll n) {
	return n / cpow(10, p - 1) % 10;
}
ll getwei(ll n) {
	int res = 0;
	while (n) {
		res++;
		n /= 10;
	}
	return res;
}
//ll F[300005], inv[300005];
//void initF()
//{
//	F[0] = inv[0] = 1;
//	for (int i = 1; i <= 300000; i++)F[i] = F[i - 1] * i % mdl;
//	inv[300000] = cpow(F[300000], mdl - 2);
//	for (int i = 299999; i >= 1; i--)inv[i] = inv[i + 1] * (i + 1) % mdl;
//}
//ll C(ll n, ll m)
//{
//	return F[n] * inv[m] % mdl * inv[n - m] % mdl;
//}
/*

---------------------------------------------------------------------
100
10
0 0 0 0 0 3 2 8 2 2

*/
int a[maxn];
int pre[maxn][62];
int dp[62][62][3];
char str[1000002];
inline void add(int& x, int y) {
	x = (x + y < mdl ? x + y : x + y - mdl);
}
int main()
{
    //cfast;

	int t=1;
//	cin >> t;
	while (t--) {
		int ans = 0;
		//string str;
		scanf("%s", str);
		int len = strlen(str);
		inc(i, 1, len+1) {
			if (str[i-1] >= '0' && str[i-1] <= '9')a[i] = str[i-1] - '0';
			else if (str[i-1] >= 'a' && str[i-1] <= 'z')a[i] = 10 + str[i-1] - 'a';
			else a[i] = 36 + str[i-1] - 'A';
			inc(j, 0, 62) {		
				pre[i][j] = pre[i - 1][j];
			}
			pre[i][a[i]]++;
		}
		for (int i = len; i >= 3; i--) {
			int m = a[i];
			inc(j, 0, 62) {
				if (m == j)continue;
				add(dp[m][j][0], dp[j][m][1]);
				add(dp[m][j][1], dp[j][m][2]);
				add(dp[m][j][2], pre[len][j] - pre[i][j]);
			//	cout << "i=" << i << " dp.0=" << dp[m][j][0] << endl;
			}
			int tmp = (1ll*(i - 1) * (i - 2) / 2) % mdl;
			inc(j, 0, 62) {
				add(tmp,mdl - (1ll * pre[i - 1][j] * (pre[i - 1][j] - 1) / 2) % mdl);
			}
			inc(j, 0, 62) {
				int minu = (1ll * (pre[i - 1][j]) * (i - 1 - pre[i - 1][j]) % mdl + 1ll * (pre[i - 1][m]) * (i-1 - pre[i - 1][m]) % mdl)%mdl;
				int tt = tmp;
				add(tt, mdl - minu);
				add(tt, 1ll * pre[i - 1][m] * pre[i - 1][j] % mdl);
				add(ans, 1ll * tt * dp[m][j][0] % mdl);
				dp[m][j][0] = 0;
			}
		}
		printf("%d\n", ans);
		
	}
	return 0;
}