AtCoder Beginner Contest 222

比赛链接

D Between Two Arrays

Description

题目链接

Solution

设 $dp[i][j]$ 表示构造出长度为 $i$，最后一个数为 $j$ 的序列的方案数，则有 $dp[i][j] = \sum \limits_{k<j} dp[i-1][k]$，这里要求 $a_i \le j \le b_i$。

初始条件为 $dp[0][0] = 1$，最终答案为 $\sum \limits_{i = a_n}^{b_n} dp[n][i]$。

Code

Between Two Arrays

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 3E3 + 5;
const int MOD = 998244353;
int n, m, T;
int dp[MAXN][MAXN], sum[MAXN], a[MAXN], b[MAXN];

void add(int& a, int b) { a = (a + b) % MOD; }

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 3000; j++)
            sum[j] = ((j ? sum[j - 1] : 0) + dp[i - 1][j]) % MOD;

        for (int j = a[i]; j <= b[i]; j++) dp[i][j] = sum[j];
    }
    int ans = 0;
    for (int i = a[n]; i <= b[n]; i++) add(ans, dp[n][i]);
    cout << ans;

    return 0;
}

E Red and Blue Tree

Description

题目链接

Solution

首先通过 BFS 或 DFS 求出从 $A_i$ 到 $A_{i+1}$ 的路径，从而求出每条边的经过次数 $cnt[]$。

问题转化为给每个 $cnt_i$ 赋予一个系数 $coef_i \in \{-1, 1\}$ （即把边赋为蓝色或红色），使得 $\sum cnt_i*coef_i=K$。

可以通过 DP 解决。设 $dp_{i,j}$ 表示计算前 i 条边，总和为 $j$ 的方案数，状态转移易得。

注意总和可能为负数，需要加上一个偏移量。另外可以使用滚动数组进一步节省空间。

Code

Red and Blue Tree

#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e3 + 3, MOD = 998244353;

int n, m, a[MAXN], k;
int cnt[MAXN];
vector<pair<int, int>> g[MAXN];
pair<int, int> pre[MAXN];
int vis[MAXN];

void getpath(int s, int t) {
    queue<int> q;
    for (int i = 1; i <= n; i++) vis[i] = 0, pre[i] = {0, 0};
    q.push(s), vis[s] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& e : g[cur]) {
            int to = e.first, id = e.second;
            if (!vis[to]) {
                q.push(to), vis[to] = true;
                pre[to] = {cur, id};
            }
        }
    }
    int cur = t;
    while (cur != s) {
        int id = pre[cur].second;
        cnt[id]++;
        cur = pre[cur].first;
    }
}

int dp[2][200005];

int main() {
    boost;
    cin >> n >> m >> k;
    int bias = n * m;
    for (int i = 1; i <= m; i++) cin >> a[i];
    for (int i = 1, u, v; i < n; i++) {
        cin >> u >> v;
        g[u].push_back({v, i - 1});
        g[v].push_back({u, i - 1});
    }
    for (int i = 1; i < m; i++) getpath(a[i], a[i + 1]);
    dp[1][bias] = 1;
    for (int i = 0; i < n - 1; i++) {
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        for (int j = 0; j <= 2 * bias; j++) {
            if (j + cnt[i] <= 2 * bias) dp[i & 1][j] = (dp[i & 1][j] + dp[(i & 1) ^ 1][j + cnt[i]]) % MOD;
            if (j - cnt[i] >= 0) dp[i & 1][j] = (dp[i & 1][j] + dp[(i & 1) ^ 1][j - cnt[i]]) % MOD;
        }
    }
    if (bias + k < 0) cout << 0 << endl;
    else cout << dp[(n - 2) & 1][bias + k] << endl;
    return 0;
}

F Expensive Expense

Description

题目链接

Solution

如果只计算一个点的答案，可以通过树形 DP 解决。设根节点为 1， $dp_i$ 表示 $i$ 到子树内的最大值花费，则 $dp_i = max\{dp_{son}+w, d_{son}+w\}$。此外用 multiset[] 记录从 节点 $i$ 出发，到其儿子节点的子树内的最大费用的可重集和，即 $\{max(dp_j+w, d_j+w)| j\in son_i\}$。

之后可以通过换根 DP 求出其它节点的答案。

设 $f_i$ 表示节点 $i$ 的正确答案，则 $f_1 = dp_1$。

对于 $i != 1$，首先从 $multiset_{fa_i}$ 减去 $max(dp[i] + w, d[i] + w)$，表示先不考虑 $i$ 的子树，$fa_i$ 到其它节点的最大费用。

如果 $multiset_{fa_i}$ 不为空，得到 $multiset_{fa_i}$ 中的最大值 $mx$，令 $f_i = max(dp_i, mx + w, d_{fa_i} + w)$，并将 $max(mx + w, d_{fa_i} + w)$ 插入到 $multiset_i$，表示 $i$ 到 $\{j \notin SubTree_i\}$ 的最大费用；否则直接令 $f_i = max(dp_i, d_{fa_i} + w)$，并将 $d_{fa_i} + w$ 插入到 $multiset_i$。

最后在将 $max(dp[i] + w, d[i] + w)$ 加回到 $multiset_{fa_i}$。

DFS 对每个节点进行上述操作即可得到每个点到其它节点的正确最大费用。

时间复杂度 $O(nlogn)$。上述思路可以通过前缀、后缀最大值做到 O(n) Link。

Code

Expensive Expense O(nlogn)

#include <bits/stdc++.h>

using namespace std;

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

#define int long long

