剑锋所指,心之所向。

目前完成:

abl

abc 179

abc 175

abc 174

abc 173

abc 172

abc 171

abc175

D Moving Piece Editorial

给出常数 k,有 n 个点,每个点有一条唯一的出边 nxt_i,保证 nxt 为一个 1 \cdots n 的排列。每个点有一个权值 v_i

你可以任意选一个点作为出发点,并进行以下步骤不超过 k 次(不能不进行):

  • 从当前点走到当前点的出点。并且你将得到当前点的权值的分数。

求最多能得到多少分数。


容易看出问题等价与,给出一个环,你能走不超过 k 步,求最大的和。

破环为链,一个显然的 dp,令 f_i 表示以 i 为终点最大的和。

有:

f_i = \max_{j \in [i - len, i)} sum_i - sum_j + \big\lfloor \dfrac{k - (i - j)}{L}\big\rfloor \times \max(0, S)

其中,sum 代表前缀和,S 是整个环的和,L 是环长。

直接暴力搞是 O(n^2) 的,这题数据范围比较小,能过。

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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

namespace IO {
    #define gc getchar()
    template <typename T>
    inline void read(T& x) {
        x = 0; bool f = 1; char ch;
        for (ch = gc; ch < '0' || '9' < ch; ch = gc) if (ch == '-') f ^= 1;
        for (; '0' <= ch && ch <= '9'; ch = gc) x = (x << 3) + (x << 1) + (ch ^ 48);
        x = f ? x : -x;
    }
    #undef gc
}

typedef long long ll;

const int MAXN = 1e6 + 10;

int n, k, nxt[MAXN], len[MAXN];
ll val[MAXN], sum[MAXN << 1], f[MAXN << 1], arr[MAXN << 1], fans = -LONG_LONG_MAX;

bool vis[MAXN];

int m;

void work(int st) {
    m = 0;
    int cur = nxt[st];
    while (1) {
        arr[++m] = val[cur], vis[cur] = true;
        if (cur == st) break;
        cur = nxt[cur];
    }
    rep(i, 1, m) arr[++m] = arr[i];
    rep(i, 1, m) sum[i] = sum[i - 1] + arr[i];
    int mxlen = min(m >> 1, k);
    ll mxval = -LONG_LONG_MAX; int mxval_len = 0;
    rep(i, 1, m) {
        f[i] = -LONG_LONG_MAX;
        rep(j, max(i - mxlen, 0), i - 1) {
            f[i] = max(sum[i] - sum[j] + 1ll * max(sum[m >> 1], 0ll) * ((k - i + j) / (m >> 1)), f[i]);
        }
        mxval = max(f[i], mxval);
    }
    fans = max(fans, mxval);
}

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(nxt[i]);
    rep(i, 1, n) IO::read(val[i]);
    rep(i, 1, n) if (!vis[i]) {
        work(i);
    }
    printf("%lld\n", fans);
    return 0;
}

考虑优化,最后一项的 \big\lfloor \dfrac{k - (i - j)}{L}\big\rfloor,取值只有可能有两种:\big\lfloor \dfrac{k}{L} \big\rfloor 以及 \big\lfloor \dfrac{k}{L} \big \rfloor - 1

取得 \big\lfloor \dfrac{k}{L} \big\rfloor 的一对 (i, j),必有 i - j \leq k \bmod L。因此,这一段可以把后面一项去掉,前面一项就可以直接单调队列。

取得后面一项的则没有任何限制,因此,也可以单调队列。

代码待补。

E Picking Goods

给出一个 R \times C 的网格,网格上有 k 个格子上有分数。

你从 (1, 1) 出发,每次向下或右走,最终走到 (R, C)。每次走到一个有分数的点可以选择是否拿走分数。每一行至多拿走三个格子的分数。

求最多一共能拿走多少分数。


直接 dp,f(i, j, 0/1/2/3) 表示走到 (i, j) 拿了 0/1/2/3 个格子最大分数。

时间复杂度 O(n^2)

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

const int MAXN = 3000 + 10;

typedef long long ll;

