「做题记录」计数 DP 选做

· · 算法·理论

写的是主要难点在计数 DP 上的题。组合数学做题记录。

被 employ 和 sale 创飞后发现基础不牢,因此放置了一定量的水题(

【无题解】P6651 「SWTR-5」Chain

P16415 【MX-X28-T4】「FAOI-R12」落花雨

给出一个长为 n 的 01 串 S。你可以执行任意次操作,将邻项做 \text{NOR} 运算合并,求最终可以得到的 01 串数目,对 998244353 取模。

多测,\sum n \le 10^6,2 秒,512 MB。

:::::success[题解] 考虑我们怎么做 O(2^n \times \text{poly}(n)),也就是枚举最终的串 T 然后判定 S \to T 是否合法。

如果我们能找到一种划分方式,将 S 划分为 |T| 个非空子串,使得子串内经过 \text{NOR} 合并以后可以变成 0 或 1,T 就是合法的。\text{NOR} 运算没啥性质,考虑打表观察结构。

::::info[打表代码]

int n;
set<int> st;
int nor(int a, int b) {return a == 0 && b == 0;}
void dfs(vector<int> a) {
    if (a.size() == 1) return st.emplace(a[0]), void();
    for (int i = 1; i < (int)a.size(); i++) {
        vector<int> b(a.begin(), a.end());
        b[i - 1] = nor(a[i], a[i - 1]);
        b.erase(b.begin() + i);
        dfs(b); 
    }
}

void _main() {
    cin >> n;
    vector<int> a(n);
    for (int s = 0; s < (1 << n); s++) {
        for (int i = 0; i < n; i++) a[i] = s >> i & 1;
        st.clear(), dfs(a);
        for (int i = 0; i < n; i++) cerr << a[i];
        cerr << ": ";
        for (int i : st) cerr << i << ' ';
        cerr << endl;
    }
} 

::::

根据打表的结果,在 n \ge 4 时所有串都能变成 0 和 1,而无法变换的子串只有如下 10 个:

所以判定就随便做了,比如做可行性 DP,转移由上面提到的 10 种情况分别判掉,可以获得一个多项式复杂度的判定方法。

计数其实也不难,考虑从右到左匹配 S,那么我们需要维护一个合法分隔点的集合 A,每个 i \in A 都表示 T 的当前后缀可以变换为 S_{[i+1,n]}。

当我们添加字符 c 时,新的集合 A' 由 A 转移而来,此时 i \in A' 当且仅当 \exists j \in A, S_{[i+1,j]} 可以变换为 c。此时将 f_A 转移到 f_{A'}。

当 0 \in A 时,说明 T 可以匹配整个串,我们就将 f_A 计入答案。初值 f_{\varnothing}=1。

上面提到的观察允许我们用 O(n) 的复杂度维护 A。可以将 A 的信息一个二元组 (m,X) 唯一表示:

因此,用二元组 (m,X) 即可表示一个集合 A,并且转移到的 (m',X') 必然有 m'<m,故 dp 无后效性。X \to X' 的过程需要把 10 种情况都编码进去计算,代码有点难写。

复杂度 O(n),状态数带 16 倍常数,转移带 10 倍常数,实现不好可能会被卡常。

:::::info[代码]

const int N = 2e5 + 5;
int n;
char s[N];
mint f[16][N];  // f[X][m]

bool chk(int c, int l, int r) {
    if (l > r || l < 1 || r > n) return false;
    int len = r - l + 1;
    if (c == 0) {
        if (len == 1) return s[l] != '1';
        if (len == 2) return s[l] != '0' || s[l + 1] != '0';
        if (len == 3) return s[l] != '0' || s[l + 1] != '1' || s[l + 2] != '0';
    } else {
        if (len == 1) return s[l] != '0';
        if (len == 2) {
            if (s[l] == '0' && s[l + 1] == '1') return false;
            if (s[l] == '1' && s[l + 1] == '0') return false;
            if (s[l] == '1' && s[l + 1] == '1') return false;
        }
        if (len == 3) {
            if (s[l] == '0' && s[l + 1] == '0' && s[l + 2] == '0') return false;
            if (s[l] == '1' && s[l + 1] == '0' && s[l + 2] == '1') return false;
            if (s[l] == '1' && s[l + 1] == '1' && s[l + 2] == '1') return false;
        }
    }
    return true;
}
pair<int, int> nxt(int m, int x, int c) {
    bitset<10> b;
    for (int k = 0; k < 4; k++) {
        if (!(x >> k & 1)) continue;
        int i = m - k;
        if (i < 0) continue;
        if (chk(c, i, i)) b[k] = 1;
        if (chk(c, i - 1, i)) b[k + 1] = 1;
        if (chk(c, i - 2, i)) b[k + 2] = 1;
    }
    int m0 = -1, x0 = 0;
    for (int i = m - 1; i >= m - 4; i--) {
        if (i < 0) continue;
        if (i <= m - 4 || b[m - 1 - i]) {
            m0 = i; break;
        }
    }
    if (m0 == -1) return make_pair(-1, -1);
    for (int k = 0; k < 4; k++) {
        int i = m0 - k;
        if (i < 0) continue;
        if (i <= m - 4 || b[m - 1 - i]) x0 |= (1 << k);
    }
    return make_pair(m0, x0);
}

void _main() {
    cin >> n >> (s + 1);
    for (int x = 0; x < 16; x++) fill(f[x], f[x] + n + 1, 0);
    f[1][n] = 1; mint res = 0;
    for (int m = n; m >= 1; m--) 
        for (int x = 0; x < 16; x++) 
            for (int c : {0, 1}) {
                auto [m0, x0] = nxt(m, x, c);
                if (m0 == -1) continue;
                f[x0][m0] += f[x][m];
                if (m0 >= 4 || (x0 >> m0 & 1)) res += f[x][m];
            }
    cout << res << '\n';
} 

:::::

P14514 [NFLSPC #8] 如何区分北京东路和北京东路

给出一个长为 n 的序列 a_i。进行 k 次操作,每次操作随机选择一个 i,令 \forall j \ne i, a_j \gets a_j+\frac{a_i}{n-1},并且 a_i \gets 0。对每个 i 求出 k 次操作后 a_i 的期望值,对 998244353 取模。

:::::success[题解]

考虑正推,设 f_{i,k} 为 k 次爆炸以后城市 i 威力的期望,分类讨论:

注意到总威力 s=\sum_{i=1}^n a_i 不变,于是

\begin{aligned} f_{i,k}&=\dfrac{n-1}{n} \left(f_{i,k-1}+\sum_{j \ne i} \dfrac{f_{j,k-1}}{n-1} \right) \\ &=\dfrac{n-1}{n} \left(f_{i,k-1}+\dfrac{s-f_{i,k-1}}{(n-1)^2}\right)\\ &=\dfrac{n-1}{n}f_{i,k-1}+\dfrac{s-f_{i,k-1}}{n(n-1)}\\ &=\dfrac{n-2}{n-1}f_{i,k-1}+\dfrac{s}{n(n-1)} \end{aligned}

可以做到 O(nk)。解这个线性递推得到

f_{i,k}=\dfrac{s}{n}+\left(a_i-\dfrac{s}{n}\right)\left(\dfrac{n-2}{n-1}\right)^k

可以做到 O(n+\log k),实现是 O(n\log k) 的。

:::::

:::::info[代码]

const int N = 1e6 + 5;
int n, k;
mint a[N];

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    mint s = accumulate(a + 1, a + n + 1, mint(0));
    for (int i = 1; i <= n; i++) cout << s / n + (a[i] - s / n) * (mint(n - 2) / (n - 1)).pow(k) << ' ';
}

:::::

AGC030D Inversion Sum

给出一个长为 n 的序列 a_i。进行 k 次操作,每次操作给出 x_i,y_i,可以选择交换 a_{x_i},a_{y_i} 或不交换。求所有 2^k 种操作方式后逆序对数目的总和,对 10^9+7 取模。

:::::success[题解]

计数转期望。注意到 O(n^2) 是能过的。如果认为每个操作等概率执行或不执行,可以设 dp_{i,j} 为当前时刻 a_i > a_j 的概率。

那么答案就是 2^m \sum\limits_{i<j} dp_{i,j},也就是期望乘总数。现在我们考虑对于一次操作 x,y 对第 i 个位置造成的影响:

注意对于 dp_{x,y} 也有转移为 dp_{x,y} \gets \frac{dp_{x,y}+dp_{y,x}}{2},原理类似。复杂度 O(n^2)。

:::::

:::::info[代码]

const int N = 3005;
int n, m, a[N], x[N], y[N];
mint dp[N][N];

void _main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i] > a[j]) dp[i][j] = 1;
        }
    }
    for (int k = 1; k <= m; k++) {
        for (int i = 1; i <= n; i++) {
            if (i == x[k] || i == y[k]) continue;
            dp[x[k]][i] = dp[y[k]][i] = (dp[x[k]][i] + dp[y[k]][i]) / 2;
            dp[i][x[k]] = dp[i][y[k]] = (dp[i][x[k]] + dp[i][y[k]]) / 2;
        }
        dp[x[k]][y[k]] = dp[y[k]][x[k]] = (dp[x[k]][y[k]] + dp[y[k]][x[k]]) / 2;
    }
    mint res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) res += dp[i][j];
    } cout << res * mint(2).pow(m);
}

