A. Pride

考虑如果序列中出现了一个或以上的 1，那么剩下的所有元素都可以只用一次变为 1。若原序列中没有 1 则考虑找到长度最小的 gcd 为 1 的区间并把这个区间内的一个元素变为 1。复杂度 O(n^2\log n)。

B. Gluttony

做这道题的时候我看到 n\leq 22 就没敢往贪心构造来想。。然而这只是因为这题的 checker 复杂度是 O(n2^n) 的，实际上构造的复杂度可以很低。

考虑这样一种构造：先将序列排好序，然后令 b_1=a_n,b_i=a_{i-1},\forall i\in[2,n]。这样不包含元素 1 的子集一定有 \sum a_{x_i}>\sum b_{x_i}。而包含 1 的子集则仅有全集才能使上式取等号，而题目中不考虑。因此这样是对的。

C. Envy

先说我很菜的 LCT 做法。

先 Kruskal 求出一棵 MST，并用边权 LCT 维护起来。然后对于每个询问的每条边，按以下方式处理：

• 若这条边在当前的 LCT 中，不处理它。
• 否则，在这条边的两端点构成的 LCT 中路径找出边权最大的一条边 e。
  • 若 e 的边权严格小于询问边的边权，则答案为 NO，立即退出。
  • 否则，在 LCT 中断边 e，连当前边，并在 LCT 中将当前边的权值设为 0。

所有边都加入完毕后，即可得出答案。最后把修改为 0 的边权改回原权值。

这样做的复杂度为 O(\left(m+\sum k)\log (n+m)\right)，但常数很大，实测会在第 26 个点 TLE。但是我们可以将出题人给你的边的顺序 random_shuffle 以下就可以早点退出减小常数了。但事实上应该还是可以卡的，不过我就没有写额外的优化技巧了。这里是部分代码：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=550000;
const int INF=1E9;
typedef pair<int, int> Max;
struct LCT
{
    struct Node
    {
        int c[2], fa;
        int val; Max mx;
        bool rev;
    } tr[2*MAXN];
    // LCT 板子略。
} lct;
int n, m, q;
struct Edge
{
    int u, v, w;
} e[MAXN];
int c[MAXN], p[MAXN];
bool cmp(int a, int b)
{
    return e[a].w<e[b].w;
}
int d[MAXN];
int main()
{
//  freopen("C.in", "r", stdin);
//  freopen("C.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) lct.initNode(i, 0);
    for (int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
        lct.initNode(i+n, e[i].w);
        p[i]=i;
    }
    sort(p+1, p+m+1, cmp);
    for (int i=1, cnt=0; i<=m&&cnt<n-1; i++)
    {
        int u=e[p[i]].u, v=e[p[i]].v;
        if (!lct.connected(u, v))
        {
            lct.link(u, p[i]+n);
            lct.link(v, p[i]+n);
            cnt++;
        }
    }
    scanf("%d", &q);
    while (q--)
    {
        int k;
        scanf("%d", &k);
        for (int i=1; i<=k; i++)
            scanf("%d", &d[i]);
        random_shuffle(d+1, d+k+1);
        bool flag=1;
        for (int i=1; i<=k; i++)
        {
            int u=e[d[i]].u, v=e[d[i]].v, w=e[d[i]].w;
            lct.update(d[i]+n, 0);
            if (!lct.existedge(u, d[i]+n))
            {
                lct.split(u, v);
                Max mx=lct.tr[v].mx;
                if (mx.first<w)
                {
                    for (int j=1; j<=i; j++)
                        lct.update(d[j]+n, e[d[j]].w);
                    flag=0; break;
                }
                lct.cut(e[mx.second-n].u, mx.second);
                lct.cut(e[mx.second-n].v, mx.second);
                lct.link(u, d[i]+n); lct.link(v, d[i]+n);
            }
        }
        if (flag)
        {
            puts("YES");
            for (int i=1; i<=k; i++)
                lct.update(d[i]+n, e[d[i]].w);
        }
        else puts("NO");
    }
    return 0;
}

然后是正解。

MST 有两个性质：

• 任意 MST 的边权组成的多重集唯一。
• 对于一种正确的连边方式，只连权值小于一个数的边，图的连通性唯一。

因此对于一棵 MST，不同权值的边集之间是不互相影响的。可以对于每条边 Kruskal 预处理出，加完所有权值小于该边权值的边后，它的两端点所在的连通块。询问按边权分别处理，用并查集维护连通块间的连通性。复杂度可以做到 O\left((\sum k)\alpha(n)\right)。代码没写

E. Lust

观察题目，可以得到结论：每次操作的贡献为操作前后 \prod_{i=1}^{n}a_i 的差。进一步可以推出，答案为初始时 a_i 的乘积减去最终状态 a_i 的乘积的期望。

然后推到了这里我就没有往下想生成函数，因为我觉得 k 次的多项式处理起来似乎不太好搞。。因此错过正解。

考虑设 f_{A,i} 表示序列 A 操作了 i 次后所有情况的乘积之和，同理也设 f_{B,i}。那么有 f_{A\cup B,i}=\sum_{j=0}^{i}\binom{i}{j}f_{A,i}f_{B,i}。考虑使用指数生成函数，则有 F_{A\cup B}=F_AF_B。对于单个元素，有 f_{\{a_p\},i}=a_p-i，故

那么，将所有元素的 EGF 乘起来就是结果 EGF，即

这个式子分为两部分，设 H(x)=\prod_{i=1}^na_i-x，这部分只有 n 次，暴力 DP 或者分治 NTT 优化都可；另一部分 e^{nx} 可以递推计算。因此答案为

时间复杂度可以做到 O(n^2) 或 O(n\log^2n)。下面是 O(n^2) 实现：

#include <cstdio>
const int MAXN=5500;
const int P=1E9+7;
int a[MAXN], f[MAXN];
int qpow(int n, int k)
{
    int r=1;
    while (k)
    {
        if (k&1) r=1ll*r*n%P;
        n=1ll*n*n%P; k>>=1;
    }
    return r;
}
int main()
{
//  freopen("E.in", "r", stdin);
//  freopen("E.out", "w", stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++) scanf("%d", &a[i]);
    f[0]=1;
    for (int i=1; i<=n; i++)
        for (int j=n; j>=0; j--)
        {
            f[j]=1ll*a[i]*f[j]%P;
            if (j>0) f[j]=(f[j]-f[j-1]+P)%P;
        }
    int ans=1, invn=qpow(n, P-2);
    for (int i=1; i<=n; i++)
        ans=1ll*ans*a[i]%P;
    for (int i=0, p=1; i<=n&&i<=k; i++)
    {
        ans=(ans-1ll*p*f[i]%P+P)%P;
        p=1ll*p*(k-i)%P*invn%P;
    }
    printf("%d\n", ans);
    return 0;
}