int n, m, k, val[MAXN][MAXN];
ll f[4][MAXN][MAXN];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= k; ++i) {
        int x, y, _val; scanf("%d %d %d", &x, &y, &_val);
        val[x][y] = _val;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for (int pre = 0; pre <= 3; ++pre) f[0][i][j] = max(f[0][i][j], f[pre][i - 1][j]), f[1][i][j] = max(f[1][i][j], f[pre][i - 1][j] + val[i][j]);
            f[0][i][j] = max(f[0][i][j], f[0][i][j - 1]);
            for (int cnt = 1; cnt <= 3; ++cnt) {
                f[cnt][i][j] = max(f[cnt][i][j], max(f[cnt][i][j - 1], f[cnt - 1][i][j - 1] + val[i][j]));
            }
        }
    }
    ll ans = 0;
    for (int cnt = 0; cnt <= 3; ++cnt) ans = max(ans, f[cnt][n][m]);
    printf("%lld\n", ans);
    return 0;
}

F Making Palindrome

N 个字符串 S_i,你需要选择若干个字符串,满足将其按照某种顺序拼接后,是一个回文串。一个字符串可以选择多次。每个字符串都有一个代价。

求最小代价和。

|S_i| \leq 20N \leq 50


考虑在左右依次交替放一个串。如果一个字符在右侧有匹配的字符,则将这个字符删去。这样每次都只会在一边剩下一些字符。状态可以由 (0/1, S) 描述,表示现在在 左/右 剩下字符串 S

因为我们是在左右交替放,所以剩下的字符一定是 N 个字符串中某个字符串的 前/后 缀。因此,至多只有 2000 种剩下的后缀。共 4000 个节点。

考虑直接 dij,每次枚举出边,分类讨论一下即可。

时间复杂度 O(M \log M)M \leq 2000

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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define m_p make_pair

namespace IO {
    #define gc getchar()
    template <typename T>
    inline void read(T& x) {
        x = 0; bool f = 1; char ch;
        for (ch = gc; ch < '0' || '9' < ch; ch = gc) if (ch == '-') f ^= 1;
        for (; '0' <= ch && ch <= '9'; ch = gc) x = (x << 3) + (x << 1) + (ch ^ 48);
        x = f ? x : -x;
    }
    #undef gc
}

typedef long long ll;

const int MAXN = 2000 + 10;

template <typename T>
bool chkmin(T& a, T b) { if (a > b) return a = b, true; return false; }
template <typename T>
bool chkmax(T& a, T b) { if (a < b) return a = b, true; return false; }

int n;
string str[MAXN], id_to_str[MAXN];
bool is_palindrome[MAXN];
unordered_map<string, int> str_to_id;
ll val[MAXN], ans = LONG_LONG_MAX, dis[2][MAXN], vis[2][MAXN];

typedef pair<int, int> Node;
typedef pair<ll, Node> plii;

priority_queue<plii, vector<plii>, greater<plii> > que;

bool starts_with(string& a, string& b) {
    if (a.size() < b.size()) return false;
    rep(i, 0, b.size() - 1) if (a[i] != b[i]) return false;
    return true;
}

Node trans(int flg, string u, string v) {
    Node ret; ret.first = 0, ret.second = 0;
    string res;
    if (flg == 0) reverse(v.begin(), v.end());
    else reverse(u.begin(), u.end());
    if (flg == 0 && starts_with(u, v) || flg == 1 && starts_with(v, u)) {
        ret.first = 0;
        if (flg == 1) res = v.substr(u.size(), v.size() - u.size() + 1);
        else res = u.substr(v.size(), u.size() - v.size() + 1);
    } else if (flg == 0 && starts_with(v, u) || flg == 1 && starts_with(u, v)) {
        ret.first = 1;
        if (flg == 0) res = v.substr(u.size(), v.size() - u.size() + 1);
        else res = u.substr(v.size(), u.size() - v.size() + 1);
        reverse(res.begin(), res.end());
    } else {
        ret.first = -1;
        return ret;
    }
    ret.second = str_to_id[res];
    return ret;
}