:::::

CF1184D2 Parallel Universes (Hard)

给出 n,m,k,表示现有 n 个元素,元素数目上限为 m,当前位置为 k。记 l 为当前元素数目,每次操作以 1-\frac{l}{m} 概率插入新元素到随机位置,或以 \frac{l}{m} 概率删除一段前缀 / 后缀。当前位置到达首尾时停止操作。求最终元素数目期望,对 10^9+7 取模。

:::::success[题解] 我们首先有一个期望 DP。设 e_{l,r} 表示当前左侧有 l 个元素,右侧有 r 个元素时,剩余元素数的期望。边界为 e_{0,r}=r+1,e_{l,0}=l+1。

转移的话根据题目来转移,每种转移乘上一个概率。这里我们有

e_{l,r}=p_l \times e_{l+1,r}+p_r \times e_{l,r+1}+p_d \times \left(\sum_{i=0}^{l-1} e_{i,r}+\sum_{j=0}^{r-1} e_{l,j} \right)

其中,p_l 为向左创造的概率,p_r 为向右创造的概率,p_d 为删除的概率。记当前元素数 c=l+r+1,根据题目我们有

p_l = \dfrac{(m-c)(l+1)}{m(c+1)} p_r=\dfrac{(m-c)(r+1)}{m(c+1)} p_d=\dfrac{c}{m(c-1)}

