王清楚

2023-02-23 10:28 牛客运营

发布于北京

关注

【题解】"蔚来杯"2022牛客暑期多校训练营（加赛）

A

考虑如何快速计算 $f (x)$ ，若把 $x$ 差分一下，则需要最后序列全 $1$ 。而每次修改相当于改变两个或一个地方的值。

令 $w=\sum_{i=1}^{k-1}[x_i=x_{i+1}]$ ，则 $f(x)=\lceil\frac{w}{2}\rceil$ 。

把上取整换成 $\frac{1}{2}(w+w\ \rm mod\ 2)$ ，分开计算。

对于前者，枚举子序列中的一对相邻位置， $l\leq i<j\leq r$ 并且 $s_{i} = s_{j}$ ，方案数有 $2^{i-l}\times 2^{r-j}=2^{r-l+i-j}$ 种。总所有贡献和为：

\sum_{l\leq l<r\leq r,s_i=s_j}2^{r-l+i-j}=2^{r-l}\sum_{l\leq i<j\leq r,s_i=s_j}2^{i-j}\\ =2^{r-l}\Bigg(\sum_{1\leq i<j\leq r,s_i=s_j}2^{i-j}-\sum_{1\leq i<l,l\leq j\leq r,s_i=s_j}2^{i-j}-\sum_{1\leq i<j<l,s_i=s_j}2^{i-j}\Bigg)

预处理即可 $\mathcal O(1)$ 计算。

而 $w$ 为奇数的子序列个数。因为 $w$ 的奇偶性等于(子序列长度 $+[s_{st}=s_{ed}]$ )的奇偶性。

特判 $ed-st\leq 1$ 的子序列，发现其他的情况，偶数和奇数的个数相等，都是 $2^{ed-st-2}$ 。

这一部分的贡献为：

\sum_{l\leq i<r}[s_i=s_{i+1}]+\sum_{l\leq i<j-1<r}2^{j-i-2}=\sum_{l\leq i<r}[s_i=s_{i+1}]+\sum_{2\leq i\leq r-l}(r-l-i+1)2^{i-2}

预处理也可 $\mathcal O(1)$ 计算。所以总的复杂度是 $\mathcal O(n+q)$ 的。

当然也可以线段树维护区间矩阵来做，复杂度略高。

#include <bits/stdc++.h>
#define MOD 1000000007
#define int long long
using namespace std;
const int N=5000010;
int inv2 = 500000004;
int n, q, al, bl, ar, br, l, r;
string s;
int a[N];
int p2[N], twon[N], w[N], pre1[N], pre2[N][2], pre2n[N][2];
void INIT() {
    p2[0] = twon[0] = 1;
    w[0] = 0;
    for (int i = 1; i <= n; i++) {
        p2[i] = p2[i - 1] * 2 % MOD;
        twon[i] = twon[i - 1] * inv2 % MOD;
        w[i] = (w[i - 1] + (a[i] == a[i + 1])) % MOD;
    }
    for (int i = 1; i <= n; i++) {
        pre1[i] = (pre1[i - 1] + pre2[i - 1][a[i]] * twon[i] % MOD) % MOD;
        pre2[i][!a[i]] = pre2[i - 1][!a[i]];
        pre2n[i][!a[i]] = pre2n[i - 1][!a[i]];
        pre2[i][a[i]] = (pre2[i - 1][a[i]] + p2[i]) % MOD;
        pre2n[i][a[i]] = (pre2n[i - 1][a[i]] + twon[i]) % MOD;
    }
}
signed main() {
    cin >> n >> q;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        a[i] = s[i - 1] - '0';
    }
    cin >> al >> bl >> ar >> br >> l >> r;
    int ans = 0;
    INIT();
    for (int i = 1; i <= q; i++) {
        l = (l * al + bl) % n + 1;
        r = (r * ar + br) % n + 1;
        if (l > r)
            swap(l, r);
        if (l == r) {
            ans = ans ^ (23 * i);
            continue;
        }
        if (r - l == 1) {
            ans = ans ^ (23 * i + (a[l] == a[r]));
            continue;
        }
        int res = 0;
        res = (pre1[r] - pre1[l - 1] + MOD) % MOD;
        res = (res - (pre2n[r][0] - pre2n[l - 1][0] + MOD) % MOD * pre2[l - 1][0] % MOD) % MOD;
        res = (res - (pre2n[r][1] - pre2n[l - 1][1] + MOD) % MOD * pre2[l - 1][1] % MOD) % MOD;
        res = res * p2[r - l] % MOD;
        res = (res + w[r - 1] - w[l - 1] + MOD) % MOD;
        res = (res + (r - l - 1) * (p2[r - l - 1] - 1 + MOD) % MOD -
                  ((r - l - 3) * p2[r - l - 1] + 2 + MOD) % MOD + MOD) %
                 MOD;
        res = (res * inv2) % MOD;
        ans ^= res + 23 * i;
    }
    cout << ans;
}

