The Solution of HEUCPC2021

Nanarikom

General

预计难度

  • Easy --- NIB
  • Easy-Mid --- EJF
  • Mid --- DC
  • Mid-Hard --- HAG
  • Hard --- KL << M

实际难度

image-20210426212500430

  • Easy --- NIB
  • Easy-Mid --- JF
  • Mid --- CEAD
  • Mid-Hard --- HL
  • Hard --- GKM

预料之外的地方主要是 E 居然这么多人没看出来；A 居然这么简单；G 和 L 难度和预计的相反。

Problem N. anikore

Idea

判断 是否为质数。

Source & Random Fact

本来是没有这个题的，但某几位没有参与出题工作的人在出题差不多结束的时候过来大致了解了一下都有什么题目。他们觉得整体难度太高了，强行加上了这个题，目标是“一定要所有人都过”。从结果来看并没有完成它的任务（有人 4tries 没过），而且并没有增加任何区分度（N: 71/111; I: 68/94），实属本场比赛的一大败笔。

Solution

注意到 ，所以 是合数。这可能是本题最自然的非暴力做法。

当然，手算验证一下 / 写个程序跑一跑也都是可以的。实在不行 Yes 和 No 都输出一遍，总有一个是对的。4tries 没过确实是有点虚无。

Code (by Nanarikom)

#include <iostream>
using namespace std;

int main () {
    puts("No");
}

Problem I. cy Resurrection

Idea

边长为 的正三角形网格用边长为 的菱形填充，最少会空出多少格子。

Source & Random Fact

出题工作快结束的时候，被批判了签到题 B 不够签到，于是我加上了这个题。

Solution

在纸上画一画，结合样例，很容易猜到答案等于 。我们来证明一下这件事情。

首先我们来证明答案可以等于 。我们把所有菱形都竖着放，显然只有最后一行的 个格子被空出来。

接下来我们证明答案不可能比 更小。一个菱形不管怎么旋转，放进网格中总是占用一个尖角朝上的格子和一个尖角朝下的格子。注意到尖角朝上的格子比尖角朝下的格子多 个，所以至少有 个尖角朝上的格子被空出来。

Code (by Nanarikom)

#include <iostream>
using namespace std;

int main () {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", n);
    }
}

Problem B. lazing Riff

Idea

求最短的非回文的子串的长度。

Source & Random Fact

我在知乎上看到有人问最长的非回文的子串的长度。这看上去确实是一个很合适的签到题，但由于不想出一模一样的原题，所以又简化成问最短的。

Solution

显然，所有字符都相同时，不存在非回文的子串；否则总是存在一个长度为 的子串。

Code (by Nanarikom)

#include <iostream>
#include <string>
using namespace std;

int main () {
    string s;
    cin >> s;

    int allsame = 1;
    for (char c : s) {
        if (c != s[0]) allsame = 0;
    }

    cout << (allsame ? -1 : 2) << endl;
}

Problem J. uvenile Galant

Idea

询问将两种给定形状拼接成一个指定长度的直角梯形的方案数。

Source & Random Fact

原版本来自于 Biubiubiu，是未举办的 HEUCPC2020 中的题——用底和高均为 的平行四边形、两边长均为 的直角三角形拼成 的长方形有多少种方案。

为了不显得过于无聊，我把它改成了平行四边形底为 （要求讨论奇偶性），并且要求最后留出一个尖的版本（也正好切合背景）。

Solution

这题是一个入门级的 DP。具体实现方法有很多，我们讲一个最入门的。

令 分别表示长边长度为 时，右端是平的 / 右端尖角朝上 / 右端尖角朝下的方案数，则有：
$dp_{0, 0} = 1$，然后一直往后算就行了。

Code (by Nanarikom)

// 下面的代码不是上述做法

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 5;
const int mod = 998244353;

int pre[N];
int dp[N];

int main () {
    int n;
    scanf("%d", &n);
    dp[0] = 1, pre[0] = 1;
    dp[1] = 0, pre[1] = 0;
    dp[2] = 0, pre[2] = 1;
    for (int i = 3;i <= n;++i) {
        dp[i] = 2 * pre[i - 3] % mod;
        pre[i] = (pre[i - 2] + dp[i]) % mod;
    }
    printf("%d\n", pre[n - 2]);
}

Problem F. leeing Sunlight

Idea

给定长度为 的序列 ，找出最小的 使得 。

Source & Random Fact

这个题的初始版本来自于 Xiuchen，HP 取 的概率是 ，取 的概率是 。我觉得不够自然，就改成了 HP 取值连续的版本。

很显然，如果你会二分答案，这就是一个裸题（裸到部分验题人强烈反对这个题的存在）。但有的好哥哥把 eps 开得超大，然后 TLE 了，导致这个题非常 dirty。我们都加粗说了精度 了，这个不能怪我们吧……

