「考试总结」ZROI-21-NOIP冲刺-TEST4 总结

#T1 序列变换

Time Limit: 1s Memory: 256MiB

#题意简述

给定两个长度为 \(n(n\leq3\times10^5)\) 的序列 \(a_i,b_i(1\leq a_i,b_i\leq10^9)\)，定义两个序列的距离为： \[ d(a,b)=\sum\limits_{i=1}^n(a_i-b_i)^2 \] 你可以任意选择 \(a_i\) 中两个数交换位置，求最小代价，对 \(998244353\) 取模，\(T=1\) 时给出最小代价所需步数。

#大体思路

\[ \begin{aligned} d(a,b)&=\sum\limits_{i=1}^n(a_i-b_i)^2=\sum\limits_{i=1}^n(a_i^2-2a_ib_i+b_i^2)\\ &=\sum\limits_{i=1}^na_i^2+\sum\limits_{i=1}^nb_i^2-2\sum\limits_{i=1}^na_ib_i, \end{aligned} \]

于是我们需要做的就是让 \(\sum_{i=1}^na_ib_i\) 尽可能大，根据排序不等式可知，将 \(a_i,b_i\) 都顺序/逆序排序后一一对应得到的答案最大。

我们可以得到变换后 \(a_i\) 对应的 \(b_i\) 的位置，他们会形成 \(k\) 个环，显然我们的最优交换策略是按环交换，每个环需要交换 \(k-1\) 次，于是总交换次数是 \(n-k\) 次。

时间复杂度 \(O(n\log n)\).

#Code

#define ll long long

const int N = 300010;
const ll MOD = 998244353;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, T; ll ans, a[N], b[N], ta[N], tb[N], tot;
ll sma, smb, sum, posa[N], posb[N], vis[N], vpos[N];

#define lb(t, len, x) lower_bound(t + 1, t + len + 1, x)

int main() {
    read(n); read(T);
    for (int i = 1; i <= n; ++ i)
      read(a[i]), (sma += a[i] * a[i] % MOD) %= MOD, ta[i] = a[i];
    for (int i = 1; i <= n; ++ i)
      read(b[i]), (smb += b[i] * b[i] % MOD) %= MOD, tb[i] = b[i];
    sort(ta + 1, ta + n + 1); sort(tb + 1, tb + n + 1);
    for (int i = 1; i <= n; ++ i)
      (sum += ta[i] * tb[i] % MOD) %= MOD;
    ans = ((sma + smb) % MOD - 2 * sum % MOD + MOD) % MOD;
    printf("%lld ", ans); if (!T) return 0;
    for (int i = 1; i <= n; ++ i) posa[i] = lb(ta, n, a[i]) - ta;
    for (int i = 1; i <= n; ++ i) posb[i] = lb(tb, n, b[i]) - tb;
    for (int i = 1; i <= n; ++ i) vpos[posb[i]] = i;
    for (int i = 1; i <= n; ++ i) posa[i] = vpos[posa[i]];
    for (int i = 1; i <= n; ++ i) {
        if (vis[i]) continue; int now = i; ++ tot;
        while (!vis[now]) {vis[now] = 1, now = posa[now];}
    }
    printf("%lld", n - tot);
    return 0;
}   

#T2 下象棋

Time Limit: 3s Memory Limit: 256MiB

#题意简述

一个 \(n\times n(n\leq10^6)\) 的棋盘，上面放置了 \(m(m\leq10^6)\) 个棋子，每个棋子的个攻击范围为所在的两条斜率为 \(1\) 和 \(-1\) 的斜线，问当前棋盘上有多少点不会被攻击到。

#大体思路

一个棋子对应了斜率为 \(1\) 和 \(-1\) 的两条斜线，这样的斜线的个数是 \(O(n)\) 级别的，每个斜率为 \(-1\) 的斜线都与一个奇偶性确定的斜率为 \(1\) 的斜线区间相交，于是我们可以对斜率为 \(-1\) 的直线进行标记，斜率为 \(1\) 的直线用奇偶分组前缀和处理。时间复杂度 \(O(n)\).

#Code

#define ll long long

const int N = 1000005;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T a, T b) {return a > b ? a : b;}
template <typename T> inline T Min(T a, T b) {return a < b ? a : b;}

