9.8 度小满笔试 50min AK

1、模拟

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int n, k;
    cin >> n >> k;
    vector<char> v(n);
    vector<int> idxs;
    idxs.push_back(0);
    int cnt = 0;
    for(int i = 0; i < n; ++i) {
        cin >> v[i];
        if(v[i] == 'A') {
            idxs.push_back(i);
            ++cnt;
        }
    }
    int ans = n * (k / cnt); 
    if(k % cnt) {
        ans += idxs[k % cnt] + 1;
    }
    else {
        ans -= (n - idxs.back() - 1);
    }
    cout  << ans;
}

2、深搜

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> mp;
vector<int> color;
const int mod = 1e9 + 7;
int dfs(int cur) {
    if(mp[cur].size() == 0) return 1;
    int res{};
    if(color[cur] == 1) {
        for(auto child : mp[cur]) {
            res += dfs(child);
        }
    }
    else {
        res = 1;
        for(auto child : mp[cur]) {
            res = (res * dfs(child)) % mod;
        }
    }
    return res % mod;
}
signed main() {
    int n;
    cin >> n;
    mp.resize(n + 1);
    color.resize(n + 1);
    int fa{};
    for(int i = 2; i <= n; ++i) {
        cin >> fa;
        mp[fa].push_back(i);
    }
    for(int i = 1; i <= n; ++i) cin >> color[i];
    cout << dfs(1);
}

3、快速幂(大概看了一下数据，感觉要快速幂)+深搜

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, A, B, M;
vector<vector<int>> mp;
int mod;

int fastmi(int a, int u) {
    int ans = 1;
    while(u) {
        if(u & 1) ans = (ans * a) % mod;
        u >>= 1;
        a = (a * a) % mod;
    }
    return ans % mod;
}

int dfs(int cur) {
    if(mp[cur].size() == 0) return 0;
    int res = 0;
    for(auto child : mp[cur]) {
        res = (res + (dfs(child) + fastmi(A, cur)) * B) % mod;
    }
    return res;
}

signed main() {
    cin >> n >> A >> B >> M;
    mod = M;
    mp.resize(n + 1);
    int fa{};
    for(int i = 2; i <= n; ++i) {
        cin >> fa;
        mp[fa].push_back(i);
    }
    cout << dfs(1);
}