AT2370 [AGC013D] Piling Up

博主： tony102
发布时间：2021 年 01 月 23 日
1587 次浏览
暂无评论
1224字数
分类：题解

[Link](https://www.luogu.com.cn/problem/AT2370)

## Sol

题目给的这个操作每次拿一个球再放两个球，这种操作就很不好计数。~~肉眼观察~~手玩一波可以发现，这个操作其实就可以理解为每次替换一个球为另一个与它个不同颜色的球。

那么再来考虑一下什么样的颜色序列是被认为不同的。构造出来的颜色序列只由每次被替换的球的颜色决定。如何描述一种方案，我们用一个这样的函数来表示。

[![fLHsk6.png](https://z3.ax1x.com/2021/08/20/fLHsk6.png)](https://imgtu.com/i/fLHsk6)

感谢[Winlere](https://www.cnblogs.com/winlere/p/10472232.html)的图（已经过允许使用）

黑色的先代表x轴，蓝色的线代表黑色球的数量，那么这个函数就是黑色球的数量关于时间的函数。我们来解决几个问题。因为我们的颜色序列只由每次取出来的是黑色还是白色的球组成，也就代表了斜率是正还是负。若取出球黑色球替换进一个白色球则是负，若取出白色球替换进黑色球则是正。上图中的线经过平移而成，实际上代表的颜色序列是一模一样的。而为什么截距不同，只是因为最开始黑白球的个数不确定所导致。

那么我们已经找到了描述一种方案的方法，也知道了如何的方案属于重复的方案。现在我们来考虑设计状态。设 $f[i][j]$ 表示第$i$次操作时剩余了$j$个黑球，这样的状态就无法描述出刚刚所述的重复方案。

现在很巧妙的地方就是这个状态设计了。设$f[i][j][0/1]$表示第$i$次操作时剩余了$j$个黑球，$0/1$表示黑色的球的数量有没有达到过$0$的状态。这代表的意思就是，因为一旦出现你剩余的球中完全没有黑球，那么下一步必然出来的是白球。也就是说，若有一种到达过黑色球数量为$0$的局面，那么意味着你无法再添加一条平移而得的线段了，因为在这之前所有方案到达这一步时下一步必须出白球。（此处语文表达能力有限，建议多深入思考一下）

~~经过深入地思考~~，你会发现必然有一种可以使黑球数量从未到达$0$的方案，那么就会算重。可以直接钦定他们在第$0$步就到达过数量为$0$的状态即可。

考虑转移，讨论这次取出来的是黑球还是白球。转移比较简单

## Code

```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int SIZE = 3e3 + 5;
const int mod = 1e9 + 7;

int n, m;
int f[SIZE][SIZE][2];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

signed main() {
	// freopen("code.in", "r", stdin);
	n = read(), m = read();
	f[1][0][1] = 1;
	for (int i = 1; i <= n; ++ i) f[1][i][0] = 1;
	for (int i = 1; i <= m; ++ i) {
		for (int j = 0; j <= n; ++ j) {
			if (j) {
				f[i + 1][j - 1][1] = (f[i + 1][j - 1][1] + f[i][j][1]) % mod;
				f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][1]) % mod;
				if (j == 1) {
					f[i + 1][j - 1][1] = (f[i + 1][j - 1][1] + f[i][j][0]) % mod;
					f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][0]) % mod;
				}
				else {
					f[i + 1][j - 1][0] = (f[i + 1][j - 1][0] + f[i][j][0]) % mod;
					f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][0]) % mod;
				}
			}
			if (j < n) {
				f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][0]) % mod;
				f[i + 1][j + 1][1] = (f[i + 1][j + 1][1] + f[i][j][1]) % mod;
				f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][0]) % mod;
				f[i + 1][j][1] = (f[i + 1][j][1] + f[i][j][1]) % mod;
			}
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; ++ i) {
		ans = (ans + f[m + 1][i][1]) % mod;
	}
	printf("%lld\n", ans % mod);
	return 0;
}
```

最后修改：2021 年 08 月 20 日