下面我们介绍一下什么是二分答案。

Solution

我们先给答案假设一个特别宽松的界，比如下界 ，上界 ，显然答案是属于 的。现在我们令 ，并假设 就是最终答案，将 代入 。考虑到这个式子关于 是单调的，那么，如果这个式子的结果大于 ，就说明最终答案小于 ，我们需要在 内继续寻找更精确的答案；如果这个式子的结果小于 ，就说明最终答案大于 ，我们需要在 内继续寻找更精确的答案。容易发现，两种情况中的任意一种都是原问题的一个子问题，我们不断使用以上方法就能不断把答案确定在更小的区间内，直到 时为止。

由于每次区间的长度缩小一半，容易看出该算法的时间复杂度是 的。

Code (by Nanarikom)

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

const int N = 1e5 + 5;
const double eps = 1e-6;

double l0[N], r0[N];

int main () {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;++i) {
        scanf("%lf%lf", &l0[i], &r0[i]);
    }

    double l = 0, r = 1e9;
    while (fabs(r - l) > eps) {
        double mid = (l + r) / 2;
        double exp = 0;
        for (int i = 1;i <= n;++i) {
            if (mid > r0[i]) exp += 1;
            else if (mid > l0[i]) exp += (mid - l0[i]) / (r0[i] - l0[i]);
        }
        //cout << l << ' ' << r << ' ' << mid << ':' << exp << endl;
        if (exp < m) l = mid;
        else r = mid;
    }
    printf("%.10lf\n", l);
}

Problem C. hivalric Blossom

Idea

有 个任务，你需要给每个任务指定一个优先级，之后你会按优先级递增的顺序完成这些任务。如果有两个任务优先级相同，你会先完成编号小的。现在有 对任务必须连续完成，你的目标是在满足这些限制的情况下，让不同优先级的数量尽可能少。

Source & Random Fact

这是我一年前产生了出一场 CF 的想法的时候造的一个题，但并没有出 CF 于是这个题就保留下来了。这个 idea 来自于一个游戏，具体是啥我就不说了（因为很无聊）。

Solution

做法有很多，我们来讲一个线性的贪心。

很显然所有的限制关系形成了若干条链，我们预处理链上每个点的前驱后继。显然，链上的端点颜色必须相同，被链框住的点必须和链颜色不同。先把 种颜色扔到一个表示可用的颜色的栈里，然后从左往右给每个点分配颜色。遇到一个链头，我们从栈里取出一个颜色分配给他；遇到一个链的中间结点，我们给他跟链头一样的颜色；遇到一个链尾，我们给他跟链头一个的颜色，并将这个颜色释放回栈里。这个贪心的正确性显然，时间复杂度 。

如果你用优先队列或者 set 替代栈，时间复杂度是 ，也可以通过本题。

Code (by Nanarikom)

#include <iostream>
#include <stack>
using namespace std;

const int N = 1e5 + 5;

int col[N];
int l[N], r[N];

int main () {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n;++i) {
        l[i] = r[i] = 0;
    }
    for (int i = 1;i <= m;++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        l[b] = a;
        r[a] = b;
    }

    stack <int> s;
    for (int i = n;i >= 1;--i) {
        s.push(i);
    }
    for (int i = 1;i <= n;++i) {
        if (l[i]) {
            col[i] = col[l[i]];
            if (!r[i]) s.push(col[i]);
        } else {
            col[i] = s.top();
            if (r[i]) s.pop();
        }
    }

    for (int i = 1;i <= n;++i) {
        printf("%d ", col[i]);
    }
    puts("");
}

Problem E. clipsing Star

Idea

轮游戏，每轮有 块钱。在一轮中，先手可以自己拿 块钱，给后手 块钱，然后交换先后手的概率为 。问最优策略下先手方与后手方总钱数之差的期望。

Source && Random Fact

是很久之前 Luowaterbi 问我的一个问题，我惊讶于他不会。出题的时候想起来，于是我扔过来了。

当时我以为这个题的简单程度仅次于前三个签到题，没想到这么多人没看出来。

Solution

注意到第 轮的先手方必定拿 全部，那么考虑第 轮的先手方如何操作。观察第 轮的操作如何影响结果，可以发现，因为一次函数的复合还是一次函数，而一次函数只在两端取最值，所以最优策略下，第 轮的先手方要不然拿 全部，强制交换先后手，让对手拿 全部；要不然放弃 全部，强制保留先手，然后拿 全部。

至此，容易发现我们可以把最后两轮归纳为钱数为 的一轮。我们从后向前一直归纳，只剩一轮时的结果就是答案。时间复杂度 。

为了避免暗示，题目里允许你输出一个实数而非只能输出整数。实际上，根据上面的推理，这题的答案一定是整数。

Code (by Nanarikom)

#include <iostream>
using namespace std;

