UOJ Logo gaolinxiang的博客

博客

2018 暑期集训 AB 班刷题营 Day2 题解

2018-08-05 13:25:04 By gaolinxiang

不要忘了点好评！

Update #1：Task #2 题解已更新。

Update #2：Task #3 题解已更新。已经全部更新完毕。

Task #1：占领地区 Occupy

Subtask #1：$n,m\le3000\ (50\ pts)$

直接暴力对网格图进行覆盖即可。

#include <cstdio>
const int subn = 3005;
int n, m, b[subn][subn];
int main() {
    scanf("%d %d", &n, &m);
    for (int x, y, k = 1; k <= m; k++) {
        scanf("%d %d", &x, &y);
        for (int i = x, j = y; i > 0 && j > 0; i--, j--) {
            b[i][j] = 1;
        }
        for (int i = x, j = y; i > 0 && j <= n; i--, j++) {
            b[i][j] = 1;
        }
        for (int i = x, j = y; i <= n && j > 0; i++, j--) {
            b[i][j] = 1;
        }
        for (int i = x, j = y; i <= n && j <= n; i++, j++) {
            b[i][j] = 1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            ans += !b[i][j];
        }
    }
    printf("%d\n", ans);
    return 0;
}
Subtask #2：$n\le100000,m\le3000\ (70\ pts)$

将两种对角线分开处理，将总答案分别减去这两种对角线的答案，再加上两种对角线重合的格子数量即可。直接计算的时间复杂度为 $\Theta(n+m^2)$。

Subtask #3：$n,m\le100000\ (100\ pts)$

如何快速计算出两种对角线重合的格子数量呢？枚举每一个 $x-y$ 为恒定值的对角线，用前缀和计算有几个 $x+y$ 为恒定值的对角线与之重合即可。时间复杂度 $\Theta(n+m)$。具体细节见代码。