B

对于在树上的点， $a n s_{i}$ 就是以 $i$ 为根的子树，最小的深度满足有 $k$ 个点。用长剖或其他数据结构快速维护。

而在环上时，把树上的人按照时间依次加入，维护和环上的哪个人一起走。

然后求出环上的每个人哪一时刻满足一起走的人大于等于 $k$ ，最后扫一遍更新环上答案，由于每个点只会被更新一次，所以总时间复杂度可以做到 $\mathcal O(n)$ 。

#include <bits/stdc++.h>
using namespace std;
#define N 1000010
const int INF = 0x3f3f3f3f;
int n, K;
int A[N], mxDep[N], son[N], ans[N], stk[N], lsum[N], pos[N];
bool inLoop[N], vis[N];
int *sum[N], pool[N], tot;
vector<int> G[N], loop;
vector<pair<int, int>> tim[N];
void dfsPre(int x) {
    vis[x] = 1;
    mxDep[x] = 1;
    for (int to : G[x]) {
        if (inLoop[to]) {
            continue;
        }
        dfsPre(to);
        if (mxDep[to] + 1 > mxDep[x]) {
            mxDep[x] = mxDep[to] + 1;
            son[x] = to;
        }
    }
}
void newArray(int x) {
    sum[x] = pool + tot;
    tot += mxDep[x];
}
void dfsCal(int x) {
    sum[x][0] = 1;
    if (son[x]) {
        sum[son[x]] = sum[x] + 1;
        dfsCal(son[x]);
        ans[x] = min(ans[x], ans[son[x]] + 1);
    }
    for (int to : G[x]) {
        if (inLoop[to] || son[x] == to) {
            continue;
        }
        newArray(to);
        dfsCal(to);
        ans[x] = min(ans[x], ans[to] + 1);
        for (int j = 0; j < mxDep[to]; j++) {
            sum[x][j + 1] += sum[to][j];
            if (sum[x][j + 1] >= K) {
                ans[x] = min(ans[x], j + 1);
            }
        }
    }
}
void work(int p) {
    int top = 0, x = p;
    do {
        stk[++top] = x;
        vis[x] = 1;
        x = A[x];
    } while (!vis[x]);
    loop.clear();
    p = x;
    do {
        x = stk[top--];
        inLoop[x] = 1;
        loop.push_back(x);
        pos[x] = (int)loop.size() - 1;
    } while (x != p);

    int m = (int)loop.size(), h = 0;
    for (int x : loop) {
        dfsPre(x);
        newArray(x);
        dfsCal(x);
        h = max(h, mxDep[x]);
    }
    for (int i = 0; i < h; i++) {
        tim[i].clear();
    }
    for (int i = 0; i < m; i++) {
        int x = loop[i];
        for (int j = 0; j < mxDep[x]; j++) {
            tim[j].push_back({ loop[(i + j) % m], sum[x][j] });
        }
        lsum[x] = 0;
    }
    for (int i = 0; i < h; i++) {
        for (auto [x, y] : tim[i]) {
            lsum[x] += y;
            if (lsum[x] >= K) {
                int t = loop[((pos[x] - i) % m + m) % m];
                ans[t] = min(ans[t], i);
            }
        }
    }
    for (int i = m * 2 - 1; i > 0; i--) {
        int x = loop[i % m], y = loop[(i + m - 1) % m];
        ans[y] = min(ans[y], ans[x] + 1);
    }
}
int main() {
    scanf("%d%d", &n, &K);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        G[A[i]].push_back(i);
        ans[i] = INF;
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            work(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == INF) {
            ans[i] = -1;
        }
        printf("%d%c", ans[i], " \n"[i == n]);
    }
    return 0;
}

C