const int N = 1e6 + 5;

int a[N];

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1;i <= n;++i) {
        scanf("%d", &a[i]);
    }

    int ans = a[n];
    for (int i = n - 1;i >= 1;--i) {
        ans = abs(ans - a[i]);
    }
    printf("%d\n", ans);
}

Problem A. stral Reflection

Idea

在 上支持如下操作。操作一：学习一个新的技能——清除 内所有的陨石。操作二：给定一个点集代表陨石出现在这些位置，询问最少需要使用多少技能才能清除所有陨石（不能使用当前没有学习的技能）。

Source & Random Fact

也来自未举办的 HEUCPC2020。原版本是个签到题，但我读错题了，然后变成了现在这个题目。

Solution

对于每次询问，很容易想到，最左边的陨石反正是一定要清除的，那么清除这个陨石的时候肯定能顺带清除越多别的陨石越好，所以对于每个位置，我们考虑维护能覆盖这个位置的线段中右端点最右的一个。询问的时候我们按以上维护的信息每次贪心地尽可能往右覆盖即可。

考虑如何维护这个信息。最直接的做法是吉司机树，每次学习技能 时，用 更新 内的每个位置能到达的最右位置。

这其实是一个没有必要的做法。再仔细看一眼，我们发现其实只需要在 这个位置填上 ，然后，当你想询问覆盖一个位置的线段中右端点最右的一个，你就直接询问前缀中填的东西的最大值就行了。容易发现，这只需要一个树状数组或者线段树就能实现。时间复杂度 。

实际上这个题 也能过，时限非常宽松。

Code (by Bakapiano)

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

const int MAXN = 1e5+9;
const int inf  = 1e9+7;

int n,m,a[MAXN];
vector<int> ve;
#define mid ((l+r)>>1)
#define ls (cnt<<1)
#define rs (cnt<<1|1)

int mx[MAXN*4];
void update(int l,int r,int pos,int val,int cnt)
{
    if(l==r)return void(mx[cnt]=max(mx[cnt],val));
    if(pos<=mid)update(l,mid,pos,val,ls);
    else update(mid+1,r,pos,val,rs);
    mx[cnt]=max(mx[ls],mx[rs]);
}
int query(int l,int r,int nl,int nr,int cnt)
{
    if(l==nl&&r==nr)return mx[cnt];
    if(nr<=mid)return query(l,mid,nl,nr,ls);
    if(nl> mid)return query(mid+1,r,nl,nr,rs);
    return max(query(l,mid,nl,mid,ls),query(mid+1,r,mid+1,nr,rs));
}
int main(int argc, char* argv[]) 
{
    scanf("%d%d",&n,&m),memset(mx,-1,sizeof(mx));
    while(m--)
    {
        int t,l,r,w;scanf("%d",&t);
        if(t==1)scanf("%d%d%d",&l,&r,&w),update(0,n,l,r,1);
        if(t==2)
        {
            int k,ans=0,pre=-1;scanf("%d",&k),ve.clear();
            for(int i=1,x;i<=k;++i)scanf("%d",&x),ve.push_back(x);
            sort(ve.begin(),ve.end(),greater<int>());
            while(!ve.empty())
            {
                pre=query(0,n,0,ve.back(),1);
                if(pre<ve.back()){ans=-1;break;}
                ++ans;
                while(!ve.empty()&&pre>=ve.back())ve.pop_back();
            }
            printf("%d\n",ans);
        }
    }
    return 0;
}

Problem D. andelion Knight

Idea

给定 01 序列 ，对于 ，询问有多少方案可以在 和 各选择一个前缀，使得两个前缀的长度之和为 且两个前缀的和相等。

Source & Random Fact

这是我一年前产生了出一场 CF 的想法的时候造的一个题，但并没有出 CF 于是这个题就保留下来了。

不知道为什么过的人这么少，难道因为题意有点难懂？

Solution

为了方便，我们把在 中选择长度为 的前缀、在 中选择长度为 的前缀的方案记为方案 。

我们对 求前缀和，并预处理前缀和中每个数 第一次出现的位置 和最后一次出现的位置 。然后对 求前缀和，求出第 个位置的前缀和 之后，很显然，方案 都是合法的。令 表示 的答案，则上面列出的合法方案意味着 都应该加一。

这种区间加操作，可以使用树状数组或线段树在 的时间复杂度内完成。总时间复杂度 。

注意到你只需要最后一起回答所有答案，即询问是静态的，所以区间加可以转化成差分数组上的单点修改，总时间复杂度 。在本题中，时间复杂度为 和 的算法均可通过。

Code (by Nanarikom)

#include <iostream>
#include <cstring>
using namespace std;

const int N = 2e6 + 5;

int a[N], b[N];
int prea[N], preb[N], l[N], r[N];
int ans[N];

