P8386 [PA2021] Od deski do deski
挺奇怪的一个转移式，还是套路看少了
一开始想到的是 分治，像 卡特兰数 那样求
但是发现 两端相同 这个限制的 去重 不好处理，没法划分 子问题
就比如 样例的 \(4 ~ 2\)，显然包含 \(1 ~ 1 ~ 2 ~ 2\) 这种情况
当我们求 \(6 ~ 2\) 时，如果划分成 \(4 + 2\)，就会有 \((1 ~ 1 ~ 2 ~ 2) ~ (X ~ X)\) 这种东西
容易注意到其在划分成 \(2 + 4\) 的时候也会出现
但显然 \(2 + 4\) 的可能划分并不 全部包含在 \(4 + 2\) 中
所以也不能直接 舍弃一种划分方式，火大
然后 直接开始看题解，得到一种较好的思路
有点像 正难则反？从整体划分部分是困难的，于是我们考虑 从部分开始推出整体
注意到如果存在序列 \(S\)，数 \(x\)，使得 \(S + x\)（\(S\) 接上数 \(x\) 形成的 新序列）合法
则有 \(S + x + x\) 一定合法，且 \(S + x + y\)（保证 \(S + y\) 不合法时）一定不合法
如果 \(S\) 本身合法，则 \(x + x\) 构成一对即可
如果 \(S\) 不合法，则 \(S\) 中存在 \(x\)，一定可以把 \(S\) 写成 合法串 \(F\) + \(x\) + 任意串 \(G\) 的形式
这样 \(S + x = F + x + G + x\)，\(F\) 可以自己消掉， \(x + G + x\) 显然可以消掉，合法
而 \(S + x + x = F + (x + G + x + x)\)，显然合法
而若 \(S + y\) 不合法，则 \(S\) 中不存在 \(y\) 或 \(S\) 可写作 不合法串 \(T\) + \(y\) + 任意串 \(G\) 的形式
显然 \(x \neq y\)，故如果 \(S\) 中 不存在 \(y\)，则 \(S + x\) 中 不存在 \(y\)，显然 \(S + x + y\) 不合法
否则 \(S + x + y = T + y + G + y\)，消掉 \(y + G + y\) 中剩下 不合法串 \(T\)，仍然不合法
而 \(S + y + x = F + x + G + y + x\) 仍然合法
然后我们就可以推出转移式
我们设 \(f_{i, j ,0 / 1}\) 表示 当前遍历到前 \(i\) 个，下个数有 \(j\) 种填法使得 填完之后合法，以及 当前合法与否
这状态确实比较神秘...
分类讨论一下
-
如果当前合法，即 \(f_{i, j, 1}\)
-
下一个数选 \(j\) 种合法的之一，则 再下一个数 的 合法填法 数量不变
根据上面的结论可得，于是有 \(f_{i + 1, j, 1} += j * f_{i, j, 1}\)
-
下一个数选 \(M - j\) 种不合法的之一，则 再下一个数 的 合法填法 增加一个
即 \(S\) 合法且 存在 \(S + x\) 合法，而现在填了一个 \(y\)，变成 \(S + y\)（并不合法）
那么下一个数无论填 \(x\) 还是 \(y\) 均合法，也就是在原来 \(j\) 种 \(x\) 的选择下多了一种 \(y\)
于是有 \(f_{i + 1, j + 1, 0} += (M - j) * f_{i, j, 1}\)
-
-
如果当前不合法，即 \(f_{i, j, 0}\)
-
下一个数选 \(j\) 种合法的之一，则 再下一个数 的 合法填法 数量不变
根据上面的结论可得，于是有 \(f_{i + 1, j, 1} += j * f_{i, j, 0}\)
-
下一个数选 \(M - j\) 种不合法的之一，则 再下一个数 的 合法填法 数量不变
这里 没有多出一种填法，当前这种情况就是原串 \(S\) 不合法，而 \(S + x\) 合法
但我们填成了 \(S + y\)，故仍不合法，显然下一个数只能填 \(x\) 才合法
这与上面的第二种情况 对应了，有 \(f_{i + 1, j, 0} += (M - j) * f_{i, j, 0}\)
-
好于是四个式子就出来了，再整理一下就可以变成下面的 两个式子
\[f_{i, j, 1} = (f_{i - 1, j, 0} + F_{i - 1, j, 1}) * j \\ f_{i, j, 0} = f_{i - 1, j, 0} * (M - j) + f_{i - 1, j - 1, 1} * (M - j + 1) \]为啥要这样转化一下？我们发现现在 \(f_i\) 中的东西只从 \(f_{i - 1}\) 中得到，然后 滚动更新 一下
非常的快啊，而且空间很小，Record
#include <bits/stdc++.h>
const int MAXN = 3005;
const int MOD = 1000000007;
using namespace std;
long long F[MAXN][2][2];
int N, M, A;
int main () {
cin >> N >> M;
F[0][1][0] = 1;
for (int i = 1; i <= N; ++ i) {
for (int j = 1; j <= i; ++ j) {
F[j][1][i & 1] = (F[j][0][(i + 1) & 1] + F[j][1][(i + 1) & 1]) * j % MOD;
F[j][0][i & 1] = F[j][0][(i + 1) & 1] * (M - j) % MOD + F[j - 1][1][(i + 1) & 1] * (M - j + 1) % MOD;
}
F[0][1][i & 1] = F[0][0][i & 1] = 0;
}
for (int i = 1; i <= N; ++ i) A = (A + F[i][1][N & 1]) % MOD;
cout << A << endl;
return 0;
}