建立 SAM ,考虑在后缀树上一条从根到表示字符串前缀 $s [1, i]$ 节点的链路径，然后数编号为 $l\sim r$ 的链并节点和。

树链剖分，等价于对 log 个区间进行颜色段覆盖。颜色段数量是 $n+q\log n$ 级别，暴力 set 维护一下即可。但是常数极大。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, s, t) for (int i = (s), _t = (t); i <= _t; ++i)
typedef long long ll;
const int N = 1e6 + 50;

int val[N];
ll sum[N];
void upd(int x, int v) {
    for (; x < N; x += x & -x) sum[x] += v;
}
void modify(int x, int v) {
    upd(x, v - val[x]);
    val[x] = v;
}
ll qry(int x) {
    ll s = 0;
    for (; x; x ^= x & -x) s += sum[x];
    return s;
}
ll qry(int l, int r) { return qry(r) - qry(l - 1); }

int ch[N][27], Len[N], par[N];
int End = 1, tot = 1;
int Id[N], pos[N];
void Extend(int c) {
    int p = End;
    End = ++tot;
    Len[End] = Len[p] + 1;
    Id[End] = Len[End];
    pos[Len[End]] = End;
    for (; p && !ch[p][c]; p = par[p]) ch[p][c] = End;
    if (!p)
        par[End] = 1;
    else {
        int x = ch[p][c];
        if (Len[p] + 1 == Len[x])
            par[End] = x;
        else {
            int y = ++tot;
            Len[y] = Len[p] + 1;
            memcpy(ch[y], ch[x], sizeof(ch[x]));
            par[y] = par[x];
            par[End] = par[x] = y;
            for (; ch[p][c] == x; p = par[p]) ch[p][c] = y;
        }
    }
}
#define fs(x) (Tr[Fa[x]][1] == x)
int Tr[N][2], Fa[N];
bool is_root(int x) { return Tr[Fa[x]][0] != x && Tr[Fa[x]][1] != x; }
void rotate(int x) {
    int y = Fa[x], f = fs(x);
    if (!is_root(y))
        Tr[Fa[y]][fs(y)] = x;
    Fa[x] = Fa[y];
    Fa[y] = x;
    if (Tr[x][!f])
        Fa[Tr[x][!f]] = y;
    Tr[y][f] = Tr[x][!f];
    Tr[x][!f] = y;
}
void Splay(int x) {
    for (int y; !is_root(x); rotate(x)) {
        if (!is_root(y = Fa[x]))
            rotate(fs(x) == fs(y) ? y : x);
    }
}
void Access(int x) {
    int px = x;
    for (int pre = 0; x; pre = x, x = Fa[x]) {
        Splay(x);
        int p = x;
        while (Tr[p][1]) p = Tr[p][1];
        if (Id[p])
            modify(Id[p], Len[p] - Len[x]);
        Tr[x][1] = pre;
    }
    modify(Id[px], Len[px]);
}
char str[N];
vector<pair<int, int>> Q[N];
ll ans[N];
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    scanf("%s", str + 1);
    FOR(i, 1, q) {
        int l, r;
        scanf("%d%d", &l, &r);
        Q[r].push_back({ l, i });
    }
    FOR(i, 1, n) Extend(str[i] - 'a');
    FOR(i, 2, tot) { Fa[i] = par[i]; }
    FOR(i, 1, n) {
        Access(pos[i]);
        for (auto X : Q[i]) ans[X.second] = qry(X.first, i);
    }
    FOR(i, 1, q) printf("%lld\n", ans[i]);
    return 0;
}

D

把所有点按照和 $1$ 的方位分成 $A B$ 两类。

然后把 $A$ 类点按照中心对称和 $B$ 类进行比较。

