题解 AT2370 【[AGC013D] Piling Up】
Sata_moto
·
·
题解
\large{}\color {#6495ED} \mathcal{MyBlog}
前言：
$\quad \quad$ 楼主也是看了金钩大佬的题解才做出来的。
---
## 题目大意：
$\quad \quad$ 一开始有一个由 $n$ 个颜色为黑白的球（各个球颜色未知）组成的排列，有 $m$ 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球，最后拿出的球按顺序排列会形成一个颜色序列，求对于所有的初始排列，一共可以形成多少种颜色序列。
$\quad \quad$ 数据范围：$ n,m \le3000
思路分析:
$\quad \quad$ 本题本质上只有四种可能的操作，毕竟排列中球的顺序是没有意义的：
- 拿出黑球，放入黑球 & 白球，拿出黑球（操作1）
- 拿出黑球，放入黑球 & 白球，拿出白球（操作2）
- 拿出白球，放入黑球 & 白球，拿出黑球（操作3）
- 拿出白球，放入黑球 & 白球，拿出白球（操作4）
$\quad \quad$ 如果以操作次数为 $x$ 轴，以排列中白球的个数为 $y$ 轴，那么四个操作可以如下图描述。
$\quad \quad$ 可以看出，如果只考虑白球数目（每次操作后，排列中球的总数不会变，黑球的数量就是总球数减去白球数目），操作 $1$ 的最终结果是让白球数目增加 $1$，操作 $2,3$ 不会影响球的数目，操作 $4$ 则会让球的数目减 $1$。
$\quad \quad$ 不妨直接用向上的线段表示操作 $1$，向下的线段表示操作 $4$，水平的线段表示操作 $2/3$，就像下面这样：
$\quad \quad$ 下面我们分析每次操作会给 __序列__ 带来的变化：
$\quad \quad$ 操作 $1$ 会向序列中加入两个黑球，操作 $2/3$ 会向序列中加入一黑一白（因为序列是有序的，所以 $2/3$ 操作其实是不同的，但下面不做区分），操作 $3$ 会向序列中加入两个白球。
$\quad \quad$ 也就是说，这四种操作会带来四种不同的序列。
$\quad \quad$ 以任意一个排列作为起点，我们可以画出这 $m$ 次所有可能的操作的图像：
$\quad \quad$ 可以从中看出转移的思路：从一种排列开始，按照四种操作分别转移，显然可以统计出从一个点开始的所有情况并且不会重复。
$\quad \quad$ 于是我们设计状态 $f(i,j)$ 表示操作了 $i$ 次，排列中有 $j$ 个白球时，序列可能的情况总数。
$\quad \quad$ 转移显然是向三个方向的转移，中间的转移要重复一次（$2/3$ 两种操作不同）（注意各种转移的边界）。
$\quad \quad$ 但是初态怎么办？上面只是以某一种排列为起点，我们现在要求的是所有原始排列可以带来的所有可能的颜色序列。
$\quad \quad$ 是不是令 $f[0][j]=1$ 就可以了呢？
$\quad \quad$ 显然是不行的，不然这题就不会评紫了。
$\quad \quad$ 上面那是单单从一种排列为起点的所有选择的情况，所以可以保证每组选择各不相同，但是以所有排列为起点的话就会有重复的了。
$\quad \quad$ 比方说下面这种情况：
$\quad \quad$ 虽然两种情况的初始排列是不同的，但它们的操作顺序都是 $1,2,4$，所以都往序列中加入了 黑黑，黑白，白白，共六个球，它们的最终序列是相同的。
$\quad \quad$ 可以看出，最终序列在图像中，并不表现为点的坐标之类的形式，而是表现为图像的形状，使图像形状相同的两组操作存在重复。
$\quad \quad$ 如何解决这个问题？
$\quad \quad$ 有金钩大佬在另外一篇题解中提出了方案（%%%）：最终只统计白球数目达到过 $0$ 的操作组的答案。
$\quad \quad$ 为什么这样子可以？
$\quad \quad$ 首先，从上上张图可以看出来，从同一个点出发的路径是不存在重复的。
$\quad \quad$ 那么重复一定存在于从不同点出发的路径中，并且一定可以由一条路径上下平移得到另一条路径。
$\quad \quad$ 我们可以用反证法，假设在只统计白球数目达到过 $0$ 的情况时，统计任然有重复，设重复统计的这两条路径记为 $f(x),g(x)$。
$\quad \quad$ 因为两者可以上下平移得到，所以 $f(x)=g(x)+k$。
$\quad \quad$ 当 $f(x)=0$ 时，$g(x)=-k$，因为 $g(x)$ 有意义，所以 $g(x)=-k \le0$ （球的数目不会是负数嘛）。
$\quad \quad$ 当 $g(x)=0$ 时，同理有 $k\ge0$。因此 $k=0$，$f(x)=g(x)$，$f(x),g(x)$是同一条路径。
$\quad \quad$ 故此时不存在重复。（其实画图的话很简单可以看出不存在重复）
$\quad \quad$ 因此，我们可以多设一维表示当前状态的白球数目是否曾经达到过 $0$。
$\quad \quad$ 然后瞎搞就好了，注意转移时不要把操作真当做简单的上下线段了，要根据第一幅图的来转移（不仅仅是操作 $4$，操作 $3$ 也是可能在中途使白球数达到 $0$ 的）。
---
## 代码实现：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3010;
const int MOD = 1e9 + 7;
int n, m;
int f[N][N][2];
//取了 i 次，当前序列中有 j 个白球，是否经历过没有白球的状态
signed main()
{
scanf("%lld %lld", &n, &m);
for(register int k = 1; k <= n; k++)
f[0][k][0] = 1;
f[0][0][1] = 1;
for(register int k = 0; k < m; k++)
for(register int i = 0; i <= n; i++)
{
f[k][i][0] %= MOD, f[k][i][1] %= MOD;
if(i - 1 >= 0)
{
if(i == 1) f[k + 1][i - 1][1] += f[k][i][0];
else f[k + 1][i - 1][0] += f[k][i][0];
f[k + 1][i - 1][1] += f[k][i][1];
if(i == 1) f[k + 1][i][1] += f[k][i][0];
else f[k + 1][i][0] += f[k][i][0];
f[k + 1][i][1] += f[k][i][1];
}
if(i + 1 <= n)
{
f[k + 1][i + 1][0] += f[k][i][0];
f[k + 1][i + 1][1] += f[k][i][1];
f[k + 1][i][0] += f[k][i][0];
f[k + 1][i][1] += f[k][i][1];
}
}
int answ = 0;
for(register int k = 0; k <= n; k++)
answ += f[m][k][1], answ %= MOD;
printf("%lld", answ);
return 0;
}
```
---
## 结语：
$\quad \quad$ 如果本题解有BUG，还请评论或私信作者。
---
$$ \large{END}$$