bool zx[N << 1], fx[N << 1];
ll even[N << 1], odd[N << 1], n, m, ans;

inline ll len(ll x) {return Min(x, 2 * n - x);}

int main() {
    read(n), read(m); ans = n * n;
    for (int i = 1; i <= m; ++ i) {
        ll x, y; read(x), read(y); 
        zx[y - x + n] = 1, fx[2 * n - x - y + 1] = 1;
    }
    for (int i = 1; i < n << 1; ++ i)
      if (i & 1) odd[i] = odd[i - 1] + zx[i];
      else odd[i] = odd[i - 1];
    for (int i = 1; i < n << 1; ++ i)
      if (!(i & 1)) even[i] = even[i - 1] + zx[i];
      else even[i] = even[i - 1];
    for (int i = 1; i < n << 1; ++ i) ans -= zx[i] * len(i);
    for (int i = 1; i < n << 1; ++ i) ans -= fx[i] * len(i);
    for (int i = 1; i < n << 1; ++ i) {
        if (!fx[i]) continue;
        if (n & 1) {
            if (i & 1) ans += odd[n + len(i) - 1] - odd[n - len(i)];
            else ans += even[n + len(i) - 1] - even[n - len(i)];
        } else {
            if (!(i & 1)) ans += odd[n + len(i) - 1] - odd[n - len(i)];
            else ans += even[n + len(i) - 1] - even[n - len(i)];
        }
    }
    printf("%lld", ans); return 0;
}

#T3 外星病毒

Time Limit: 1s Memory Limit: 256MiB

#题意简述

一张 \(n(n\leq10^5)\) 个点 \(n\) 条边的有向图，每个点 \(i\) 有 \(p_i\) 的概率变为黑点，同时在变为黑点后有 \(q_i\) 的概率将自己的出边所指向的点变为黑点，问每个点变为黑点的概率，对 \(998244353\) 取模。

#大体思路

显然这是一个基环森林，且每个基环树都是内向树，考虑基环树上的 DP；

先不考虑环的影响，对于一棵树，设第 \(i\) 个点被染成黑色的概率是 \[ f_i=p_i+(1-p_i)(1-\prod\limits_{j\in ch_i}(1-f_jq_j)), \] 其中 \(\prod_{j\in ch_i}(1-f_jq_j)\) 是子树里一个也没传上来的概率，\((1-\prod_{j\in ch_j}(1-f_jq_j))\) 则是存在至少一个被染黑并传上来的概率。

现在再来考虑在环上的点被染黑的概率，环上某个点的 \(f\) 就是它被环外的点感染的概率，\(q_i\) 表示 \(i\) 到 \(i+1\) 的有向边存在的概率，设 \(g_i\) 表示 \(i\) 在环上被染黑的概率，先经典操作断环为链。

考虑边的存在情况，设 \(i\) 前面第一条不存在的边是 \(j-1\) 到 \(j\) 的边，在这种情况下，\(j\) 到 \(i-1\) 中只要有一个被染黑，\(i\) 就会被染黑，于是这部分的贡献是 \[ \sum\limits_{j=i-n+1}^i\left(\left(1-\prod_{k=j}^{i}(1-f_k)\right)\left(\prod\limits_{k=j}^{i-1}q_k\right)(1-q_{j-1})\right) \]

最初不理解这里为什么是 \(\prod_{k=j}^{i-1}q_k\)，即明明最前面的点可能没有被染黑，为什么需要所有边都存在，这样不会导致得到的概率改变么？实际上因为我们枚举了前面所有边的存在性，对于一个点 \(k\) 作为最左边黑色的点，它前面的第一条被断开的边的概率被分开考虑了，也就是说我们把状态细化了，根据全概率公式，最终加起来得到的概率依然是正确的概率。不过注意到，我们这样依旧会缺少状态，即前面没有边被断开，这也就是为什么要考虑下面的式子。下面式子中的 \(\prod_{k=i-n+1}^{i-1}q_k\) 也是同样的原因。