$A_{i}$ 在 $B_{i}$ 的东/西边等价 $A_{i}^{'}$ 在 $B_{i}$ 的前/后边。

直接单次 $\mathcal O(n^2)$ 做一遍 $\rm dp$ 就能通过。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e2 + 9;
const int Mod = 998244353;
int T, n;
int dp[N][N], E[N], W[N];
char S[N][N];
int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        bool flag = 1;
        for (int i = 1; i <= n; ++i) scanf("%s", S[i] + 1);
        for (int i = 1; i <= n; ++i) {
            int w = 0, e = n + 1;
            for (int j = i + 1; j <= n; ++j) {
                if (S[i][j] == 'W' || S[j][i] == 'E')
                    w = max(w, j);
                if (S[i][j] == 'E' || S[j][i] == 'W')
                    e = min(e, j);
            }
            E[i] = e;
            W[i] = max(w, i);
            if (w > e)
                flag = 0;
            if (W[i - 1] >= E[i])
                flag = 0;
        }
        if (flag == 0) {
            printf("0\n");
            continue;
        }
        flag = 1;
        int ans = 0ll;
        int L = n;
        for (; E[L] == n + 1; --L)
            ;
        for (int i = E[1]; i > max(W[1], L); --i) {
            for (int k = 1; k < i; ++k) dp[1][k] = 0;
            for (int k = i; k <= n + 1; ++k) dp[1][k] = 1;
            for (int k = 2; k < i; ++k) {
                for (int j = k + 1; j <= W[k]; ++j) dp[k][j] = 0;
                for (int j = W[k] + 1; j <= E[k]; ++j) dp[k][j] = (dp[k - 1][j] + dp[k][j - 1]) % Mod;
                for (int j = E[k] + 1; j <= n + 1; ++j) dp[k][j] = dp[k][j - 1];
            }
            ans = (ans + dp[i - 1][n + 1]) % Mod;
        }
        printf("%d\n", ans);
    }
    return 0;
}

E

当已经有 $n - p$ 个人复读时，若再来一个复读的人，那么剩下的人不可能受到惩罚，将会全部复读。所以这个复读的人不仅得不到冰红茶，还得 $- 154$ 瓶冰红茶。所以后面不会有人复读。

那么当有 $n - 2 p$ 个人复读时，一旦来一个复读的人，接下来 $p - 1$ 个人也会加入复读，就变成了 $n - p$ 的问题，那么之前复读的那个人就会被禁言，所以 $n - 2 p$ 后，没人会复读。

所以只有前 $n\ \text{mod}\ p$ 个人会复读，直接扫一遍即可。

#include<bits/stdc++.h>
using namespace std;
int n,p,t,x;
int main()
{
	cin>>n>>p;
	t=n%p;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	{
		cin>>x;
		if(i==j)
		{
			if(i<=t) cout<<x<<" ";
			else cout<<"0 ";
		} 
	}
}

F

考虑序列上的问题，势能线段树维护区间血量最小值。每次攻击相当于区间减。然后每次操作完后按照区间最小值是否大于 $0$ ，暴力递归到叶子节点删除。而叶子节点可以放一个优先队列或者 set。

而在二维上的问题，考虑一个经典的 trick：假设怪兽血量为 $H$ ，那么在维护 $x$ 坐标和 $y$ 坐标的线段树上分别放血量为 $\lfloor\frac{H}{2}\rfloor$ 的怪兽。当两个怪兽都没死的时候，原本的怪兽肯定也没死。

而当每次死了其中一个的时候，怪兽的血量至少会减半。这时重新在两颗线段树上更改血量。

时间复杂度是两只 log。

#include <bits/stdc++.h>
const int N = 2e5 + 9;
using namespace std;
struct Seg {
    set<pair<int, int> > st[N];
    pair<int, int> sum[N << 2];
    int tag[N << 2];
    int val[N];

#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)

    inline void up(int x) { sum[x] = min(sum[ls(x)], sum[rs(x)]); }

    inline void add(int x, int y) {
        sum[x].first += y;
        tag[x] += y;
    }

    inline void down(int x) {
        if (!tag[x])
            return;
        add(ls(x), tag[x]), add(rs(x), tag[x]);
        tag[x] = 0;
    }

    inline void modify(int x, int l) {
        if (st[l].empty())
            sum[x] = { (int)1e9, 0 };
        else
            sum[x] = { st[l].begin()->first + tag[x], st[l].begin()->second };
    }

    int del(int x, int l, int r, int pos, int d) {
        if (l == r) {
            st[l].erase({ val[d], d });
            modify(x, l);
            return val[d] + tag[x];
        }
        down(x);
        int mid = l + r >> 1, ans;
        if (mid >= pos)
            ans = del(ls(x), l, mid, pos, d);
        else
            ans = del(rs(x), mid + 1, r, pos, d);
        up(x);
        return ans;
    }