#include <cstdio>
const int maxn = 100005;
const int maxm = 200005;
int n, m, bs[maxm], bd[maxm];
int abs(int x) {
    return x < 0 ? -x : x;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int x, y, i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        bs[x + y] = 1;
        bd[x - y + n] = 1;
    }
    long long ans = 1ll * n * n;
    for (int i = 2; i <= 2 * n; i++) {
        if (bs[i]) {
            ans -= n - abs(n + 1 - i);
        }
    }
    for (int i = 1; i < 2 * n; i++) {
        if (bd[i]) {
            ans -= n - abs(n - i);
        }
    }
    for (int i = 2; i <= 2 * n; i++) {
        bs[i] += bs[i - 2];
    }
    for (int i = 1; i < 2 * n; i++) {
        if (bd[i]) {
            int x = abs(n - i);
            ans += bs[2 * n - x] - bs[x];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

Task #2：匹配 Match

Subtask #1：$n,m\le4\ (20\ pts)$

直接暴力枚举同学的位置即可。

Subtask #2：$n,m\le300\ (50\ pts)$

我们考虑对于每条边计算总共经过这条边的次数。我们发现对于每种配对方案，我们肯定是将一条边左边的 $男\ /\ 女$ 同学有先和右边的 $女\ /\ 男$ 同学配对。我们设这条边断开后两个联通块的大小为 $size_0$ 和 $size_1$，则经过它的方案数为：

$$\sum_{i=0}^{m}\sum_{j=0}^{m}(\min(i, m-j)+\min(m-i, j))\times C^i_mC^j_m\times size_0^i\cdot size_1^{m-i}\cdot size_0^j\cdot size_1^{m-j}$$

直接计算的复杂度为 $\Theta(nm^2)$。

Subtask #3：$n,m\le2500\ 最多只有一条边的权值为正\ (20\ pts)$

对于权值为 $0$ 的边跳过即可。结合前述算法可得 $70\ pts$。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int maxm = 10005;
const ll P = 1e9 + 7;
int n, m, sz[maxn];
int tot, ter[maxm], wei[maxm], nxt[maxm], lnk[maxn];
ll ans, power[maxn][maxn], inv[maxn], fact[maxn], finv[maxn];
ll C(int n, int m) {
    return fact[n] * finv[m] % P * finv[n - m] % P;
}
void addedge(int u, int v, int w) {
    ter[++tot] = v;
    wei[tot] = w;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
}
void dfs(int u, int p = 0) {
    sz[u] = 1;
    for (int v, w, e = lnk[u]; e; e = nxt[e]) {
        v = ter[e], w = wei[e];
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (w == 0) continue;
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= m; j++) {
                ll x = w * (min(i, m - j) + min(m - i, j)) % P;
                x = x * C(m, i) % P * C(m, j) % P;
                x = x * power[sz[v]][i] % P * power[n - sz[v]][m - i] % P;
                x = x * power[sz[v]][j] % P * power[n - sz[v]][m - j] % P;
                ans = (ans + x) % P; 
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        power[i][0] = 1;
        for (int j = 1; j <= m; j++) {
            power[i][j] = power[i][j - 1] * i % P;
        }
    }
    inv[1] = 1;
    for (int i = 2; i <= m; i++) {
        inv[i] = (P - P / i) * inv[P % i] % P;
    }
    fact[0] = finv[0] = 1;
    for (int i = 1; i <= m; i++) {
        fact[i] = fact[i - 1] * i % P;
        finv[i] = finv[i - 1] * inv[i] % P;
    }
    for (int u, v, w, i = 1; i < n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    dfs(1);
    printf("%lld\n", ans);
    return 0;
}
Subtask #4：$n,m\le2500\ (100\ pts)$

我们发现可以预处理出：

$$\sum_{i+j=m}(\min(i, m-j)+\min(m-i, j))\times C^i_mC^j_m$$

发现剩下的式子只和 $i+j$ 有关，然后对于每条边就可以 $\Theta(m)$ 计算了。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 5005;
const int maxm = 10005;
const ll P = 1e9 + 7;
int n, m, sz[maxn];
int tot, ter[maxm], wei[maxm], nxt[maxm], lnk[maxn];
ll ans, power[maxn][maxm], inv[maxn], fact[maxn], finv[maxn], sum[maxm];
ll C(int n, int m) {
    return fact[n] * finv[m] % P * finv[n - m] % P;
}
void addedge(int u, int v, int w) {
    ter[++tot] = v;
    wei[tot] = w;
    nxt[tot] = lnk[u];
    lnk[u] = tot;
}
void dfs(int u, int p = 0) {
    sz[u] = 1;
    for (int v, w, e = lnk[u]; e; e = nxt[e]) {
        v = ter[e], w = wei[e];
        if (v == p) continue;
        dfs(v, u);
        sz[u] += sz[v];
        if (w == 0) continue;
        for (int i = 0; i <= 2 * m; i++) {
            ll x = w * sum[i] % P;
            x = x * power[sz[v]][i] % P * power[n - sz[v]][2 * m - i] % P;
            ans = (ans + x) % P;
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        power[i][0] = 1;
        for (int j = 1; j <= 2 * m; j++) {
            power[i][j] = power[i][j - 1] * i % P;
        }
    }
    inv[1] = 1;
    for (int i = 2; i <= m; i++) {
        inv[i] = (P - P / i) * inv[P % i] % P;
    }
    fact[0] = finv[0] = 1;
    for (int i = 1; i <= m; i++) {
        fact[i] = fact[i - 1] * i % P;
        finv[i] = finv[i - 1] * inv[i] % P;
    }
    for (int u, v, w, i = 1; i < n; i++) {
        scanf("%d %d %d", &u, &v, &w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= m; j++) {
            sum[i + j] = (sum[i + j] + (min(i, m - j) + min(m - i, j)) * C(m, i) % P * C(m, j) % P) % P;
        }
    }
    dfs(1);
    printf("%lld\n", ans);
    return 0;
}

Task #3 导数卷积 Convolution

Subtask #1：$n\le200\ (20\ pts)$

直接暴力计算即可。时间复杂度 $\Theta(n^3)$。

Subtask #2：$n\le1000\ (40\ pts)$

直接暴力计算 $f^{(i)}$ ，然后 NTT 计算卷积即可。时间复杂度 $\Theta(n^2\log_2n)$。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1 << 13 | 1;
const ll P = 998244353, g = 3;
int n, m, k, r[maxn];
ll a[maxn][maxn], b[maxn], c[maxn];
ll mpow(ll a, ll b) {
    ll c = 1;
    b = (b % (P - 1) + P - 1) % (P - 1);
    for (; b; b >>= 1, a = a * a % P) {
        if (b & 1) {
            c = a * c % P;
        }
    }
    return c;
}
void ntt(ll *a, int n, int type) {
    for (int i = 0; i < n; i++) {
        if (i < r[i]) {
            swap(a[i], a[r[i]]);
        }
    }
    for (int k = 1; k < n; k <<= 1) {
        ll x = mpow(g, type * (P - 1) / (k << 1));
        for (int i = 0; i < n; i += k << 1) {
            ll y = 1;
            for (int j = i; j < i + k; j++, y = x * y % P) {
                ll p = a[j], q = y * a[j + k] % P;
                a[j] = (p + q) % P, a[j + k] = (p - q + P) % P;
            }
        }
    }
    if (type == -1) {
        ll x = mpow(n, P - 2);
        for (int i = 0; i < n; i++) {
            a[i] = x * a[i] % P;
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[0][i]);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - 1; j++) {
            a[i][j] = 1ll * (j + 1) * a[i - 1][j + 1] % P;
        }
    }
    for (m = 1; m < n; m <<= 1) k++;
    for (int i = 0; i < m; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (k - 1));
    }
    for (int i = 0; i < n; i++) {
        ntt(a[i], m, 1);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            b[j] = a[i][j] * a[n - i - 1][j] % P;
        }
        ntt(b, m, -1);
        for (int j = 0; j < n; j++) {
            c[j] = (b[j] + c[j]) % P;
        }
    }
    for (int i = 0; i < n; i++) {
        printf("%lld%c", c[i], " \n"[i == n - 1]);
    }
    return 0;
}
Subtask #3：$n\le5000\ (60\ pts)$

令 $F_i$ 为 $f(x)$ 第 $i$ 项的系数。则有：

$$G_d=\sum_{i=0}^{n-1}\sum_{0}^{d}F_{i+j}\cdot\dfrac{(i+j)!}{j!}\times F_{n-1+d-i-j}\cdot\dfrac{(n-1+d-i-j)!}{(d-j)!}$$

令 $H_i=I!\cdot F_i$，原式变为：

$$G_d=\sum_{i=0}^{n-1}\sum_{j=0}^dH_{i+j}\cdot\dfrac{1}{j!}\times H_{n-1+d-i-j}\cdot\dfrac{1}{(d-j)!}$$ $$G_d=\sum_{i=0}^{n-1+d}H_i\times H_{n-1+d-i}\cdot\sum_{0}^{d}\dfrac{1}{(d-j)!j!}$$ $$G_d=\dfrac{2^d}{d!}\cdot\sum_{i=0}^{n-1+d}H_i\times H_{n-1+d-i}$$

直接计算的复杂度为 $\Theta(n^2)$。

Subtask #4：$n\le100000\ (100\ pts)$

使用 NTT 计算上式，即可将复杂度优化到 $\Theta(n\log_2n)$。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int maxm = 1 << 18 | 1;
const ll P = 998244353, g = 3;
int n, m, b, r[maxm];
ll inv[maxn], finv[maxn];
ll fact[maxn], pow2[maxn];
ll A[maxm], B[maxm];
ll power(ll a, ll b) {
    ll c = 1;
    b = (b % (P - 1) + P - 1) % (P - 1);
    for (; b; b >>= 1, a = a * a % P) {
        if (b & 1) {
            c = a * c % P;
        }
    }
    return c;
}
void prework() {
    inv[1] = 1;
    for (int i = 2; i < n; i++) {
        inv[i] = (P - P / i) * inv[P % i] % P;
    }
    fact[0] = finv[0] = 1;
    for (int i = 1; i < n; i++) {
        fact[i] = fact[i - 1] * i % P;
        finv[i] = finv[i - 1] * inv[i] % P;
    }
    pow2[0] = 1;
    for (int i = 1; i < n; i++) {
        pow2[i] = pow2[i - 1] * 2 % P;
    }
    for (m = 1; m < n << 1; m <<= 1) b++;
    for (int i = 0; i < m; i++) {
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (b - 1));
    }
}
void ntt(ll *a, int n, int type) {
    for (int i = 0; i < n; i++) {
        if (i < r[i]) {
            swap(a[i], a[r[i]]);
        }
    }
    for (int k = 1; k < n; k <<= 1) {
        ll x = power(g, type * (P - 1) / (k << 1));
        for (int i = 0; i < n; i += k << 1) {
            ll y = 1;
            for (int j = i; j < i + k; j++, y = x * y % P) {
                ll p = a[j], q = y * a[j + k] % P;
                a[j] = (p + q) % P, a[j + k] = (p - q + P) % P;
            }
        }
    }
    if (type == -1) {
        ll x = power(n, P - 2);
        for (int i = 0; i < n; i++) {
            a[i] = a[i] * x % P;
        }
    }
}
int main() {
    scanf("%d", &n);
    prework();
    for (int i = 0; i < n; i++) {
        scanf("%lld", &A[i]);
        A[i] = B[i] = A[i] * fact[i] % P;
    }
    ntt(A, m, 1), ntt(B, m, 1);
    for (int i = 0; i < m; i++) {
        A[i] = A[i] * B[i] % P;
    }
    ntt(A, m, -1);
    for (int i = 0; i < n; i++) {
        A[i + n - 1] = A[i + n - 1] * finv[i] % P * pow2[i] % P;
    }
    for (int i = n - 1; i < 2 * n - 1; i++) {
        printf("%lld%c", A[i], " \n"[i == 2 * n - 2]);
    }
    return 0;
}