如果环上的边全部存在的话，那么只要有任意一个点被染黑，点 \(i\) 一定会被染黑，于是有贡献 \[ \left(1-\prod\limits_{k=i-n+1}^i(1-f_k)\right)\left(\prod\limits_{k=i-n+1}^{i-1}q_k\right) \] 通过一系列过程，可以得到环上的一个点 \(i\) 的完整的概率。于是只需要考虑 \(O(1)\) 维护 \(\sum_{j=i-n+1}^i\left(\prod_{k=j}^i(1-f_k)\right)\) 和 \(\sum_{j=i-n+1}^i\left((\prod_{k=j}^{i-1}q_k)(1-q_{j-1})\right)\) 即可。

---

以上是题解的做法，下面是我贺的神虎的做法。

考虑对于环上的一个点，显然当环上没有一个点被染黑时这个点一定不会被染黑，而这种情况的概率是 \(\prod_{i=1}^n(1-f_i)\)，于是除去这种情况的总概率是 \[ 1-\prod\limits_{i=1}^n(1-f_i) \] 对于点 \(i\)，我们考虑枚举最靠近它的黑点，这个总概率是 \[ \sum\limits_{j=i-n+1}^{i-1}\left(f_j\cdot\prod\limits_{k=j+1}^{i}(1-f_k)\right)+f_i, \] 但是在这所有的情况中，显然只有最近的点 \(j\) 到 \(i\) 的路径上的所有边都存在时才有可能将 \(i\) 染为黑色，于是这种情况的概率是 \[ \sum\limits_{j=i-n+1}^{i-1}\left(f_jq_j\cdot\prod\limits_{k=j+1}^{i}q_{k-1}(1-f_k)\right)+f_i, \] 于是对于点 \(i\) 的答案就是 \[ 1-\sum\limits_{j=i-n+1}^{i-1}\left(f_j\cdot\prod\limits_{k=j+1}^{i}(1-f_k)\right)-f_i+\sum\limits_{j=i-n+1}^{i-1}\left(f_jq_j\cdot\prod\limits_{k=j+1}^{i}q_{k-1}(1-f_k)\right)+f_i-\prod\limits_{i=1}^n(1-f_i) \]

---

本来贺写到这就结束了，但是突然意识到 \[ \sum\limits_{j=i-n+1}^{i-1}\left(f_jq_j\cdot\prod\limits_{k=j+1}^{i}q_{k-1}(1-f_k)\right)+f_i, \] 就是环上的答案，不需要额外多算其他的部分。

#Code

#define ll long long

const int N = 100010;
const ll MOD = 998244353;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, fa[N], t[N], vis[N], lst[N], inc[N];
ll p[N], q[N], f[N], part1[N], g[N], m[N];

vector <int> trees[N];

inline ll fpow(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) (res *= x) %= MOD;
        y >>= 1, (x *= x) %= MOD;
    }
    return res;
}

inline int find(int x) {while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}

int que[N], frt, tal;

