atcoder abc357

A Sanitize Hands 

问题：

思路：前缀和，暴力，你想咋做就咋做

代码：

#include 

using namespace std;

const int N = 2e5 + 10;

int n, m;
int a[N];

int main() {
    cin >> n >> m;
    for(int i = 1; i > a[i];
    }
    
    int ans = 0;
    for(int i = 1; i <= n; i ++ ) {
        m -= a[i];
        ans = i;
        if(m <= 0) break;
    }
    
    if(m < 0) cout << ans - 1;
    else cout << ans;
    return 0;    
}

B Uppercase and Lowercase

问题：

思路：大小写转换，这里有个问题，为什么我的转换最后都变成数字了，先留个疑问

代码：

#include 
#include 
#include 

using namespace std;

const int N = 2e5 + 10;

string str;

int main() {
    cin >> str;
    int cnt1 = 0, cnt2 = 0;
    for(auto t: str) {
        if(t >= 'a' && t = cnt2)
    transform(str.begin(),str.end(),str.begin(),::tolower);
    else 
    transform(str.begin(),str.end(),str.begin(),::toupper);
    cout<<str<<endl;
    return 0;
}

C Sierpinski carpet

问题：

思路：阴间题，第一眼递归，但是不想求太多坐标，于是想到把图全变成‘#’最后填充’.’

代码：

#include 
#include 
#include 

using namespace std;

const int N = pow(3, 6) + 10;

char g[N][N];
int n;

int main() {
    cin >> n;
    int len = pow(3, n);
    for(int i = 1; i <= len; i ++ ) {
        for(int j = 1; j <= len; j ++ ) {
            g[i][j] = '#';
        }
    }
    
    for(int level = 1; level <= n; level ++ ) {
        for(int i = 1 + pow(3, level - 1); i <= len; i += pow(3, level)) {
            for(int j = 1 + pow(3, level - 1); j <= len; j += pow(3, level)) {
                for(int k = i; k <= i + pow(3, level - 1) - 1; k ++ ) {
                    for(int u = j; u <= j + pow(3, level - 1) - 1; u ++ ) {
                        g[k][u] = '.';
                    }
                }
            }
        }
    }
    
    for(int i = 1; i <= len; i ++ ) {
        for(int j = 1; j <= len; j ++ ) {
            cout << g[i][j];
        }
        cout << endl;
    }
    return 0;
}

D 88888888

问题：

思路：逆元，快速幂，对原式子变形后发现最后的结果实际上就是x 乘上一个等比数列，这是碰见的第一道逆元的题目，也明确了我对逆元的认识，由于 a / b % mod != (a % mod/ b % mod) % mod，而直接除的话会造成精度丢失，因此我们可以把除法变成乘法，根据费马小定理如果b和p互质，那么b的逆元就等于b ^ p – 2 因此可以快速幂求逆元

代码：
 

#include 

using namespace std;

const int mod = 998244353;

long long x;

int get(long long a) {
    int cnt = 0;
    while(a) {
        a /= 10;
        cnt ++;
    }
    return cnt;
}

long long qmi(long long a, long long b) {
    long long res = 1;
    while(b) {
        if(b & 1) res = ((res % mod) * (a % mod)) % mod;
        b >>= 1;
        a = (a % mod * a % mod) % mod;
    }
    return res;
}

int main() {
    cin >> x;
    int len = get(x);
    long long part1 = x % mod;
    long long a = qmi(10, (long long)len);
    long long b = qmi(a, x);
    b --;
    long long c = qmi(a - 1, 998244353 - 2);
    long long part2 = (b % mod * c % mod) % mod;
    cout << (part1 * part2) % mod;
    return 0;
}

E Reachability in Functional Graph

问题：

思路：考虑如果题目是一颗树的话那么直接一个记忆化即可，但是该题会出现环，因此考虑缩点，记得开long long

据说这是基环树板子，回头学一下基环树

代码：

#include 
#include 
#include 
#include 

F