首先考虑如果固定了 \(a\),如何判定这个 \(a\) 是否能被排序。
如果存在 \(a_i > a_j(i < j)\),那么 \(a_i\) 肯定要交换到 \(a_j\) 后面,那么就肯定会交换 \(a_i, a_j\)。
于是合法条件就是如果存在 \(a_i > a_j(i < j)\),那么 \(a_i, a_j\) 只相差一个二进制位。
那就还能知道此时一定 \(a_i\) 这一位为 \(1\),\(a_j\) 这一位为 \(0\),其余位都相同。
于是可以考虑从高位开始往低位比较两个数字。
如果满足 \(a_i, a_j(i < j)\) 前面已经遍历的位都相同,这一位不同且 \(a_i\) 这一位为 \(1\),\(a_j\) 为 \(0\),就要求剩下的位 \(a_i, a_j\) 相同。
于是可以考虑 DP。
考虑到如果有了上面提到的情况,那么此时 \(a_i, a_j\) 在低位就应该当作一个数了,相当于合并操作,同时还有提到从高位往低位去比较。 就可以设状态 \(f_{n, m}\) 为最高位为 \(n\),当前有 \(m\) 个数的方案数。
接下来考虑转移,分为两种情况考虑:
-
不存在合并操作。
那么这个时候对于 \(n\) 这一位,就应该满足前面一部分为 \(0\),后面这部分为 \(1\),一共会有 \(m + 1\) 种可能的 \(01\) 分界线。同时考虑到此时先手可以操作使得这一位全变为 \(0\),那么比较还得继续到下一位。
有转移 \(f_{n, m} = (m + 1)f_{n - 1, m}\)。
-
存在合并操作,即存在 \(i < j\),\(a_i\) 第 \(n\) 位为 \(1\),\(a_j\) 第 \(n\) 位为 \(0\)。
考虑找到最靠前的为 \(1\) 的位置 \(l\),最靠后的为 \(0\) 的位置 \(r\),此时肯定满足 \(l < r\)。
那么可以知道的是,不论 \(l < i < r\) 里的 \(i\) 第 \(i\) 位是什么,肯定都会和 \(l\) 合并或者和 \(r\) 合并。
于是可以知道,\(l\le i\le r\) 的 \(a_i\) 都会合并,还剩下 \(m - (r - l)\) 个数。同时如果先手也选择了把这一位设成 \(0\),还需要轮到下一轮比较。
此时的方案数为中间 \(r - l - 1\) 个数这一位任选的 \(2^{r - l - 1}\)。
进一步的,考虑到对于同样的 \(r - l\),不管 \(l, r\) 是多少,本质都是相同的,此时对应的有 \(m - (r - l)\) 种方案。
于是考虑枚举 \(m - (r - l)\),有转移 \(f_{n, m} = \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
综上,有转移 \(f_{n, m} = (m + 1)f_{n - 1, m} + \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
对于转移的优化,考虑拎出后面求和的部分,令 \(g_{n, m} = \sum\limits_{i = 1}^{m - 1} i2^{m - i - 1} f_{n - 1, i}\)。
那么有 \(g_{n, m + 1} = \sum\limits_{i = 1}^m i 2^{m - i} f_{n - 1, i}\)。
可以发现有 \(g_{n, m + 1} = 2g_{n, m} + mf_{n - 1, m}\),可以递推求出。
时间复杂度 \(\mathcal{O}(nm)\)。
#include<bits/stdc++.h>
using ll = long long;
constexpr ll mod = 1e9 + 7;
const int maxn = 5e3 + 10;
ll f[maxn], g[maxn];
int main() {
int n, m; scanf("%d%d", &n, &m);
std::fill(f + 1, f + m + 1, 1);
while (n--) {
std::copy(f + 1, f + m + 1, g + 1);
for (int i = 1; i <= m; i++)
f[i] = (f[i - 1] * 2 + g[i - 1] * (i - 1)) % mod;
for (int i = 1; i <= m; i++)
(f[i] += g[i] * (i + 1)) %= mod;
}
printf("%lld\n", f[m]);
return 0;
}
标签:Atcoder,Sorting,limits,int,sum,合并,一位,Game,考虑
From: https://www.cnblogs.com/rizynvu/p/18357643