int main() {
    IO::read(n);
    str_to_id[""] = 0;
    rep(i, 1, n) {
        cin >> str[i]; IO::read(val[i]);
        string cur; cur.clear();
        rep(j, 0, str[i].size() - 1) {
            cur.push_back(str[i][j]);
            if (!str_to_id.count(cur)) {
                int _sz = str_to_id.size();
                str_to_id[cur] = _sz;
            }
        }
        cur.clear();
        per(j, str[i].size() - 1, 0) {
            cur = str[i][j] + cur;
            if (!str_to_id.count(cur)) {
                int _sz = str_to_id.size();
                str_to_id[cur] = _sz;
            }
        }
    }
    for (auto _cur : str_to_id) {
        string cur = _cur.first;
        string ruc = cur;
        id_to_str[_cur.second] = cur;
        reverse(ruc.begin(), ruc.end());
        is_palindrome[_cur.second] = (cur == ruc);
    }
    rep(i, 0, str_to_id.size()) dis[0][i] = dis[1][i] = LONG_LONG_MAX;
    rep(i, 1, n) {
        if (is_palindrome[str_to_id[str[i]]]) ans = min(ans, val[i]);
        chkmin(dis[0][str_to_id[str[i]]], val[i]);
        chkmin(dis[1][str_to_id[str[i]]], val[i]);
        que.push(m_p(val[i], m_p(0, str_to_id[str[i]])));
        que.push(m_p(val[i], m_p(1, str_to_id[str[i]])));
    }
    while (!que.empty()) {
        plii u = que.top(); que.pop();
        if (vis[u.second.first][u.second.second]) continue;
        vis[u.second.first][u.second.second] = true;
        rep(i, 1, n) {
            Node v = trans(u.second.first, id_to_str[u.second.second], str[i]);
            if (v.first == -1) continue;
            if (chkmin(dis[v.first][v.second], dis[u.second.first][u.second.second] + val[i])) {
                que.push(m_p(dis[v.first][v.second], v));
            }
        }
    }
    rep(i, 0, str_to_id.size()) {
        if (is_palindrome[i]) chkmin(ans, min(dis[0][i], dis[1][i]));
    }
    if (ans >= (LONG_LONG_MAX >> 1)) { puts("-1"); return 0; }
    printf("%lld\n", ans);
    return 0;
}

abc 174

grade

D Alter Altar

给出一个长度为 n 的由 RW 构成的字符串 Sn \leq 200000)。每次可以任选以下操作进行一次:

  • 将某两个字符 swap
  • 将某个字符取反(由 R 变成 W,反之亦然)

最少进行多少次操作,使得最后的序列不存在 i \in [1, n),满足 S[i] == 'W' && S[i + 1] == 'R'


最终的字符串一定是形如:

\text{RRR}\cdots \text{RWWW}\cdots \text{W}

猜了个结论,一定存在一个次数最小的操作,满足没有用到第二种操作。

所以最终的串是固定的,O(n) 扫一遍就好了。

不知道为啥这是对的,下午去问问 Juanzhang。

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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

namespace IO {
    #define gc getchar()
    template <typename T>
    inline void read(T& x) {
        x = 0; bool f = 1; char ch;
        for (ch = gc; ch < '0' || '9' < ch; ch = gc) if (ch == '-') f ^= 1;
        for (; '0' <= ch && ch <= '9'; ch = gc) x = (x << 3) + (x << 1) + (ch ^ 48);
        x = f ? x : -x;
    }
    #undef gc
}

const int MAXN = 200000 + 10;

int n, arr[MAXN], cnt1, ans;
char str[MAXN];

int main() {
    IO::read(n);
    scanf("%s", str + 1);
    rep(i, 1, n) arr[i] = (str[i] == 'R');
    rep(i, 1, n) cnt1 += arr[i];
    rep(i, 1, cnt1) ans += !arr[i];
    printf("%d\n", ans);
    return 0;
}

E Logs

你有长为 n 的序列 A。可以进行以下操作不超过 k 次:

  • 选择序列中的元素 A_i,规定一个 t \in (0, A_i),删除 A_i 并加入 tA_i - t

求操作后,最大元素最小值。


直接二分答案 x,可以发现把一个长度为 L 的元素操作成合法的若干个元素至少需要 \big\lfloor \dfrac{L - 1}{x} \big\rfloor 次操作。

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

#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)

namespace IO {
    #define gc getchar()
    template <typename T>
    inline void read(T& x) {
        x = 0; bool f = 1; char ch;
        for (ch = gc; ch < '0' || '9' < ch; ch = gc) if (ch == '-') f ^= 1;
        for (; '0' <= ch && ch <= '9'; ch = gc) x = (x << 3) + (x << 1) + (ch ^ 48);
        x = f ? x : -x;
    }
    #undef gc
}

typedef long long ll;

