AtCoder Beginner Contest 208

比赛链接

D Shortest Path Queries 2

Description

题目链接

Solution

设 $dp[i][j][k]$ 表示只允许经过城市 $1 \sim k$，从 $i$ 出发到 $j$ 所需要的最短时间。如果将经过的城市扩展到 $1 \sim k+1$，此时有两种情况：

• 不经过城市 $k+1$。
• 经过城市 $k+1$。显然我们不会经过同一个城市 $2$ 次，此时相当于从 $i$ 经过城市 $1 \sim k$ 到 $k+1$，再从 $k+1$ 经过城市 $1 \sim k$ 到 $j$。

由以上分析可得状态转移方程：$dp[i][j][k+1] = min(dp[i][j][k],dp[i][k+1][k]+dp[k+1][j][k])$。

时间复杂度为 $O(n^3)$。

Code

Shortest Path Queries 2

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXN = 404;
const int MOD = 1E9 + 7;
int n, m;
LL dp[MAXN][MAXN][MAXN];
LL ans = 0;

void Floyed() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j][k] =
                    min(dp[i][j][k - 1], dp[i][k][k - 1] + dp[k][j][k - 1]);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (dp[i][j][k] != 2e9) ans += dp[i][j][k];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int k = 0; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) dp[i][j][k] = 2e9;
    for (int i = 1; i <= n; i++)
        for (int k = 0; k <= n; k++) dp[i][i][k] = 0;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        for (int k = 0; k <= n; k++) dp[a][b][k] = min(dp[a][b][k], (LL)c);
    }
    Floyed();
    cout << ans;
    return 0;
}

E Digit Products

Description

题目链接

Solution

每一位在 $0 \sim 9$ 之间，故所有位的乘积可以表示成 $P = 2^a3^b5^c7^d$。由于最多有 $18$ 位，因此 $a \le 54, b \le 36, c \le 18,d \le 18$，故不同的乘积不超过 $54*36*18*18 = 629856$ 个。我们直接用 unordered_map 维护数位 $dp$ 就好了。

Code

Digit Products

#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;
LL n, k;
unordered_map<LL, LL> dp[20];
vector<int> v;

void add(LL& a, LL b) { a = a + b; }

signed main() {
    cin >> n >> k;
    while (n) {
        v.push_back(n % 10);
        n /= 10;
    }
    LL pre = 1;
    for (int i = v.size() - 1; ~i; i--) {
        if (i == v.size() - 1) {
            for (int j = 1; j < v[i]; j++) add(dp[i][j], 1);
            pre = pre * v[i];
            continue;
        }
        // 从顶上界转移
        for (int j = 0; j < v[i]; j++) add(dp[i][pre * j], 1);
        // 从全 0 转移
        for (int j = 1; j < 10; j++) add(dp[i][j], 1);
        // 不顶上界，不全为 0
        for (auto& pii : dp[i + 1]) {
            LL mul = pii.first;
            LL cnt = pii.second;
            for (int j = 0; j < 10; j++) add(dp[i][mul * j], cnt);
        }
        pre = pre * v[i];
    }
    if (pre <= k) add(dp[0][pre], 1);
    LL ans = 0;
    for (auto& pii : dp[0])
        if (pii.first <= k) add(ans, pii.second);
    cout << ans;
    return 0;
}

F Cumulative Sum

Description

题目链接

Solution

由于 $N$ 很大，暴力求解是行不通的，这里要用到拉格朗日插值，关键是确定 $f(N,M)$ 的次数。

首先用归纳法证明 $f(N,M)$ 是 $N$ 的 $M+K$ 次多项式：

• 假设 $f(N,M)$ 是关于 $N$ 的 $M+K$ 次多项式。
• 当 $M=0$ 时显然成立。
• $f(N,M+1) = \sum \limits_{n=1}^{N} f(n,M) = \sum \limits_{n=1}^{N} (n 的 M+K 次多项式) = (N 的 M+K+1 次多项式)$。

确定了 $f(N,M)$ 的次数，我们只需求出 $f(i,M),其中 1\le i \le M+K+1$，再用这 $M+K+1$ 个点插值便可快速求出该多项式在 $N$ 处的值。

时间复杂度为 $O((M+K)M)$。这里 $M$ 很小，可以通过。

Code

Cumulative Sum

#include <bits/stdc++.h>

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

using namespace std;
typedef long long LL;

const int MAXM = 35;
const int MAXN = 2.5E6 + 35;
const int MOD = 1e9 + 7;
LL n, m, k;
LL x[MAXN], y[MAXN];
LL f[2][MAXM];

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

// 插值点数，插值点，目标点，要求x连续递增
LL lagrange_cont(int n, LL* x, LL* y, LL k) {
    LL ans = 0;
    vector<LL> pre(n + 1), suf(n + 2), fac(n), inv(n);
    pre[0] = fac[0] = inv[0] = suf[n + 1] = 1;
    for (int i = 1; i <= n; i++) pre[i] = (k - x[i]) % MOD * pre[i - 1] % MOD;
    for (int i = n; i >= 1; i--) suf[i] = (k - x[i]) % MOD * suf[i + 1] % MOD;
    for (int i = 1; i < n; i++) fac[i] = fac[i - 1] * i % MOD;
    inv[n - 1] = qpow(fac[n - 1], MOD - 2, MOD);
    for (int i = n - 2; ~i; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
    for (int i = 1; i <= n; i++)
        ans =
            (ans + ((n - i) % 2 ? -1ll : 1ll) * y[i] * pre[i - 1] % MOD *
                       suf[i + 1] % MOD * inv[i - 1] % MOD * inv[n - i] % MOD) %
            MOD;
    return (ans + MOD) % MOD;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    for (int i = 1; i <= m + k + 1; i++) {
        x[i] = i;
        f[i % 2][0] = qpow(i, k, MOD);
        for (int j = 1; j <= m; j++)
            f[i % 2][j] = (f[(i - 1) % 2][j] + f[i % 2][j - 1]) % MOD;
        y[i] = f[i % 2][m];
    }
    cout << lagrange_cont(m + k + 1, x, y, n % MOD);
    return 0;
}

Bonus

将原题中 $M \le 30$ 改为 $M \le 10^7$，求 $f(N,M)$。