int main () {
    int n;
    scanf("%d", &n);
    for (int i = 1;i <= n;++i) {
        scanf("%d", &a[i]);
        prea[i] = prea[i - 1] + a[i];
    }
    for (int i = 1;i <= n;++i) {
        scanf("%d", &b[i]);
        preb[i] = preb[i - 1] + b[i];
    }

    memset(l, -1, sizeof l);
    memset(r, -1, sizeof r);
    for (int i = 0;i <= n;++i) {
        if (l[preb[i]] == -1) l[preb[i]] = i;
        r[preb[i]] = i;
    }
    for (int i = 0;i <= n;++i) {
        if (l[prea[i]] == -1) break;
        int minn = i + l[prea[i]];
        int maxx = i + r[prea[i]];
        //cout << minn << ' ' << maxx << endl;
        ans[minn]++;
        ans[maxx + 1]--;
    }
    for (int i = 0;i <= 2 * n;++i) {
        if (i) ans[i] = ans[i - 1] + ans[i];
        printf("%d ", ans[i]);
    }
    puts("");
}

Problem H. armless Sweetie

Idea

给定一个由 和 组成的序列，每次操作可以将相邻的两个数变为它们的积，并得到与它们的积一样多的分数，直到序列长度为 时停止。求最大可能的总分数。

Source & Random Fact

Bakapiano 出的。题目本身不难，但我们觉得这个题显然会非常 dirty。从结果来看果然是 dirt 率最高的题目(2/43)。

Solution

做法有很多，只要处理清楚细节即可，否则就会一直 dirt。我们讲讲 std 的做法。

首先一次操作最多产生 分数，所以先把相邻连续的 和 消掉显然是不亏的。这样，我们得到了一个 和 交替的序列。区间 DP 对 和 开头的交替序列分别打一个表，发现 的时候可以归纳：序列长度每增加 ，答案增加 。 所以 小的时候直接用 DP 结果回答， 大的时候归纳到 以内。

当然对于 小的情况也找规律也是可行的，但要讨论清楚，小心 corner case。

Code (by Nanarikom)

#include <iostream>
#include <vector>
using namespace std;

const int N = 1e6 + 5;
const int M = 8;
const int INF = 0x3f3f3f3f;

int t[M], pre[M] = {1};
int dp[2][M][M];
void init (int flag) {
    for (int i = 1;i <= 7;++i) {
        t[i] = (i + flag) & 1 ? -1 : 1;
        pre[i] = pre[i - 1] * t[i];
    }
    for (int i = 1;i <= 7;++i) for (int j = 1;j <= 7;++j) dp[flag][i][j] = -INF;
    for (int i = 1;i <= 7;++i) dp[flag][i][i] = 0;
    for (int len = 1;len <= 7;++len) {
        for (int l = 1;l + len - 1 <= 7;++l) {
            int r = l + len - 1;
            for (int i = l;i + 1 <= r;++i) {
                dp[flag][l][r] = max(dp[flag][l][r], dp[flag][l][i] + dp[flag][i + 1][r] + pre[r] * pre[l - 1]);
            }
            //cout << l << ' ' << r << ':' << dp[flag][l][r] << endl;
        }
    }
}

int a[N];

int main () {
    init(0), init(1);

    int T;
    scanf("%d", &T);
    while (T--) {
        int n, allneg = 1;
        scanf("%d", &n);
        for (int i = 1;i <= n;++i) {
            scanf("%d", &a[i]);
            if (a[i] == 1) allneg = 0;
        }
        a[n + 1] = 0;
        if (allneg) if (n > 1) {
            printf("%d\n", n & 1 ? n - 3 : n - 1);
            continue;
        }

        vector <int> v;
        int tmp = 0, headneg = 0, tailneg = 0;
        for (int i = 1;i <= n;++i) {
            if (a[i] == -1) {
                tmp++;
                if (a[i + 1] != -1) {
                    if (tmp & 1) v.push_back(tmp);
                    if (i == tmp) headneg = tmp;
                    if (i == n) tailneg = tmp;
                    tmp = 0;
                }
            }
        }
        int len = v.size() * 2;
        if ((headneg & tailneg) % 2 == 1) len--;
        if ((headneg | tailneg) % 2 == 0) len++;
        int ans = n - len;
        if (len <= 7) {
            ans += dp[headneg % 2 == 0][1][len];
        } else {
            int k = len % 4 + 4;
            ans += dp[headneg % 2 == 0][1][k] + (len - k) / 2;
        }
        //printf("%d\n", len);
        printf("%d\n", ans);
    }
}

Problem L. et the wind tell you

Idea

在无根树上每个结点初始时刻有一个标记，每次操作可以选择一个结点 ，所有和 直接相连的结点上的标记都会被吸到 上。现在需要把所有标记吸到一个结点，问最小化操作次数的方案数。

Source & Random Fact