void solve(vector <int> &tree) {
    /*Get the ring on the tree.*/
    int now = tree[0];
    while (!vis[now]) vis[now] = true, now = t[now];
    vector <int> ring(0); int nnow = now;
    do {
        ring.push_back(nnow);
        inc[nnow] = true; nnow = t[nnow];
    } while (nnow != now);
    for (int i = 0; i < ring.size(); ++ i) {
        int j = (i + 1) % ring.size();
        lst[ring[j]] = ring[i];
    }
    /*Use queue to run DP on the tree.*/
    for (auto u : tree) vis[u] = false;
    for (auto u : tree) ++ vis[t[u]];
    frt = 0; tal = -1; for (auto u : tree) f[u] = 1;
    for (auto u : tree) if (!vis[u]) que[++ tal] = u;
    while (frt <= tal) {
        int x = que[frt ++];
        if (!inc[t[x]] && !(-- vis[t[x]])) que[++ tal] = t[x];
        f[x] = f[x] * (MOD + 1 - p[x]) % MOD;
        f[x] = (MOD + 1 - f[x]) % MOD;
        (f[t[x]] *= (MOD + 1 - q[x] * f[x] % MOD)) %= MOD;
    }
    for (auto u : ring) {
        f[u] = f[u] * (MOD + 1 - p[u]) % MOD;
        (f[u] = MOD + 1 - f[u]) %= MOD;
    } 
    /*Calculate the answers on the ring.*/
    ll M = 1;
    for (auto u : ring) {
        m[u] = (MOD + 1 - f[u]) * q[lst[u]] % MOD,
        (M *= m[u]) %= MOD;
    }	
    now = ring[0]; ll ans0 = 0, tim = 1;
    do {
        (ans0 += tim * f[now]) %= MOD;
        tim = tim * m[now] % MOD; now = lst[now];
    } while(now != ring[0]);
    for (auto u : ring) {
        g[u] = ans0; ans0 = ans0 * m[t[u]] % MOD;
        ans0 = ans0 - M * f[t[u]] + f[t[u]];
        ans0 = ((ans0 % MOD) + MOD) % MOD;
    }
    for (auto u : ring) f[u] = g[u];
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++ i) fa[i] = i;
    for (int i = 1, a, b; i <= n; ++ i) {
        read(a), read(b);
        p[i] = 1ll * a * fpow(b, MOD - 2) % MOD;
    }
    for (int i = 1; i <= n; ++ i) read(t[i]);
    for (int i = 1, a, b; i <= n; ++ i) {
        read(a), read(b);
        q[i] = 1ll * a * fpow(b, MOD - 2) % MOD;
    }
    for (int i = 1; i <= n; ++ i)
      if (find(i) != find(t[i]))
        fa[fa[i]] = fa[t[i]];
    for (int i = 1; i <= n; ++ i)
      trees[find(i)].push_back(i);
    for (int i = 1; i <= n; ++ i)
      if (trees[i].size()) solve(trees[i]);
    for (int i = 1; i <= n; ++ i)
      printf("%lld ", f[i]);
    return 0;
}

#T4 删边方案

Time Limit: 5s Memory Limit: 256MiB

#题意简述

给定一张 \(n(\leq18)\) 个点 \(m(m\leq n(n-1))\) 条边的有向图，问有多少种不同的删边方案得到的图依旧存在环。

#大体思路

直接计算答案比较困难，考虑补集转化，我们求删边后得到 DAG（有向无环图）的方案数。

设 \(f_S\) 表示点集 \(S\) 删边得到 DAG 的方案数，直接计算依旧存在难度，考虑容斥。设 \(q_T\) 为我们令 \(S\) 的子集 \(T\) 中的点的入度都是 \(0\) ，\(S\) 中可能存在其他入度为 \(0\) 的点的方案数，考虑到 \(T\to S-T\) 的边可以连也可以不连， \(S-T\to T\) 的边一定不连，于是有： \[ q_T=2^{ways(T,S-T)}\times f_{S-T}, \] 我们设 \(p_T\) 为仅有 \(T(T\subseteq S)\) 中的点是入度为 \(0\) 的点时的方案数，显然有： \[ q_T=\sum\limits_{T\subseteq R\subseteq S}p_R \] 于是根据二项式反演的集合形式有 \[ p_T=\sum\limits_{T\subseteq R\subseteq S}(-1)^{|R|-|T|}q_R, \] 于是我们所求的答案便是 \[ \begin{aligned} f_S&=\sum\limits_{T\subseteq S,T\ne\varnothing}p_T=\sum\limits_{T\subseteq S,T\ne\varnothing}\sum\limits_{T\subseteq R\subseteq S}(-1)^{|R|-|T|}q_R\\ &=\sum\limits_{R\subseteq S,R\ne\varnothing}q_R\sum\limits_{T\subseteq R,T\ne\varnothing}(-1)^{|R|-|T|}\\ &=\sum\limits_{R\subseteq S,R\ne\varnothing}q_R\sum\limits_{k=1}^{|R|}(-1)^{|R|-k}\dbinom{|R|}{k}\\ &=\sum\limits_{R\subseteq S,R\ne\varnothing}q_R\sum\limits_{k=1}^{|R|-1}(-1)^{k}\dbinom{|R|}{k}\\ &=\sum\limits_{R\subseteq S,R\ne\varnothing}q_R\left(\sum\limits_{k=1}^{|R|}(-1)^{k}\dbinom{|R|}{k}-(-1)^{|R|}\right)\\ \end{aligned} \] 我们知道有这样一条定理（证明见补充证明）： \[ \sum\limits_{k=1}^{|S|}(-1)^{k}\dbinom{|S|}{k}=[S=\varnothing], \] 于是我们可以得到 \(f\) 的转移 \[ \begin{aligned} f_S&=\sum\limits_{R\subseteq S,R\ne\varnothing}q_R\left(\sum\limits_{k=1}^{|R|}(-1)^{k}\dbinom{|R|}{k}-(-1)^{|R|}\right)\\ &=\sum\limits_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}q_T\\ &=\sum\limits_{T\subseteq S,T\ne\varnothing}(-1)^{|T|-1}2^{ways(T,S-T)}\times f_{S-T}, \end{aligned} \] \(ways(T,S-T)\) 可以通过 \(ways(T-lowbit(T))\) 进行 \(O(1)\) 转移，然后直接干就完了。时间复杂度 \(O(3^n)\).