const int MAXN = 2e5 + 10;

int n, k, arr[MAXN];

bool check(int x) {
    ll cnt = 0;
    rep(i, 1, n) cnt += (arr[i] - 1) / x;
    return cnt <= k;
}

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(arr[i]);
    int l = 1, r = *max_element(arr + 1, arr + n + 1), ans;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}

F Range Set Query

静态数区间颜色个数。

n \leq 5 \times 10^5


经典问题。

考虑一段区间内的某个颜色的所有元素构成的集合,只会有一个元素有贡献。

所以我们就钦定最靠右的那个元素有贡献。打上标记。

发现每加入一个元素,只会至多有两个位置被修改。所以可以维护一个可持久化数组,求个区间和就行。

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

const int MAXN = 5e5 + 10;
const int MAX_NODE_CNT = MAXN << 6;

int n, m, lst[MAXN];

struct Persistent_Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls(_) t[_].ls
    #define rs(_) t[_].rs
    #define lq(_) t[_].ls, l, mid
    #define rq(_) t[_].rs, mid + 1, r
    int node_cnt, rt[MAXN];
    int& operator [](const int& x) { return rt[x]; }
    struct node { int ls, rs, data; } t[MAX_NODE_CNT]; 
    int build(int l, int r) {
        int cur = ++node_cnt;
        if (l == r) return cur;
        ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
        return cur;
    }
    int modify(int pre, int l, int r, int pos, int val) {
        int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
        if (l == r) { return cur; }
        if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
        else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
        return cur;
    }
    int query(int cur, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return t[cur].data;
        int ret = 0;
        if (ql <= mid) ret += query(lq(cur), ql, qr);
        if (qr > mid) ret += query(rq(cur), ql, qr);
        return ret; 
    } 
} t;

int main() {
    scanf("%d %d", &n, &m);
    t[0] = t.build(1, n);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x); t[i] = t.modify(t[i - 1], 1, n, i, 1);
        if (lst[x]) t[i] = t.modify(t[i], 1, n, lst[x], -1);
        lst[x] = i;
    }
    int pre_ans = 0;
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d %d", &u, &v);
        printf("%d\n", (t.query(t[v], 1, n, u, v)));
    }
    return 0;
}

abc178

grade

C Ubiquity

统计长度为 n 的数列的个数,满足:

  • a_i \in [0, 9]
  • \exist i, \ a_i = 0
  • \exist i, \ a_i = 9

容斥,全部的减去没有 9 的减去没有 0 的加上没有 0, 9 的。

ll qpower(int a, int x) {
    ll ret = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? ret = 1ll * ret * a % P : 0;
    return ret;
}

int main() {
    IO::read(n);
    printf("%lld\n", ((qpower(10, n) - 2 * qpower(9, n) % P + qpower(8, n)) % P + P) % P);
    return 0;
}