    void modify(int x, int l, int r, int pos, pair<int, int> d) {
        if (l == r) {
            d.first -= tag[x];
            val[d.second] = d.first;
            st[l].insert(d);
            modify(x, l);
            return;
        }
        down(x);
        int mid = l + r >> 1;
        if (mid >= pos)
            modify(ls(x), l, mid, pos, d);
        else
            modify(rs(x), mid + 1, r, pos, d);
        up(x);
    }

    void modify(int x, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            add(x, -1);
            return;
        }
        int mid = l + r >> 1;
        down(x);
        if (mid >= ll)
            modify(ls(x), l, mid, ll, rr);
        if (mid < rr)
            modify(rs(x), mid + 1, r, ll, rr);
        up(x);
    }

    void build(int x, int l, int r) {
        sum[x] = { (int)1e9, 0 };
        if (l == r)
            return;
        int mid = l + r >> 1;
        build(ls(x), l, mid), build(rs(x), mid + 1, r);
    }
} t[2];

int n, m, p, q;
int x[N], y[N], h[N], v[N];

inline void add(int i) {
    t[0].modify(1, 0, p - 1, x[i], { (h[i] + 1) / 2, i });
    t[1].modify(1, 0, q - 1, y[i], { (h[i] + 1) / 2, i });
}

int main() {
    scanf("%d%d%d%d", &n, &m, &p, &q);
    t[0].build(1, 0, p - 1), t[1].build(1, 0, q - 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d%d", &x[i], &y[i], &h[i], &v[i]);
        add(i);
    }
    int ans = 0;
    while (m--) {
        int opt;
        scanf("%d", &opt);
        if (opt == 1) {
            int l, r;
            scanf("%d%d", &l, &r);
            l = (l + ans) % p, r = (r + ans) % p;
            if (l > r)
                swap(l, r);
            t[0].modify(1, 0, p - 1, l, r);
            while (t[0].sum[1].first == 0) {
                int i = t[0].sum[1].second;
                h[i] -=
                    ((h[i] + 1) / 2) * 2 - t[0].del(1, 0, p - 1, x[i], i) - t[1].del(1, 0, q - 1, y[i], i);
                if (h[i] == 0)
                    ans += v[i];
                else
                    add(i);
            }
        } else if (opt == 2) {
            int l, r;
            scanf("%d%d", &l, &r);
            l = (l + ans) % q, r = (r + ans) % q;
            if (l > r)
                swap(l, r);
            t[1].modify(1, 0, q - 1, l, r);
            while (t[1].sum[1].first == 0) {
                int i = t[1].sum[1].second;
                h[i] -=
                    ((h[i] + 1) / 2) * 2 - t[0].del(1, 0, p - 1, x[i], i) - t[1].del(1, 0, q - 1, y[i], i);
                if (h[i] == 0)
                    ans += v[i];
                else
                    add(i);
            }
        } else {
            n++;
            scanf("%d%d%d%d", &x[n], &y[n], &h[n], &v[n]);
            add(n);
        }
        printf("%d\n", ans);
    }
}

G

如果给定没有 ? 的字符串判断是否合法，那么只需要所有前缀都满足 $cnt_r\geq cnt_e\geq cnt_d$ 。

由于中间的 $e$ 被两个条件约束着，我们考虑在两边的 $r$ 和 $d$ 。需要前缀的每个 $d$ 前面至少有一个 $e$ 。需要前缀的每个 $e$ 前面至少有一个 $r$ 。而后者等价于需要后缀的每个 $r$ 后面至少有一个 $e$ ，于是可以考虑对于前后缀分别贪心一次。

这里以前缀作例，当 $c n t_{d}$ 大于 $c n t_{e}$ 时，找到最靠后的 ? ，将其变成 $e$ ，而靠后放也是满足 $r$ 的贪心要求的。