我原先是想出个签到题，当时只询问了操作次数最少可以是多少，显然除了 的情况之外答案就是 。后来我发现这题改成询问方案数好像挺有趣的，于是有了现在的版本。

Solution

题意等价于，从一个非叶子结点开始，每次选择一个与当前选择过的结点直接相连的非叶子结点，直到没有非叶子结点，问方案数。我们考虑有定根时的方案数。对于一棵子树，子树根显然必须比子树内的其他结点先被选。一棵子树 内部的方案数等于每个儿子 的子树的方案数之积，再乘上每个儿子 的子树对应的操作序列混着插的方案数。接下来我们考虑换根来求不定根时的总方案数。当根从 换向儿子 时，我们维护外子树的方案数即可。两遍 DFS，时间复杂度 。

Code (by Nanarikom)

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;
const int mod = 998244353;

ll qpow (ll n, ll m) {
    ll ret = 1;
    while (m) {
        if (m & 1) ret = ret * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ret;
}
ll getinv (ll a) {
    return qpow(a, mod - 2);
}

ll fac[N] = {1}, inv[N];
void init () {
    for (int i = 1;i < N;++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = getinv(fac[N - 1]);
    for (int i = N - 2;i >= 0;--i) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}

ll cmn (ll m, ll n) {
    if (m < n) return 0;
    ll ret = fac[m];
    ret = ret * inv[n] % mod;
    ret = ret * inv[m - n] % mod;
    return ret;
}

vector <int> e[N];
ll siz[N], dp[N], cnt = 1;
ll ans[N];

void dfs1 (int u, int fa) {
    siz[u] = 1;
    dp[u] = 1;
    for (int v : e[u]) if (v != fa) if (e[v].size() > 1) {
        cnt++;
        dfs1(v, u);
        siz[u] += siz[v];
        dp[u] *= dp[v], dp[u] %= mod;
        dp[u] *= cmn(siz[u] - 1, siz[v]), dp[u] %= mod;
    }
}

void dfs2 (int u, int fa) {
    for (int v : e[u]) if (v != fa) if (e[v].size() > 1) {
        ll uout = ans[u] * getinv(dp[u]) % mod * getinv(cmn(cnt - 1, cnt - siz[u])) % mod;
        ll udelv = dp[u] * getinv(dp[v]) % mod * getinv(cmn(siz[u] - 1, siz[v])) % mod;
        ll vout = uout * udelv % mod * cmn(cnt - siz[v] - 1, cnt - siz[u]) % mod;
        ans[v] = vout * dp[v] % mod * cmn(cnt - 1, cnt - siz[v]) % mod;
        dfs2(v, u);
    }
}

int main () {
    init();

    int n;
    scanf("%d", &n);
    for (int i = 1;i <= n - 1;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    if (n == 2) {
        puts("2");
        return 0;
    }

    int rt = 1;
    while (e[rt].size() == 1) rt++;
    dfs1(rt, -1);
    //cout << rt << ' ' << cnt << endl;for (int i = 1;i <= n;++i) cout << dp[i] << endl;

    ans[rt] = dp[rt];
    dfs2(rt, -1);
    //for (int i = 1;i <= n;++i) cout << i << ':' << ans[i] << endl;

    ll sum = 0;
    for (int i = 1;i <= n;++i) {
        sum += ans[i];
        sum %= mod;
    }
    printf("%lld\n", sum);
}

Problem G. liding Champion

Idea

有根树染成黑白两色，要求每条根到叶子的路径都经过相同数量的黑色结点，问最大化黑色结点的方案数。

Source & Random Fact

我出的。

Solution

首先全局最浅叶子对应的路径上肯定应该全黑。然后对于其他叶子，既然要最大化黑色结点数，那肯定是在越深的地方染黑越好，因为此时可能有更多的分叉。但太深才染黑可能会导致某些叶子对应的路径上黑色结点数不够，所以也要考虑当前子树最浅叶子的深度。综上，在纸上画一画我们可以发现，我们可以通过一个 DFS 染色，DFS 到每个点时，当前点的颜色跟全局最浅叶子、当前子树最浅叶子、当前结点对应的路径上已有黑色结点数三个要素有关。

给出一种染色方案后，我们不难发现，只有分叉点之间的颜色是可以任意重排的，一个叉内的重排的方案数就是一个组合数，而总方案数就是这些组合数之积。

Code (by Nanarikom)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

ll qpow (ll n, ll m) {
    ll ret = 1;
    while (m) {
        if (m & 1) ret = ret * n % mod;
        n = n * n % mod;
        m >>= 1;
    }
    return ret;
}
ll getinv (ll a) {
    return qpow(a, mod - 2);
}

ll fac[N] = {1}, inv[N];
void init () {
    for (int i = 1;i < N;++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[N - 1] = getinv(fac[N - 1]);
    for (int i = N - 2;i >= 0;--i) {
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
}

ll cmn (ll m, ll n) {
    if (m < n) return 0;
    ll ret = fac[m];
    ret = ret * inv[n] % mod;
    ret = ret * inv[m - n] % mod;
    return ret;
}

vector <int> e[N];
int dep[N], mind[N];
int col[N], pre[N];
int lastkey[N];
ll ans = 1;

bool multison (int u) {return ((u == 1) && (e[u].size() >= 2)) || (e[u].size() >= 3);}
bool leave (int u) {return (u != 1) && (e[u].size() == 1);}
bool iskey (int u) {return multison(u) || leave(u);}

void dfs1 (int u, int fa) {
    if (leave(u)) {
        mind[u] = dep[u];
        return;
    }

    for (int v : e[u]) if (v != fa) {
        dep[v] = dep[u] + 1;
        dfs1(v, u);
        mind[u] = min(mind[u], mind[v]);
    }
}

void dfs2 (int u, int fa) {
    if (fa != -1) {
        if (mind[u] - mind[1] > pre[fa]) col[u] = 1;
        pre[u] = pre[fa] + col[u];
        lastkey[u] = lastkey[fa];
    }

    if (iskey(u)) {
        int m = dep[u] - dep[lastkey[u]];
        int n = pre[u] - pre[lastkey[u]];
        ans *= cmn(m, n);
        ans %= mod;
        //cout << u << lastkey[u] << ':' << m << n << endl;
        lastkey[u] = u;
    }

    for (int v : e[u]) if (v != fa) {
        dfs2(v, u);
    }
}

int main () {
    init();

    int n;
    scanf("%d", &n);
    for (int i = 1;i <= n - 1;++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }

    dep[1] = 1;
    memset(mind, INF, sizeof mind);
    dfs1(1, -1);

    lastkey[1] = 1;
    dfs2(1, -1);

    printf("%lld\n", ans);
}

Problem K. ätzlein Cocktail

Idea

对于一个长度为 的排列 ，每次给出其中一项，并询问确定此项后， 期望需要至少多少次交换任意两元素，才会满足 。

Source & Random Fact

最早是我想了一个很 trivial 的问题，经过跟 triple_a@NJU 和 Nezzar@CUHK 的反复讨论之后有了现在的版本。

这个题的代码难度很低，几乎是一个纯数学题，但可能需要相对高一点的群论和组合数学水平。

Solution

如果把排列看作置换，我们发现一个排列 可以被唯一分解成若干不交轮换之积。记排列 的不交轮换数为 ，显然， 当且仅当 。考虑一次交换操作，它的结果会是将一个轮换分解为两个不交轮换、将两个不交轮换合并为一个轮换这两种结果之一，即轮换数在一次操作中不是加一就是减一，所以最快的满足 的方案就是每次让轮换数加一。即，要满足 所需的最小交换次数是 。我们现在要求的就是这个东西的期望。

如果把排列看作置换，我们发现一个排列 可以被唯一分解成若干不交轮换之积。记排列 的不交轮换数为 ，显然，排列 单增当且仅当 。考虑一次交换操作，它的结果会是将一个轮换分为两个不交轮换、将两个不交轮换合并为一个轮换这两种结果之一。那么，自然地，将一个排列 恢复为单增所需的最小交换次数是 。

我们先来介绍一个结论：对于长度为 的随机排列 ， 。一会我们会证明这个调和级数是怎么来的，现在先跳过。至此，我们已经可以很轻松的回答第一次询问了。

但是确定若干元素后又如何呢？假设存在 到 共 个结点，其实每次给定的输入 可以看做是从 结点连一条边连向 结点，而多次操作后图中就会存在链和环，让我们来讨论它们的地位。考虑一个点，它在不成链的情况下可以被别的结点连一次、可以连一次别的结点；考虑一条链，它的一端可以被别的结点连一次、它的另一端可以连一次别的结点、它的中间结点已经无法被其他结点连入或连出了。不难发现，点可以看成退化的链，他们对外的性质是一样的。因此，这个图中对我们计算答案有帮助的事只有两个：已成环的连通块数和不成环的连通块数。已成环的连通块对答案的贡献已固定，不成环的连通块数对应调和级数的项数。我们先预处理调和级数的前缀和，用并查集维护一下当前的连通性即可回答每次询问。总时间复杂度是 。

接下来回收伏笔，我们证明为什么对于长度为 的随机排列 ， 。我们提供两种证明。

证明一需要高超的生成函数技巧，如果你能看懂的话我贴在这了，总之我没看懂。

img)Q3N$Y.png)

如果你对细节感兴趣，链接是 https://codeforces.com/blog/entry/77468。

证明二如下，是我一点一点推出来的，推完之后跟 triple_a 一说，triple_a 立刻掏出了上面这篇文章，告诉我这个结论是 well-known 的，然后为了防止题目看起来太原，这个题才被改成增量询问的版本。

我们令 代表所有长度为 的排列的 的期望。当我们试图从前置状态转移到 时，相当于我们选择将 作为一个新的一阶轮换或者插入一个已有的轮换。记 所在的轮换阶数为 ，则 为 的加权均值。经过观察我们可以发现， 所在的轮换的长度在 是均匀分布的，所以前文中加权均值的权实际上都相等（为了不打断思路我们最后再来证明这一点）。由此，我们有 。我们考虑用数列的形式表示上面的转移，则有 。这意味着
$E(c(p)) = \sum_{i=1}^{n} \frac 1i$。

接下来再回收伏笔，我们来讨论为什么 所在的轮换的长度在 是均匀分布的。考虑 个人选 个格子，从 号玩家开始，他在 到 号格子中选一个，占到 号格子后 号玩家从剩余的格子里面选一个，直到 号格子被选择时结束。那么这个游戏运行 轮结束的概率和 所在的轮换的长度为 的概率是一致的。枚举所有长度为 的排列，我们发现 在任意位置出现的概率都是相等的。把这个排列看做玩家们选择格子的顺序，我们就得到了上面的结果。

Code (by Nanarikom)

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;

ll inv[N], pre[N];
void init () {
    inv[1] = pre[1] = 1;
    for (int i = 2;i < N;++i) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
        pre[i] = (pre[i - 1] + inv[i]) % mod;
    }
}

int fa[N];
int getfa (int x) {
    return (x == fa[x]) ? x : fa[x] = getfa(fa[x]);
}
void merge (int u, int v) {
    u = getfa(u);
    v = getfa(v);
    fa[u] = v;
}

int main () {
    init();

    ios::sync_with_stdio(false);

    int n, cyc = 0;
    scanf("%d", &n);
    printf("%d\n", (n - pre[n] + mod) % mod);
    for (int i = 1;i <= n;++i) {
        fa[i] = i;
    }
    for (int i = 1;i <= n;++i) {
        int p;
        scanf("%d", &p);
        if (getfa(i) == getfa(p)) cyc++;
        else merge(i, p);
        printf("%d\n", (n - (pre[n - i] + cyc) + mod) % mod);
    }
}

Problem M. abushii Omoi

Idea

在 上支持如下操作。操作一：学习一个新的技能——花费 代价清除 内所有的陨石。操作二：给定一个点集代表陨石出现在这些位置，询问最少需要花费多少代价才能清除所有陨石。

Source & Random Fact

最开始是只有 A 题的，后来经过和 Bakapiano、triple_a@NJU 和 Nezzar@CUHK 的反复讨论之后有了这个版本。最终的做法是由 Nezzar@CUHK 给出的。

这个题的目标是让 ***joke 和 XZH 不能 AK，从结果来看圆满地完成了它的任务。

Solution

我们先来介绍一个单组 的最短路做法。我们把每次询问的点集看成若干个结点，对于每条线段，我们在询问集上二分其覆盖的结点。如果该线段能覆盖从第 个结点到第 个结点，我们连接一条从第 个结点到第 个结点的边，边权为 。此外，我们对于每个结点，将其向前一个结点连一条边，边权为 。容易发现，经过建图，覆盖询问集所需的最小代价会等于从第 个结点到终点的最短路。跑 dijkstra 即可。

以上算法显然无法通过本题，因为如果我们可以多次询问，建图的时间复杂度无法承受。我们再来介绍一个单组 的做法。考虑一个朴素的 DP，我们令 表示覆盖询问集前 个点所需的最小代价。求解 时，我们枚举 从哪一个 转移而来，并暴力枚举所有线段，找出覆盖第 个点到第 个点的权值最小的线段进行转移。这个朴素的 DP 是 的，我们考虑将线段的右端点作为版本建主席树，实现在 的时间复杂度内查询覆盖第 个点到第 个点的最小权值，则时间复杂度优化至 。

以上算法显然也无法通过本题，因为如果我们询问一个足够大的点集，那么 DP 的时间复杂度无法承受。结合两种做法，我们考虑按询问集大小分类讨论。当 ，我们使用建图 dijkstra 的做法；当 ，我们使用主席树优化 DP 的做法。由于 的询问不能超过 次，总复杂度大致不会超过 的级别。

Code (by Nanarikom & Bakapiano)

#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;

typedef long long LL;
typedef pair<int,int> pr;

const int MAXN = 1e5+5;
const int N = MAXN*40;
const int inf  = 1e9+ 114514;
const LL  linf = 1e18+114514;
const int M = 314;

#define mid ((l+r)>>1)

int cnt,mn[N],ls[N],rs[N],root[MAXN];
void insert(int pre,int &rt,int l,int r,int pos,int val)
{
    // printf("%d %d\n",l,r);
    if(!rt)rt=++cnt,mn[rt]=pre?mn[pre]:inf;
    if(l==r)return void(mn[rt]=min(mn[rt],val));
    if(pos<=mid)insert(ls[pre],ls[rt],l,mid,pos,val),rs[rt]=rs[pre];
    else insert(rs[pre],rs[rt],mid+1,r,pos,val),ls[rt]=ls[pre];
    if(ls[rt])mn[rt]=min(mn[rt],mn[ls[rt]]);    
    if(rs[rt])mn[rt]=min(mn[rt],mn[rs[rt]]);    
}
int query(int rt,int l,int r,int nl,int nr)
{
    if(!rt||nl>nr||nr<l||nl>r)return inf;
    if(l==nl&&r==nr)return mn[rt];
    if(nr<=mid)return query(ls[rt],l,mid,nl,nr);
    if(nl> mid)return query(rs[rt],mid+1,r,nl,nr);
    return min(
        query(ls[rt],l,mid,nl,mid),
        query(rs[rt],mid+1,r,mid+1,nr)
    );
}

int n,m;
vector<pr> seg[MAXN];
vector<int> v[MAXN];
LL   f[MAXN];
bool g[MAXN];
LL solve(vector<int> &a)
{
    //sort(a.begin(),a.end());
    int len = a.size();
    for(int i=1;i<=len;++i)
    {
        f[i]=linf;
        for(int j=1;j<=i;j++)
        {
            LL w = query(root[a[j-1]],0,n,a[i-1],n);
            if(w==inf)w=linf;
            // printf("w=%lld %d %d\n",w,a[j-1],a[i-1]);
            f[i]=min(f[i],f[j-1]+w);
        }
        // printf("f:%d=%lld\n",i,f[i]);
    }
    return f[len]>=linf?-1:f[len];
}

namespace nnk
{
    const int N = 1e5+5;
    int n, m;
    int l0[N], r0[N], w[N], tot = 0;
    int q[N] = {0};

    struct node {
        int v;
        LL w;
    };
    bool operator < (const node& a, const node& b) {
        return a.w > b.w;
    }

    vector <node> e[N];
    LL dis[N];
    int vis[N];
    void dijkstra (int n) {
        priority_queue <node> q;
        for (int i = 0;i <= n;i++) {
            dis[i] = linf;
            vis[i] = 0;
        }

        dis[0] = 0;
        q.push({0, 0});
        while (!q.empty()) {
            node t = q.top(); q.pop();
            int u = t.v;
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = 0;i < e[u].size();i++) {
                int v = e[u][i].v;
                int w = e[u][i].w;
                if ((!vis[v]) && (dis[v] > dis[u] + w)) {
                    dis[v] = dis[u] + w;
                    q.push({v, dis[v]});
                }
            }
        }
    }

    void read_seg(int i,int l,int r,int _w){tot++,l0[i]=l,r0[i]=r,w[i]=_w;}
    LL   solve(vector<int> &a)
    {
        int qsiz = a.size();
        for (int i = 0;i <= qsiz;++i) {
            e[i].clear();
        }
        for (int i = 1;i <= qsiz;++i) {
            // scanf("%d", &q[i]);
            q[i] = a[i-1];
            e[i].push_back({i - 1, 0});
        }
        //sort(q + 1, q + qsiz + 1);

        for (int i = 1;i <= tot;++i) {
            int l = lower_bound(q, q + qsiz + 1, l0[i]) - q;
            int r = upper_bound(q, q + qsiz + 1, r0[i]) - q - 1;
            e[max(0, l - 1)].push_back({r, w[i]});
            //cout << max(0, l - 1) << ' ' << r << endl;
        }
        dijkstra(qsiz);
        //for (int i = 0;i <= qsiz;++i) cout << i << ':' << dis[i] << endl;
        return (dis[qsiz] == linf) ? -1 : dis[qsiz];
    }
}

int main()
{
    scanf("%d%d",&n,&m),nnk::n=n,nnk::m=m;
    for(int i=1;i<=m;i++)
    {
        int t,l,r,w,k;
        scanf("%d",&t);
        if(t==1)scanf("%d%d%d",&l,&r,&w),seg[l].push_back({r,w}),nnk::read_seg(i,l,r,w);
        if(t==2)
        {
            scanf("%d",&k);
            while(k--)scanf("%d",&w),v[i].push_back(w);
            g[i]=1;
        }
    }
    int pre=0,cur=0;
    for(int i=0;i<=n;i++)
    {
        for(auto p:seg[i])
        {
            cur=0;
            insert(pre,cur,0,n,p.first,p.second);
            pre=cur;
        }
        root[i]=pre;
    }
    for(int i=1;i<=m;i++)if(g[i])
        printf("%lld\n",v[i].size()<=M?solve(v[i]):nnk::solve(v[i]));
    return 0;
}