感觉自己对这种容斥还不太熟悉(

E Dist Max

给出 n 个点,求任意点对曼哈顿距离最大值。

n \leq 2 \times 10^5


x 递增加入,这样保证第一维可以拆开。

第二维相当于是求一个前后缀最大值。

BIT 维护即可。

int main() {
    IO::read(n);
    rep(i, 1, n) IO::read(arr[i].first), IO::read(arr[i].second), tmp[i] = arr[i].second;
    sort(arr + 1, arr + n + 1), sort(tmp + 1, tmp + n + 1);
    int _n = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    rep(i, 1, n) num[i] = lower_bound(tmp + 1, tmp + _n + 1, arr[i].second) - tmp;
    rep(i, 1, n) {
        if (i > 1) ans = max(ans, arr[i].first + max(arr[i].second + bit1.query(num[i]), bit2.rquery(num[i]) - arr[i].second));
        bit1.add(num[i], -(arr[i].first + arr[i].second)), bit2.radd(num[i], -arr[i].first + arr[i].second);
    }
    bit1.clear(), bit2.clear();
    per(i, n, 1) {
        if (i < n) ans = max(ans, -arr[i].first + max(arr[i].second + bit1.query(num[i]), bit2.rquery(num[i]) - arr[i].second));
        bit1.add(num[i], -(-arr[i].first + arr[i].second)), bit2.radd(num[i], arr[i].first + arr[i].second);
    }
    printf("%lld\n", ans);
    return 0;
}

然而可以 O(n)

void solve() {
  int n = read();
  int mx1 = -1e18, mx2 = -1e18, mn1 = 1e18, mn2 = 1e18;
  rep(i, 1, n) {
    int x = read(), y = read();
    chkmax(mx1, x + y), chkmin(mn1, x + y);
    chkmax(mx2, x - y), chkmin(mn2, x - y);
  }
  int ans = max(mx1 - mn1, mx2 - mn2);
  cout << ans << endl;
}

(source:Juanzhang)

F Contrast

给出两个不降的序列 A, B,重排 B,使得 \nexists i, A_i = B_i

n \leq 2\times 10^5


构造 1:

考虑 reverse(B)。这样之后至多会有一个区间的 BA 相同,并且这个区间的值都一样。然后从左右找能够替换的就行。

int main() {
    IO::read(n);
    rep(_, 0, 1) rep(i, 1, n) IO::read(arr[_][i]), cnt[_][arr[_][i]]++;
    reverse(arr[1] + 1, arr[1] + n + 1);
    rep(i, 1, n) if (arr[0][i] == arr[1][i]) val = arr[0][i], pos.push_back(i);
    int l = 1, r = n; bool flg = false;
    for (auto cur_pos : pos) {
        if (flg == false) {
            if (arr[0][l] != val && arr[1][l] != val) {
                swap(arr[1][l], arr[1][cur_pos]);
                ++l;
            } else flg = true;
        }
        if (flg == true) {
            if (arr[0][r] != val && arr[1][r] != val) {
                swap(arr[1][r], arr[1][cur_pos]);
                --r;
            } else return puts("No"), 0;
        }
    }
    puts("Yes");
    rep(i, 1, n) printf("%d ", arr[1][i]);
    return 0;
}

构造 2:

B shift 一段距离可以合法。(不太清楚为什么这是必要的)。

对于每个值,shift 的合法距离是一段区间,把这些区间并起来就好。

int main() {
    IO::read(n);
    ansr = INT_MAX;
    rep(_, 0, 1) rep(i, 1, n) IO::read(arr[_][i]);
    rep(_, 0, 1) rep(i, 1, n) {
        if (arr[_][i] != arr[_][i - 1]) l[_][arr[_][i]] = i;
        if (arr[_][i] != arr[_][i + 1]) r[_][arr[_][i]] = i;
    }
    rep(i, 1, n) {
        if (l[0][i] && l[1][i]) {
            ansl = max(ansl, r[0][i] - l[1][i] + 1);
            // ansr = min(ansr, abs(l[0][i] - r[1][i]));
            ansr = min(ansr, l[0][i] - r[1][i] + n - 1);
        }
    }
    // printf("l = %d, r = %d\n", ansl, ansr);
    if (ansl > ansr) return puts("No"), 0;
    puts("Yes");
    rep(i, 1, n) {
        ans[(i + ansl - 1) % n + 1] = arr[1][i];
    }
    rep(i, 1, n) printf("%d ", ans[i]);
    return 0;
}

abc173

D Chat in a Circle \color{red}\times

n 个人,每个人有一个权值,现在按某种顺序插入到一个环上。对于插入的第 i 个人(i > 1),随意安排他插入的位置,并且将获得与他相邻的两个位置的人的权值的最小值的分数。求最多分数。

n \leq 2\times 10^5


看起来应该是按权值降序地插入,然后每次贪心。

证明如下:

假设有 x, y, a, b,满足 x > y > a > b

如果是按照权值降序插入,则是:

(x, y) \rightarrow (x, a, y) \rightarrow (x, b, a, y)\ \text{or}\ (x, a, b, y)

贡献是 \min(x, y) + a

如果先插入了 b,则是:

(x, y) \rightarrow (x, b, y) \rightarrow (x, b, a, y)\ \text{or}\ (x, a, b, y)

贡献是 \min(x, y) + b

显然第一种更优。

确定插入顺序之后考虑插入位置。如果每次都贪心插入到分数最大的地方,可以获得最大分数。因为不存在一个比他更大的方案,因为每个数都最多贡献两次。

时间复杂度 O(n)

int main() {
    IO::read(n);
    rep(i, 1, n) IO::read(arr[i]);
    sort(arr + 1, arr + n + 1), reverse(arr + 1, arr + n + 1);
    ans += arr[1];
    int cnt = 1, i = 2;
    while (cnt <= n - 1) {
        if (cnt == n - 1) break;
        ans += 1ll * min(2, n - 1 - cnt) * arr[i];
        i++, cnt += min(2, n - 1 - cnt);
    }
    printf("%lld\n", ans);
    return 0;
}

E Multiplication 4 \color{red}\times

给出 n 个数(可能为负数),取 k 个数,使得乘积最大。

n \leq 2 \times 10^5


每次要么取最小的两个数,要么取最大的。

贪心就行。

int main() {
    IO::read(n), IO::read(k);
    rep(i, 1, n) IO::read(arr[i]);
    sort(arr + 1, arr + n + 1);
    if (k & 1 && arr[n] < 0) {
        per(i, n, n - k + 1) ans = 1ll * ans * arr[i] % P;
        printf("%lld\n", (ans + P) % P);
        return 0;
    }
    int l = 1, r = n, tot = 0;
    if (k & 1) ans = arr[n] % P, r--, tot++;
    while (l <= r && tot <= k) {
        if (tot == k) break;
        ll numl = arr[l] * arr[l + 1];
        ll numr = arr[r] * arr[r - 1];
        if (numl > numr) ans = 1ll * numl % P * ans % P, l += 2, tot += 2;
        else ans = 1ll * numr % P * ans % P, r -= 2, tot += 2;
    }
    printf("%lld\n", (ans % P + P) % P);
    return 0;
}

F Intervals on Tree \color{green} \sqrt{}

给出一棵树,函数 f(i, j) 代表,下标在 [i, j] 之间的点的生成子图的连通块个数。

\sum_{l = 1}^n \sum_{r = l}^n f(l, r)

n \leq 2 \times 10^5


树上 V 个点 E 条边的子图的连通块个数为 V - E

就能直接算了。

int main() {
    IO::read(n);
    rep(i, 1, n) ans += 1ll * (n - i + 2) * (n - i + 1) / 2;
    rep(i, 1, n - 1) {
        int a, b;
        IO::read(a), IO::read(b);
        if (a > b) swap(a, b);
        ans -= 1ll * a * (n - b + 1);
    }
    printf("%lld\n", ans);
    return 0;
}

abc 171

F Strivore

给出一个小写拉丁字符串 S。一次操作被定义为:

  • 在当前串的某个位置(可以为开头或结尾)插入一个小写字符。

问一共有多少个可以以 S 为初始串,经过 K 次操作得到。

998244353 取模。


问题等价与问有多少个串,满足长度为 |S| + K,且 S 为其子序列。

考虑一个显然的 DP。状态由 (i, j) 描述,表示现在填了 i 位,并且匹配 S 到了 j。则:

f(i, j) = \sum_{c = a}^\text{z} f(i - 1, j - [S(j) = c])

即:

f(i, j) = 25 \times f(i - 1, j) + f(i - 1, j - 1)

因此我们发现,答案是与 S 无关的

上式可以联想到杨辉三角。

事实上考虑当 S 全部由 \text{a} 组成时,答案即为求大小为 |S| + K 的包含至少 |S|a 的字符串个数。

枚举恰有多少个 a 即可。

const int MAXN = 1e7 + 10;
const int P = 1e9 + 7;

int prod[MAXN], inv[MAXN], k, s;
char str[MAXN];

int Combine(int n, int m) { return 1ll * prod[n] * inv[n - m] % P * inv[m] % P; }

int qpower(int a, int x) {
    int res = 1;
    for (; x; x >>= 1, a = 1ll * a * a % P) x & 1 ? res = 1ll * res * a % P : 0;
    return res;
}

void add(int& a, int b) { a = a + b > P ? a + b - P : a + b; }

int main() {
    prod[0] = 1;
    rep(i, 1, MAXN) prod[i] = 1ll * prod[i - 1] * i % P;
    inv[0] = inv[1] = 1;
    rep(i, 2, MAXN) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    rep(i, 2, MAXN) inv[i] = 1ll * inv[i] * inv[i - 1] % P;
    IO::read(k);
    scanf("%s", str + 1);
    s = strlen(str + 1);
    int ans = 0;
    rep(i, s, k + s) {
        // printf("%d\n", Combine(k + s, i));
        add(ans, 1ll * Combine(k + s, i) * qpower(25, k + s - i) % P);
    }
    printf("%d\n", ans);
    return 0;
}

实际上也可以从数学的角度由

f(i, j) = 25 \times f(i - 1, j) + f(i - 1, j - 1)

推导出

f(i, j) = \binom{i}{j} \times 25^{i - j}

数学归纳一下可以证明。

不过也能由打表看出其规律,大概和 25 的次幂有关。并且指数从左到右递减。

abl

E Replace Digits

维护一个十进制数。操作设计将某一位到某一位上的所有数字改为 x,并输出其 \bmod\ 998244353 的值。

位数 \leq 2 \times 10^5


可以直接对位建线段树。


const int MAXN = 2e5 + 10;
const int P = 998244353;

int n, q, _pow10[MAXN], inv[MAXN];

int getsum(int k) {
    return 1ll * ((_pow10[k] - 1) % P + P) % P * inv[9] % P;
}

struct Segment_Tree {
    #define mid ((l + r) >> 1)
    #define ls k << 1, l, mid
    #define rs k << 1 | 1, mid + 1, r
    struct Node { int val, tag; } t[MAXN << 2];
    void pushup(int k) { t[k].val = (t[k << 1].val + t[k << 1 | 1].val) % P; }
    void pushdown(int k, int l, int r) {
        if (t[k].tag != -1) {
            t[k << 1].tag = t[k].tag, t[k << 1 | 1].tag = t[k].tag;
            t[k << 1].val = 1ll * t[k].tag * getsum(mid - l + 1) % P * _pow10[n - mid] % P;
            t[k << 1 | 1].val = 1ll * t[k].tag * getsum(r - mid) % P * _pow10[n - r] % P;
            t[k].tag = -1;
        }
    }
    void build(int k, int l, int r) {
        t[k].tag = -1;
        if (l == r) return t[k].val = _pow10[n - r], void();
        build(ls), build(rs);
        pushup(k);
    }
    void modify(int k, int l, int r, int ql, int qr, int val) {
        if (ql <= l && r <= qr) {
            t[k].tag = val;
            t[k].val = 1ll * val * getsum(r - l + 1) % P * _pow10[n - r] % P;
            return ;
        }
        pushdown(k, l, r);
        if (ql <= mid) modify(ls, ql, qr, val);
        if (qr > mid) modify(rs, ql, qr, val);
        pushup(k);
    }
} sgt;

int main() {
    _pow10[0] = 1;
    inv[0] = inv[1] = 1;
    rep(i, 2, MAXN - 1) inv[i] = 1ll * (P - P / i) * inv[P % i] % P;
    rep(i, 1, MAXN - 1) _pow10[i] = 1ll * _pow10[i - 1] * 10 % P;
    IO::read(n), IO::read(q);
    sgt.build(1, 1, n);
    rep(i, 1, q) {
        int l, r, val;
        IO::read(l), IO::read(r), IO::read(val);
        sgt.modify(1, 1, n, l, r, val);
        printf("%d\n", sgt.t[1].val);
    }
    return 0;
}

F Heights and Pairs

给出 2n 个数,求将这 2n 个数分成 n 对,使得 \forall (a, b),满足 a \neq b 的方案数。

n \leq 5\times10^4, a_i \leq 10^5


SJX 大爷给我讲了讲。尽管我不会 NTT,但还是记录一下咋做吧(

\text{cnt}(i) 代表 i 这个数出现的次数。

考虑 f(i, j) 代表值域为 [1, i],钦定有 j 个数对相等。

那么

f(i, j) = \sum_{k = 0}^{\lfloor\frac{\text{cnt}(i)}{2}\rfloor} \binom{\text{cnt}(i)}{2k} \times \binom{2k}{k} \times k! \times f(i - 1, j - k)

g(i, k) 记为前面的系数,则

f(i, j) = \sum_{k = 0}^{\lfloor\frac{\text{cnt}(i)}{2}\rfloor} g(i, k)\times f(i - 1, j - k)

记答案多项式

F = \sum_{i = 1}^n f(10^5, i) \times x^i

G_n = \sum_{i = 1}^n g(n, i) \times x^i

F = \prod_{i = 1}^{10^5} G_n

利用分治 NTT 解决即可。

国庆 Day1 模拟赛赛后题解与总结
上一篇 «
莫比乌斯函数的应用与莫比乌斯反演
» 下一篇