最后还未填的 red 按 ? 顺序填。然后再扫一遍 check 一次。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, T, p[N];
string s;
void solve() {
    cin >> s;
    int len = s.length();
    s = " " + s;
    int tim = 0, p1 = 0, p2 = 0;
    for (int i = 1; i <= len; i++) {
        if (s[i] == 'e')
            p1++;
        if (s[i] == 'd')
            p2++;
        if (s[i] == '?')
            p[++tim] = i;
        if (p2 > p1) {
            if (tim) {
                s[p[tim--]] = 'e';
                ++p1;
            } else {
                puts("No");
                return;
            }
        }
    }
    p1 = 0, p2 = 0, tim = 0;
    for (int i = len; i >= 1; i--) {
        if (s[i] == 'e')
            p1++;
        if (s[i] == 'r')
            p2++;
        if (s[i] == '?')
            p[++tim] = i;
        if (p2 > p1) {
            if (tim) {
                s[p[tim--]] = 'e';
                ++p1;
            } else {
                puts("No");
                return;
            }
        }
    }
    int p3 = 0;
    p1 = p2 = 0;
    for (int i = 1; i <= len; i++) {
        if (s[i] == 'r')
            p1++;
        if (s[i] == 'e')
            p2++;
        if (s[i] == 'd')
            p3++;
    }
    for (int i = 1; i <= len; i++) {
        if (s[i] == '?') {
            if (p1 * 3 < len)
                s[i] = 'r', p1++;
            else if (p2 * 3 < len)
                s[i] = 'e', p2++;
            else if (p3 * 3 < len)
                s[i] = 'd', p3++;
        }
    }
    p1 = p2 = p3 = 0;
    for (int i = 1; i <= len; i++) {
        if (s[i] == 'r')
            p1++;
        if (s[i] == 'e')
            p2++;
        if (s[i] == 'd')
            p3++;
        if (p1 < p2 || p2 < p3) {
            puts("No");
            return;
        }
    }
    if (p1 != p2 || p2 != p3) {
        puts("No");
        return;
    }
    puts("Yes");
}
int main() {
    cin >> T;
    while (T--) solve();
}

H

末尾 $0$ 的个数等价于能分解出多少个 $10$ 作为因子，等价于分解出的 $2$ 和 $5$ 的个数最小值。

那么对于 $2$ 和 $5$ 分别做一遍。

考虑枚举点 $x$ 为 lca，那么给子树内每个点贡献 $cnt_x\times sz_x$ 。同时由于在同一个子树内的会算重，枚举儿子 $y$ ，对儿子的子树每个点贡献 $-cnt_x\times sz_y$ 。

#include <bits/stdc++.h>
using namespace std;
vector<int> num[100010];
int siz[100010];
int ans1[100010], ans2[100010];
void dfs1(int x, int fa) {
    siz[x] = 1;
    for (auto i : num[x])
        if (i != fa)
            dfs1(i, x), siz[x] += siz[i];
}
void dfs(int x, int fa) {
    int a = 0, b = 0, ss = x;
    ans1[x] += ans1[fa];
    ans2[x] += ans2[fa];
    while (ss && ss % 5 == 0) a++, ss /= 5;
    while (ss && ss % 2 == 0) b++, ss /= 2;
    for (auto i : num[x])
        if (i != fa) {
            ans1[i] += a * (siz[x] - siz[i]);
            ans2[i] += b * (siz[x] - siz[i]);
            dfs(i, x);
        }
    ans1[x] += a * siz[x];
    ans2[x] += b * siz[x];
}
int main() {
    int n, t;
    scanf("%d%d", &n, &t);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        num[x].push_back(y);
        num[y].push_back(x);
    }
    dfs1(1, 0);
    dfs(1, 0);
    while (t--) {
        int x;
        scanf("%d", &x);
        printf("%d\n", min(ans1[x], ans2[x]));
    }
}

J

差分后发现原本的操作变成如下操作：

把 $(2, 1)$ 变成 $(0, 0)$
把 $(1, 1)$ 变成 $(2, 0)$
把 $(0, 1)$ 变成 $(1, 0)$

操作三相当于随意移动 $1$ 的位置

那么 $2$ 只能由 $1$ 消掉，所以 $1$ 的个数不少于 $2$ 的个数。

当只剩 $1$ 和 $0$ 的时候，由于环形数组差分总和是 $0(\rm mod\ 3)$ ，而三个 $1$ 一定能消掉。

综上，只要 $1$ 的个数不少于 $2$ 的个数即可。

#include <bits/stdc++.h>
using namespace std;
long long t, i, n, j, a[1000001], temp;
int main() {
    scanf("%lld", &t);
    for (i = 1; i <= t; i++) {
        scanf("%lld", &n);
        for (j = 0; j < n; j++) scanf("%lld", &a[j]);
        temp = 0;
        for (j = 0; j < n; j++)
            if (a[j] < a[(j + 1) % n])
                temp++;
            else if (a[j] > a[(j + 1) % n])
                temp--;
        puts(temp < 0 ? "No" : "Yes");
    }
}