然后你发现 e 的转移怎么有环。但是这个转移是一个线性组合,可以高斯消元做出。状态数 O(m^2),总复杂度 O(m^6)。

观察转移,我们发现:e_{l,r+1} 可以被 e_{l,r},e_{l+1,r} 及其对应的前缀和唯一表示。因此,我们将 e_{l,1} 作为主元。之后,我们通过 O(m^3) 的朴素转移,将每个 e_{l,r} 表示为 e_{l,1} 的线性组合,即维护一个多项式。

当 l=m 时,转移方程缺失 p_l,p_r 这两项,形成了一个线性方程,且总数为 m-2。由于主元也恰有 m-2 个,可以对这里高斯消元,回代到 e_{k-1,n-k} 即可。线性逆元,总复杂度 O(m^3)。

::::::info[代码]

const int N = 255;
int n, k, m;

using poly = array<mint, N>;
poly operator+ (const poly& a, const poly& b) {
    poly c;
    for (int i = 0; i < N; i++) c[i] = a[i] + b[i];
    return c;
}
poly operator- (const poly& a, const poly& b) {
    poly c;
    for (int i = 0; i < N; i++) c[i] = a[i] - b[i];
    return c;
}
poly operator* (const poly& a, mint b) {
    poly c;
    for (int i = 0; i < N; i++) c[i] = a[i] * b; 
    return c;
}
poly e[N][N], sr[N];
mint mat[N][N];

void work() {
    for (int r = 1; r <= m - 3; r++) {
        poly sl = e[0][r];
        for (int l = 1; l <= m - r - 2; l++) {
            mint cnt = l + r + 1;
            mint pl = (m - cnt) * (l + 1) / ((cnt + 1) * m), pr = (m - cnt) * (r + 1) / ((cnt + 1) * m);
            poly t1 = (sl + sr[l]) * (cnt / ((cnt - 1) * m)), t2 = e[l + 1][r] * pl;
            e[l][r + 1] = (e[l][r] - t1 - t2) * (mint(1) / pr);
            sl = sl + e[l][r];
        }
        for (int l = 1; l <= m - r - 2; l++) sr[l] = sr[l] + e[l][r];
    }
}
void build() {
    for (int l = 1; l <= m - 2; l++) {
        int r = m - l - 1;
        poly sl = e[0][r], sr = e[l][0];
        for (int i = 1; i < l; i++) sl = sl + e[i][r];
        for (int i = 1; i < r; i++) sr = sr + e[l][i];
        poly f = e[l][r] - (sl + sr) * (mint(1) / (m - 1));
        for (int i = 0; i < m - 2; i++) mat[l - 1][i] = f[i];
        mat[l - 1][m - 2] = -f[m - 2];
    }
}
void guass() {
    for (int i = 0; i < m - 2; i++) {
        int k = i;
        for (int j = i; j < m - 2; j++) {
            if (mat[j][i] != 0) {k = j; break;}
        }
        swap(mat[i], mat[k]);
        mint inv = ~mat[i][i];
        for (int j = i; j <= m - 2; j++) mat[i][j] *= inv;
        for (int j = 0; j < m - 2; j++) {
            if (i == j) continue;
            mint x = mat[j][i];
            for (int k = i; k <= m - 2; k++) mat[j][k] -= x * mat[i][k];
        }
    }
}

