A - Sanitize Hands
题意：给定一个序列和m，问m按顺序减去这个序列，m >= 0情况下最多能减多少个数
思路：前缀和 + prev(upper_bound())
总结:disinfectan(消毒ji), disinfect(消毒，杀毒), aliens(外星人),
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
if (i) {
a[i] += a[i - 1];
}
}
cout << (upper_bound(a.begin(), a.end(), m) - a.begin()) << '\n';
}
B - Uppercase and Lowercase
题意：给个奇数长度字符串，如果大写字符数量大于小写字符数量，全小写，否则全大写。
思路：记录数量直接变。
总结：没读透彻题目，还在思考如果两种字符出现次数相等怎么办。才发现是奇数长度的字符串。
void solve() {
string s;
cin >> s;
int cnt0 = 0;
int cnt1 = 0;
for (const auto& x : s) {
if ('a' <= x && x <= 'z') {
cnt0++;
}
else {
cnt1++;
}
}
for (auto& x : s) {
if (cnt0 < cnt1) {
if ('a' <= x && x <= 'z') {
x += 'A' - 'a';
}
}
else if ('A' <= x && x <= 'Z'){
x += 'a' - 'A';
}
}
cout << s << '\n';
}
C - Sierpinski carpet
题意：给定一个3的k次幂的矩阵，每个矩阵可以分解为9个3的k-1次幂的小矩阵，其中中间的矩阵需要是白色，其他矩阵作为3的k-1次矩阵存在。输出该矩阵。
思路:深度遍历，每次给定当前矩阵的左上和右下坐标，在矩阵中遍历，中间矩阵染白，其他矩阵递归处理。
总结：在坐标的处理上把握不准确：一共有3行3列，我们只要考虑当前行列左上角的坐标即可，右下角的坐标直接用左上角的坐标加长度就行。左上角的坐标对于行来说，第2行加一个单位长度，第3行加两个单位长度，列也同理。然后其实也可以不用右下角坐标参数，只要传一个边长进去就行，这个边长一定是3的整数次幂。
在输出矩阵的时候wa了两次，习惯了数组输出中间加' '...
carpet(地毯)
void solve() {
int n;
cin >> n;
int m = pow(3, n);
vector<vector<char>> mat(m + 1, vector<char>(m + 1, '#'));
function<void(int, int, int, int)> dfs = [&](int x1, int y1, int x2, int y2) {
if (x1 == x2 && y1 == y2) {
return;
}
int d = (x2 - x1 + 1) / 3;
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
int u1 = x1 + (i - 1) * d;
int v1 = y1 + (j - 1) * d;
int u2 = u1 + d - 1;
int v2 = v1 + d - 1;
if (i == 2 && j == 2) {
while (u1 <= u2) {
for (int k = v1; k <= v2; ++k) {
mat[u1][k] = '.';
}
u1++;
}
}
else if (d > 1){
dfs(u1, v1, u2, v2);
}
}
}
};
dfs(1, 1, m, m);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= m; ++j) {
cout << mat[i][j];
}
cout << '\n';
}
}
D - 88888888
题意：给定一个数字x(x <= 1e18)，问这个数字重复x次对998244353取模是多少。
思路：从最高的前x位考虑，每次取模后的余数m+后x位是下一次要参与到取模计算的位，设t为pow(10, x的长度) % mod，
可以得出公式:(((x % mod * t) + x) % mod * t + x) + x) * t % mod + ...
x % mod是一个定值，设为res，先不考虑mod，公式写为(((res * t) + x) * t + x) * t + ...
第一项:res = x % mod
第二项:res * t + x
第三项:(res * t + x) * t + x = res * t² + x * t + x
第四项: res * pow(t, 3) + x * pow(t, 2) + x * t + x
..
第n项: res * pow(t, n - 1) + x * (pow(t, 1) + pow(t, 2) + .. + pow(t, n - 2))
根据上述公式，第一项快速幂直接得出结果，第二项是一个等比数列，根据等比数列公式 s = t * (1 - pow(t, n - 2)) / 1 - t。由于t是一个模运算的值，所以这里除法要用逆元的形式来求。
基于上述推导，可以使用快速幂+乘法逆元直接计算了，时间复杂度很低，乘法逆元使用费马小定理即可。
总结：赛时公式推导出来了，但是总感觉数字溢出了，最后比赛结束了才发现是除法没有去逆元。 这题目很棒。
快速幂的时候要注意次数一定要>=0，如果输入为1时，不需要按推导公式计算。
constexpr int mod = 998244353;
void solve() {
long long n;
cin >> n;
long long t = 1;
if (n == 1) {
cout << 1 << endl;
return;
}
for (auto x = n; x; x /= 10, t = (t * 10) % mod);
long long res = n % mod;
res = res * (1 + fastPower(t, n - 1, mod)) % mod +
n % mod * (t * (1 - fastPower(t, n - 2, mod)) % mod * fermatInverse(1 - t, mod) % mod) % mod;
cout << res % mod << endl;
}