constexpr int MAXN = 2e5 + 5, MOD = 1e9 + 7;

int n, d[MAXN], dp[MAXN], f[MAXN];
vector<pair<int, int>> g[MAXN];
multiset<int> s[MAXN];

void DP(int cur, int f) {
    for (const auto& [to, w] : g[cur]) {
        if (to == f) continue;
        DP(to, cur);
        dp[cur] = max({dp[cur], dp[to] + w, d[to] + w});
        s[cur].insert(max(dp[to] + w, d[to] + w));
    }
}

vector<int> vec;
void dfs(int cur, int fa) {
    for (const auto& [to, w] : g[cur]) {
        if (to == fa) continue;
        const int tmp = max(dp[to] + w, d[to] + w);

        s[cur].erase(s[cur].find(tmp));

        if (s[cur].size()) {
            int mx = *s[cur].rbegin();
            f[to] = max({f[to], dp[to], mx + w, d[cur] + w});
            s[to].insert({mx + w, d[cur] + w});
        } else {
            f[to] = max({f[to], dp[to], d[cur] + w});
            s[to].insert(d[cur] + w);
        }

        dfs(to, cur);

        s[cur].insert(tmp);
    }
}

signed main() {
    boost;
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++) {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i++) cin >> d[i];
    DP(1, 0);
    f[1] = dp[1];
    dfs(1, 0);
    for (int i = 1; i <= n; i++) cout << f[i] << "\n";
    return 0;
}

G 222

Description

题目链接

Solution

转化题意，即求最小的 $n$ 满足 $\frac{2}{9}(10^n-1) ≡ 0 \mod K$。设 $M = (K\&1?9K:\frac{9}{2}K)$，那么我们要求的是最小的 $n$，使得 $10^n≡1 \mod M$。

要让上面的等式成立，那么 $M$ 不能是 $2$ 或 $5$ 的倍数，即 $M$ 与 $10$ 互质。由欧拉定理可知 $10^{\phi(M)}≡1 \mod M$。可以证明满足条件的 $n$ 一定是 $\phi(M)$ 的约数（证明见官方题解），因此从小大到枚举 $\phi(M)$ 的约数并检查是否满足条件即可。

时间复杂度：$O(T\sqrt{M})$

Code

222

#include <bits/stdc++.h>

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 2E5 + 5;
const int MOD = 1E9 + 7;
int k;

LL qpow(LL a, LL b, LL MOD) {
    LL ans = 1, base = a % MOD;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

int phi(int x) {
    int ans = x;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            ans -= ans / i;
        }
    if (x != 1) ans -= ans / x; // 依据欧拉函数公式
    return ans;
}

vector<int> divisor(int x) {
    vector<int> ans;
    for (int i = 1; i * i <= x; i++)
        if (x % i == 0) {
            ans.push_back(i);
            if (i * i != x) ans.push_back(x / i);
        }
    sort(ans.begin(), ans.end());
    return ans;
}

void solve(int caseNum) {
    cin >> k;
    if (k % 2 == 0) k /= 2;
    k *= 9;
    if (__gcd(k, 10) != 1) return cout << -1 << endl, void();
    for (auto& d : divisor(phi(k)))
        if (qpow(10, d, k) == 1) return cout << d << endl, void();
}

signed main() {
    int testCase = 1;
    ios::sync_with_stdio(false);
    cin >> testCase;
    for (int i = 1; i <= testCase; i++) solve(i);
    return 0;
}

附上 BSGS 代码，当 $b = 1$ 且 $gcd(a, p) != 1$ 时无解:

BSGS

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

#define boost ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

constexpr int MAXN = 1e5 + 5;

namespace BSGS {
    struct custom_hash {
        static uint64_t splitmix64(uint64_t x) {
            x += 0x9e3779b97f4a7c15;
            x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
            x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
            return x ^ (x >> 31);
        }

        size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM =
                chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };

    int qpow(int a, int b, int p) {
        int res = 1;
        while (b) {
            if (b & 1) res = 1LL * res * a % p;
            a = 1LL * a * a % p;
            b >>= 1;
        }
        return res;
    }

    /* for a^x = b(mod p) where gcd(a, p) = 1*/
    int bsgsCoprime(int a, int b, int p) {
        if (__gcd(a, p) != 1) return -1;
        unordered_map<int, int, custom_hash> mp;
        int sq = sqrt(p) + 1;
        for (int i = 0, tmp; i <= sq; i++) {
            if (!i) tmp = b;
            else tmp = 1LL * tmp * a % p;
            mp[tmp] = i;
        }

        int gap = qpow(a, sq, p);
        for (int i = 0, tmp; i <= sq; i++) {
            if (!i) tmp = 1;
            else tmp = 1LL * tmp * gap % p;

            if (i == 1) {
                int res = INT_MAX;
                for (int j = 0, tmp; j <= sq; j++) {
                    if (!j) tmp = b;
                    else tmp = 1LL * tmp * a % p;
                    if (gap == tmp && i * sq - j > 0) res = min(res, i * sq - j);
                }
                if (res != INT_MAX) return res;
            } else if (mp.find(tmp) != mp.end()) {
                int j = mp[tmp];
                if (i * sq - j > 0) return i * sq - j;
            }
        }
        return -1;
    }
};

int main() {
    boost;
    int tc;
    cin >> tc;
    while (tc--) {
        int k;
        cin >> k;
        if (k & 1) k = 9 * k;
        else k = 9 * k / 2;
        cout << BSGS::bsgsCoprime(10, 1, k) << "\n";
    }
    return 0;
}