评论

liukaiyuan
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 14:31:27
wcx
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 14:37:43
hepan
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 15:45:02
hepan
%%%
  • 2018-08-05 15:45:55
siyuan
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 15:46:29
RainAir
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 15:53:00
zhuky_RLG
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 15:53:17
zmwang
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 15:58:16
l___z___t
英文名题目是什么操作%%%
  • 2018-08-05 17:39:58
RyeCatcher
前排膜拜未来IOI选手高麟翔
  • 2018-08-05 19:07:56
gaolinxiang
我可菜了，您们可假了。
  • 2018-08-05 22:48:08
da32s1da
前排膜拜未来IOI选手高麟翔
  • 2018-08-06 07:59:44
PQF
前排膜拜未来IOI金牌选手高麟翔
  • 2018-08-06 08:18:56
shleodai
后排膜拜未来IOI金牌选手高麟翔
  • 2018-08-06 09:13:04
xuruiyang
%%%
  • 2018-08-06 14:55:41
cppascalinux
膜拜未来IOI冠军选手高麟翔
  • 2018-08-06 17:53:05
larryzhong
前排膜拜未来 $\text{IOI}$ 世界第一选手高麟翔。 这场比赛我只会 $50 + 20 + 20 = 90$ 分。您太强了！
  • 2018-08-06 21:54:17
gaolinxiang
@larryzhong 太假了！！！
  • 2018-08-06 21:56:07
chentongfei
膜拜未来IOI冠军选手高麟翔
  • 2018-08-06 22:22:42
harryhe
前排膜拜未来IOI选手高麟翔
  • 2018-08-07 09:05:00

中文 English

Server time: 2024-11-24 16:37:57   |   浙ICP备17047493号