void _main() {
    cin >> n >> k >> m;
    if (m <= 2 || k == 1 || k == n) return cout << n, void();
    for (int l = 0; l <= m; l++) e[l][0][m - 2] = l + 1;
    for (int r = 0; r <= m; r++) e[0][r][m - 2] = r + 1;
    for (int l = 1; l <= m - 2; l++) e[l][1][l - 1] = 1, sr[l] = e[l][0];
    work(), build(), guass();
    mint res = e[k - 1][n - k][m - 2];
    for (int i = 0; i < m - 2; i++) res += mat[i][m - 2] * e[k - 1][n - k][i];
    cout << res;
}

::::::

P4223 期望逆序对

给出一个长为 n 的排列 a_i。k 次操作均匀随机选择两个不同下标 x,y,交换 a_x,a_y。求操作后逆序对数目的期望,对 10^9+7 取模。

::::::success[题解]

记 f_{i,x,y} 为进行 i 轮操作后,a_x>a_y 的概率,答案即 \sum f_{k,x,y}。考虑在一轮中,x,y 的变化:

我们不妨在最后再让 f_{i,x,y} 乘上一个概率系数 \frac{2}{n(n-1)} 来让式子更自然。上面的转移是省略了系数的结果。

直接做为 O(kn^3),对第 2&3 条转移记录一下行列和就是 O(kn^2) 了。可以获得 50 分。

:::::info[50pts 代码]

const int N = 505;
int n, k, a[N];
mint f[2][N][N], r[N], c[N];

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) f[0][i][j] = a[i] > a[j];
    const mint p = ~mint(n) * ~mint(n - 1) * 2, i2 = ~mint(2);
    for (int T = 1, st = 1; T <= k; T++, st ^= 1) { 
        for (int i = 1; i <= n; i++) r[i] = accumulate(f[st ^ 1][i] + 1, f[st ^ 1][i] + n + 1, mint(0));
        for (int j = 1; j <= n; j++) {
            c[j] = 0;
            for (int i = 1; i <= n; i++) c[j] += f[st ^ 1][i][j];
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                f[st][i][j] = f[st ^ 1][i][j] * (n - 2) * (n - 3) * i2;  
                f[st][i][j] += r[i] - f[st ^ 1][i][j];
                f[st][i][j] += c[j] - f[st ^ 1][i][j];
                f[st][i][j] += f[st ^ 1][j][i];
                f[st][i][j] *= p;
            }
        }
    }
    mint res = 0;
    for (int i = 1; i <= n; i++) 
        for (int j = i + 1; j <= n; j++) res += f[k & 1][i][j];
    cout << res * (~p).pow(k);
}

:::::

记 p=\frac{2}{n(n-1)}。整理一下转移式:

\begin{aligned} f_{i,x,y}&=p\left(\left(C_{n-2}^2-3\right)f_{i-1,x,y} +r_{i-1,x}+c_{i-1,y}+1\right)\\ r_{i,x}&=\sum_{y \ne x} f_{i,x,y}\\ c_{i,y}&=\sum_{x \ne y} f_{i,x,y} \end{aligned}

我们来观察一下性质:

性质 1 当 x \ne y 时,恒有 f_{i,x,y}+f_{i,y,x}=1。

性质 2 c_{i,y}=n-1-r_{i,y}。

:::::success[性质 2 的证明] 将性质 1 代入 c 的定义式:

\begin{aligned} c_{i,y}&=\sum_{x \ne y} f_{i,x,y}\\ &=\sum_{x \ne y} (1-f_{i,y,x})\\ &=n-1-\sum_{x \ne y} f_{i,y,x}\\ &=n-1-r_{i,y} \end{aligned}

:::::

性质 3 \sum\limits_{x' \ne x} r_{i,x'}=C_n^2-r_{i,x}。

:::::success[性质 3 的证明] 根据性质 1,在矩阵 f_i 中,非对角线的元素和为 C_n^2。

考虑 r 的定义即有 \sum \limits_{x}r_{i,x}=C_n^2。