#Code

#define ll long long

const int N = (1 << 18) + 10;
const ll MOD = 1e9 + 7;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, m, u, v, e[20], re[20]; ll pw[310], f[N], num[N], lb[N], cnt[N];

int main() {
    read(n); read(m); pw[0] = 1; f[0] = 1;
    for (int i = 1; i <= m; ++ i) pw[i] = (pw[i - 1] << 1) % MOD;
    for (int i = 1; i < (1 << n); ++ i) cnt[i] = cnt[i >> 1] + (i & 1);
    for (int i = 1; i < (1 << n); ++ i) lb[i] = (i & 1 ? 1 : lb[i >> 1] + 1);
    for (int i = 1; i <= m; ++ i) read(u), read(v), e[u] |= (1 << v - 1), re[v] |= (1 << u - 1);
    for (int i = 1; i < (1 << n); ++ i) {
        for (int t = (i - 1 & i), j = i - t; ; t = (t - 1 & i), j = i - t) {
            num[j] = num[j - (j & -j)] - cnt[re[lb[j]] & j] + cnt[e[lb[j]] & i - j];
            (f[i] += ((cnt[j] & 1 ? 1 : MOD - 1) * pw[num[j]]) % MOD * f[i - j]) %= MOD;
            if (!t) break;
        }
    }
    printf("%d", (pw[m] - f[(1 << n) - 1] + MOD) % MOD);
    return 0;
}

#补充证明

#Part. 1

我们要求的结论： \[ \sum\limits_{k=1}^{|S|}(-1)^{k}\dbinom{|S|}{k}=[S=\varnothing], \] 证明：考虑这样一个问题：从 \([n]\) 到 \(\{y_1,y_2,\dots,y_k\}\) 的满射有多少个？

设 \(S\) 为所有 \([n]\) 到 \(\{y_1,y_2,\dots,y_k\}\) 的映射的集合，则 \(|S|=k^n\)，定义性质 \(P_i\) 表示“\(y_i\) 不是映射的像”，\(A_i\) 为满足性质 \(P_i(1\leq i\leq k)\) 的所有从 \([n]\) 到 \(\{y_1,y_2,\dots,y_k\}\) 的集合，显然对于任意 \(1\leq i\leq k\) 有 \[ |A_i|=(k-1)^n, \] 同样的，对于任意 \(1\leq i_1<i_2<\cdots<i_j\leq k\) 有 \[ |A_{i_1}\cap\cdots\cap A_{i_j}|=(k-j)^n, \] 于是，根据容斥原理所求满设的个数为 \[ \begin{aligned} &|\overline{A_1}\cap\overline{A_2}\cap\cdots\cap\overline{A_k}|\\ =&|S|-\sum_i|A_i|+\sum_{i<j}|A_i\cap A_j|-\cdots+(-1)^k|A_1\cap\cdots\cap A_k|\\ =&\sum_{j=0}^k(-1)^j\dbinom{k}{j}(k-j)^n=\sum_{j=0}^k(-1)^{k-j}\dbinom{k}{j}j^n, \end{aligned} \] 再考虑原题的组合意义，可以知道，若 \(k>n\)，则一定不存在满射，若 \(k=n\)，则满射的个数是 \(n!=k!\)，于是有 \[ \sum_{j=0}^k(-1)^{k-j}\dbinom{k}{j}j^n=\begin{cases}0,&k>n,\\n!,&k=n.\end{cases} \] 上式中 \(n=0\) 时即得所求结论（定义 \(0!=1\)）。

证毕.