「做题记录」计数 DP 选做
stripe_python · · 算法·理论
写的是主要难点在计数 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[题解]
考虑我们怎么做
如果我们能找到一种划分方式,将
::::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;
}
}
::::
根据打表的结果,在
- 不能变成
0 :1、00、010; - 不能变成
1 :0、01、10、11、000、101、111。
所以判定就随便做了,比如做可行性 DP,转移由上面提到的
计数其实也不难,考虑从右到左匹配
当我们添加字符
当
上面提到的观察允许我们用
因此,用二元组
| 复杂度 |
|---|
:::::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[题解]
考虑正推,设
- 选择当前城市:
i 的威力变为0 。 - 选择其他城市:枚举
j \ne i ,则威力增加\dfrac{f_{j,k-1}}{n-1} 。
注意到总威力
可以做到
可以做到
:::::
:::::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[题解]
计数转期望。注意到
那么答案就是
- 若
i \ne x 且i \ne y :则dp_{x,i} \gets \frac{dp_{x,i}+dp_{y,i}}{2} 。因为每次操作以后它有\frac{1}{2} 的概率继承原来的状态,还有\frac{1}{2} 的概率变成dp_{y,i} 的状态,根据概率的加法原理可得。剩下的dp_{y,i},dp_{i,x},dp_{i,y} 同理。
注意对于
:::::
:::::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。设
转移的话根据题目来转移,每种转移乘上一个概率。这里我们有
其中,
然后你发现
观察转移,我们发现:
| 当 |
|---|
::::::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[题解]
记
- 选择与
x,y 不相关:f_{i-1,x,y} \times \frac{(n-2)(n-3)}{2}\to f_{i,x,y} 。 - 选择了
x 但不选y :\sum \limits_{z \ne y}f_{i-1,x,z} \to f_{i,x,y} 。 - 选择了
y 但不选x :\sum \limits_{z \ne x} f_{i-1,z,y} \to f_{i,x,y} 。 - 同时选择
x,y :f_{i-1,y,x} \to f_{i,x,y} 。
我们不妨在最后再让
直接做为
:::::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);
}
:::::
记
我们来观察一下性质:
性质 1 当
性质 2
:::::success[性质 2 的证明]
将性质 1 代入
:::::
性质 3
:::::success[性质 3 的证明]
根据性质 1,在矩阵
| 考虑 |
|---|
根据性质 2,我们只需计算
我们发现,
解一阶线性递推得
:::::success[怎么解]
记
将原递推式与
我们构造了一个以
| 移项得解。 |
|---|
我们写出整体期望
代入性质 2 和
我们有
解关于
求出初始逆序对数
::::::
::::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);
}
::::