K

一个 $1$ 能给某一行或者某一列加上 $1$ 。在一个点可以被重复放的情况下，列和行的贡献是独立的，所以分开考虑。

当分配行的时候，每行至少有一个 $1$ ，且在此基础上想越均匀越好，那么就会出现若干个 $2 x + 1$ 和 $2 x - 1$ 的分配方式。

而最后只需要枚举每一行选一些列来匹配即可。每次贪心选最大的。

最后特例是 $k = n m - 2$ 且 $n, m$ 都是奇数时无解。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
int a[N], b[N];
void init(int len, int arr[], int sum) {
    for (int i = 1; i <= len; i++) sum--, arr[i] = 1;
    while (sum) {
        for (int i = 1; i <= len; i++) {
            if (!sum)
                break;
            arr[i] += 2, sum -= 2;
        }
    }
}
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    if ((n & 1) != (k & 1) || (m & 1) != (k & 1) || (n & 1) != (m & 1) || k < max(m, n)) {
        cout << "NO\n";
        return;
    }
    init(n, a, k);
    init(m, b, k);
    priority_queue<pair<int, int>> q;
    for (int i = 1; i <= m; i++) q.push({ b[i], i });
    vector<pair<int, int>> v;
    vector<pair<int, int>> ans;
    for (int i = 1; i <= n; i++) {
        v.clear();
        while (a[i]) {
            a[i]--;
            if (q.empty()) {
                cout << "NO\n";
                return;
            }
            int x,pos;x=q.top().first;pos=q.top().second;
            q.pop();
            x--;
            ans.push_back({ i, pos });
            if (x)
                v.push_back({ x, pos });
        }
        for (auto t : v) q.push(t);
    }
    cout << "YES\n";
    for (auto X : ans) cout << X.first << ' ' << X.second << '\n';
}
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

L

设 $f_{i}$ 表示 $\rm mex$ 恰好为 $i$ 的方案数，设 $g_{i}$ 表示 $\rm mex$ 至少为 $i$ 的方案数。

ans=\sum_{i=0}^{+\infty} if_i=\sum_{i=1}^{\infty} i(g_i-g_{i+1})=\sum_{i=1}^{+\infty}g_i

而计算 $g_{i}$ 只需要数字 $0\sim i-1$ 都出现过即可。

当枚举数字 $i$ 在区间内出现了 $b_{i}$ 次，则合法总方案数为：

\binom{\sum_{i=0}^n b_i}{b_0...b_n}\binom{n-\sum_{i=0}^n b_i}{a_0-b_0...a_n-b_n}\Bigg(n-(\sum_{i=0}^n b_i)+1\Bigg)

三个分别是区间内的方案数，区间外的方案数和插入区间的方案数。

设 $F_{i} (x)$ 表示选择数字 $i$ 的 EGF， $G_{i} (x)$ 表示至少选择一个数字 $i$ 的 EGF。

F_i(x)=\sum_{j=0}^{a_i}\frac{x^j}{j!(a_i-j)!}\\ G_i(x)=F_i(x)-\frac{1}{a_i!}

那么最终答案就变成：

\sum_{l=0}^n(n-l+1)!\times l!\times \Bigg([x^l]\sum_{i=0}^{n-1}\prod_{j=0}^iG_j(x)\prod_{j=i+1}^nF_j(x)\Bigg)

考虑分治 $\rm NTT$ ，设 $A$ 为 $\prod_{i=l}^r G_i(x)$ ， $B$ 为 $\prod_{i=l}^r F_i(x)$ ， $C$ 为 $\sum_{i=l}^r\prod_{j=l}^iG_j(x)\prod_{j=i+1}^rF_j(x)$ 。

A=A_l\times A_r\\ B=B_l\times B_r\\ C=A_lC_r+C_lB_r

时间复杂度 $\mathcal O(n\log^2 n)$ 。

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; ++i)
#define repd(i, x, y) for (int i = x; i >= y; --i)
#define pb push_back
#define mid ((l + r) >> 1)

using namespace std;
const int N = 100005, mod = 998244353;
typedef long long LL;
typedef vector<LL> vll;
int n, a[N], len, bin[N << 2];
LL flv[N], inv[N], A[N << 2], B[N << 2], ans;
vll L[N], R[N], M[N];