根据性质 2,我们只需计算 r 即可实现加速转移的目的。接下来,将 f 的转移代入 r:

\begin{aligned} r_{i,x}&=\sum_{y \ne x} f_{i,x,y}\\ &=p\sum_{y \ne x}\left(\left(C_{n-2}^2-3\right)f_{i-1,x,y} +r_{i-1,x}+c_{i-1,y}+1\right)\\ &=p\left(\sum_{y \ne x}\left(C_{n-2}^2-3\right)+\sum_{y \ne x}r_{i-1,x}+\sum_{y \ne x}c_{i-1,y}+\sum_{y \ne x} 1\right)\\ &=p\left((C_{n-2}^2-3) r_{i-1,x} +(n-1)r_{i-1,x}+\sum_{y \ne x}(n-1-r_{i,x})+n-1\right)\\ &=p\left((C_{n-2}^2-3) r_{i-1,x} +(n-1)r_{i-1,x}+(n-1)^2-(C_n^2-r_{i-1,x})+n-1\right)\\ &=p\left(\dfrac{n(n-3)}{2}r_{i-1,x}+C_n^2\right)\\ &=\dfrac{n-3}{n-1}r_{i-1,x}+1 \end{aligned}

我们发现,r 和初始排列以及 f 的值无关!

解一阶线性递推得

r_{i,x}=\dfrac{n-1}{2}+\left(\dfrac{n-3}{n-1}\right)^i \left(r_{0,x}-\dfrac{n-1}{2}\right)

:::::success[怎么解] 记 \alpha=\frac{n-3}{n-1}。假定数列收敛于常数 C,则 C=\alpha C+1。解得 C=\frac{n-1}{2}。

将原递推式与 \alpha C+1 相减

r_{i,x}-C=(\alpha r_{i-1,x}+1)-(\alpha C+1)\\ r_{i,x}-C=\alpha\left(r_{i-1,x}-C \right)

我们构造了一个以 \alpha 为公比的等差数列。根据等差数列通项公式

r_{i,x}-C=\alpha^i \left(r_{0,x}-C\right)
移项得解。

我们写出整体期望 e_i=\sum\limits_{x<y}f_{i,x,y},答案为 e_k。将 f 的转移代入

e_i=\dfrac{n-5}{n-1} e_{i-1} +p \sum\limits_{x<y} (r_{i-1,x}+c_{i-1,y}+1)

代入性质 2 和 r 的递推式得

e_i=\dfrac{n-5}{n-1} e_{i-1} +n+\dfrac{2C}{n(n-1)} \left(\dfrac{n-3}{n-1}\right)^{i-1}\\ C=\sum_{x=1}^n \left(r_{0,x}-\dfrac{n-1}{2}\right)(n-2x+1)

我们有 f_{0,x,y}=[a_x>a_y],根据 r 的定义 r_{0,x}=\sum\limits_{x \ne y} [a_x>a_y]=a_x-1。

解关于 e 的线性递推:

e_i=\left(\dfrac{n-5}{n-1}\right)^i e_0 +C_n^2 \dfrac{1-\left(\frac{n-5}{n-1}\right)^i}{2}+\dfrac{C\left(\left(\frac{n-3}{n-1}\right)^{i}-\left(\frac{n-5}{n-1}\right)^i\right)}{n}

求出初始逆序对数 e_0 后快速幂即可解决本题,复杂度 O(n \log n+\log k)。

::::::

::::info[代码]

const int N = 5e5 + 5;
int n, k, a[N];
struct BIT {
    int tr[N];
    void add(int x, int c) {
        for (; x <= n; x += lowbit(x)) tr[x] += c;
    }
    int ask(int x) {
        int res = 0;
        for (; x >= 1; x -= lowbit(x)) res += tr[x];
        return res;
    }
} B;

void _main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) return cout << 0, void();
    const mint i2 = ~mint(2), n5 = mint(n - 5) / (n - 1), n3 = mint(n - 3) / (n - 1), c2 = mint(n) * (n - 1) / 2;
    mint e0 = 0;
    for (int i = 1; i <= n; i++) B.add(a[i], 1), e0 += i - B.ask(a[i]);
    mint C = 0;
    for (int i = 1; i <= n; i++) C += (a[i] - 1 - (n - 1) * i2) * (n - 2 * i + 1);
    mint ek = n5.pow(k) * e0 + c2 * (1 - n5.pow(k)) / 2 + (C * (n3.pow(k) - n5.pow(k))) / n; 
    cout << ek * c2.pow(k);
} 

::::