int getint() {
    char ch;
    while (!isdigit(ch = getchar()))
        ;
    int x = ch - 48;
    while (isdigit(ch = getchar())) x = x * 10 + ch - 48;
    return x;
}

LL getmi(LL a, LL x) {
    LL rt = 1;
    while (x) {
        if (x & 1)
            rt = rt * a % mod;
        a = a * a % mod, x >>= 1;
    }
    return rt;
}

void FFT(LL a[], int len, int tp) {
    rep(i, 0, len - 1) bin[i] = bin[i >> 1] >> 1 | ((i & 1) * (len >> 1));
    rep(i, 0, len - 1) if (i < bin[i]) swap(a[i], a[bin[i]]);
    for (int i = 1; i < len; i <<= 1) {
        LL wn = getmi(3, (mod - 1) / (i << 1));
        if (tp == -1)
            wn = getmi(wn, mod - 2);
        for (int j = 0; j < len; j += i << 1) {
            LL w = 1, x, y;
            rep(k, 0, i - 1) {
                x = a[j + k], y = a[i + j + k] * w % mod, w = w * wn % mod;
                a[j + k] = (x + y) % mod, a[i + j + k] = (x - y + mod) % mod;
            }
        }
    }
    if (tp == -1) {
        LL x = getmi(len, mod - 2);
        rep(i, 0, len - 1) a[i] = a[i] * x % mod;
    }
}

vll operator+(vll a, vll b) {
    vll c(max(a.size(), b.size()));
    int sz = a.size();
    rep(i, 0, sz - 1) c[i] = (c[i] + a[i]) % mod;
    sz = b.size();
    rep(i, 0, sz - 1) c[i] = (c[i] + b[i]) % mod;
    return c;
}

vll operator*(vll a, vll b) {
    int sza = a.size();
    int szb = b.size();
    for (len = 1; len <= sza + szb - 2; len <<= 1)
        ;
    rep(i, 0, len - 1) A[i] = B[i] = 0;
    rep(i, 0, sza - 1) A[i] = a[i];
    rep(i, 0, szb - 1) B[i] = b[i];
    FFT(A, len, 1), FFT(B, len, 1);
    rep(i, 0, len - 1) A[i] = A[i] * B[i] % mod;
    FFT(A, len, -1);
    vll c;
    rep(i, 0, sza + szb - 2) c.pb(A[i]);
    return c;
}

void solve(int l, int r) {
    if (l == r) {
        L[l].pb(0);
        rep(i, 1, a[l]) L[l].pb(inv[i] * inv[a[l] - i] % mod);
        rep(i, 0, a[l]) R[l].pb(inv[i] * inv[a[l] - i] % mod);
        M[l].pb(inv[a[l]] * l % mod);
        return;
    }
    solve(l, mid);
    solve(mid + 1, r);
    M[l] = L[l] * M[mid + 1] + R[mid + 1] * M[l];
    L[l] = L[l] * L[mid + 1];
    R[l] = R[l] * R[mid + 1];
}

int main() {
    n = getint();
    rep(i, 0, n) a[i] = getint();
    flv[0] = 1;
    rep(i, 1, n) flv[i] = flv[i - 1] * i % mod;
    inv[n] = getmi(flv[n], mod - 2);
    repd(i, n, 1) inv[i - 1] = inv[i] * i % mod;
    solve(0, n + 1);
    int sz = M[0].size();
    rep(i, 0, sz - 1) {
        LL x = M[0][i];
        ans = (ans + x * (n - i + 1) % mod * flv[i] % mod * flv[n - i]) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

M

按照题意模拟。

#include <bits/stdc++.h>
int v[6][6] = { { 10, 10, 8, 5, 0 },
                { 20, 20, 16, 10, 0 },
                { 30, 30, 24, 15, 0 },
                { 50, 50, 25, 20, 0 },
                { 10, 5, 4, 3, 0 } },
    a[6], A, B, A0, B0;
int main() {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 5; ++j) scanf("%d", a + j);
        for (int j = 0; j < 5; ++j) A += a[j] * v[i][0], A0 += a[j] * v[i][j];
    }
    for (int j = 0; j < 5; ++j) B += a[j] * v[4][0], B0 += a[j] * v[4][j];
    printf("%.9lf", A0 * 100.0 / A + B0 * 1.0 / B);

    return 0;
}