AT_arc068_d Solitaire 题解
又是计数，吓哭了。
计数题太困难。
考虑加入之后的双端队列里有什么性质。由于你是按照从小到大的顺序加入的，因此呈现一个两边大中间小的 V 字形。
由于题目要求第
注意到左侧的数决定了唯一的双端队列，而左侧的数在前
此时我们考虑去重，我们使用代表元法，在可以生成一个序列的所有双端队列中选取一个代表元。首先我们的代表元必须要有足够良好的性质方便我们进行计数。
我们考虑对每个生成方案进行编码。定义一个二进制字符串
实际上构造这个方案是简单的，记录当前左端点的最小值，如果当前最小值小于左端点的最小值就直接扔到左边，否则扔到右边。注意到这个代表元有一个良好的性质，就是在任意小于
我们令
- 左侧序列扩展一次，枚举会给右侧增加几次扩展到机会。
- 右侧序列扩展一次，会使
减去 。
然后实际上是一个前缀和优化。注意如果右侧的扩展次数少于剩下元素个数了就不行了，这时要判掉。
然后队列里剩下的元素一共有
代码如下： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182#include <iostream>
#include <vector>
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
namespace maths {
template <ull mod, class int_type = ll, class uint_type = ull>
class modular {
private:
uint_type x;
void norm() { x -= mod * (x >= mod); }
public:
modular() : x(0) {}
modular(int_type _x) {
if (x < 0) {
x = _x % (int_type)mod + (int_type)mod;
}
else {
x = _x % mod;
}
norm();
return;
}
friend modular operator+(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + rhs.x;
ret.norm();
return ret;
}
friend modular operator-(const modular &lhs, const modular &rhs) {
modular ret;
ret.x = lhs.x + mod - rhs.x;
ret.norm();
return ret;
}
friend modular operator*(const modular &lhs, const modular &rhs) {
return modular(lhs.x * rhs.x);
}
modular operator-() const {
modular ret;
ret.x = mod - x;
return ret;
}
modular operator-=(const modular &b) { return *this = *this - b; }
modular operator+=(const modular &b) { return *this = *this + b; }
modular operator*=(const modular &b) { return *this = *this * b; }
bool operator==(const modular &b) const { return x == b.x; }
uint_type val() const { return x; }
friend std::istream &operator>>(std::istream &is, modular &rhs) {
is >> rhs.x;
rhs.x %= mod;
return is;
}
friend std::ostream &operator<<(std::ostream &os, const modular &rhs) {
os << rhs.val();
return os;
}
};
} // namespace maths
namespace maths {
template <class T>
T quick_pow(T a, ull b, T id = T()) {
T ret = id;
for (; b; b >>= 1, a = a * a) {
if (b & 1) {
ret = a * ret;
}
}
return ret;
}
} // namespace maths
int main() {
using mll = maths::modular<(ull)1e9 + 7>;
uint n, k;
std::cin >> n >> k;
std::vector<std::vector<mll>> dp(k + 1, std::vector<mll>(n + 1));
dp[0][0] = 1;
for (size_t i = 0; i < k - 1; i++) {
mll sum = 0;
for (size_t j = 0; j <= n; j++) {
/**
* 检测能不能填完。
*/
int rest = n - i - 1;
if ((int)j >= rest) {
break;
}
sum += dp[i][j];
dp[i + 1][j] = sum + (j != n ? dp[i][j + 1] : 0);
// std::cerr << dp[i + 1][j] << " ";
}
// std::cerr << std::endl;
}
mll ans = 0;
int rest = n - k;
for (size_t j = 0; j <= n; j++) {
/**
* 检测能不能填完。
*/
if ((int)j > rest) {
break;
}
ans += dp[k - 1][j];
}
// std::cerr << ans << std::endl;
std::cout << ans * (maths::quick_pow(mll(2), std::max<int>(0, rest - 1),
mll(1)))
<< std::endl;
return 0;
}
/**
* 显然你需要向一个方法去刻画这个东西。
*
* 首先就是什么样的序列可以被造出？
*
* 容易发现放入元素之后的 deque 一定中间底两边高。
*
* 然后你取出来的区间一定是一段一段的上升序列。
*
* 上升还是下降？
*
* 下降吧。总之就是这样。
*
* 然后你钦定了 1 在 k。换句话说在 k 前面必然有一个（左侧/右侧）是清空了的。
*
* 由于我们只关心序列，因此我们不妨钦定清空的是左边。
*
* 考虑左边有哪些数，选出来一些数，顺序一定是递减的，然后从左侧选择一些位置填进去。
*
* 但是可能会有重复啊。比如说，某个序列可能有多个生成方式。
*
* 因此直接这样做肯定是不行的。考虑 n 只有 2000，我们有另一个 O(n) 的维度可以使用。
*
* 不妨考虑重复的问题。那咋办。
*
* 那，考虑什么时候会重复呗。显然一个例子就是完全倒序的时候，完全倒序就会有很多种情况。
*
* 比如 6 5 4 3 2 1。
*
* 可以选择 6 5 4 或者 6 5 3 之类之类。
*
* 考虑代表元法，对于每个序列，钦定一个生成方式并且按照这个计数。
*
* 比如说，字典序最小的方案？
*
* 那我们要考虑如何对于一个可行序列生成字典序最小的方案了。
*
* 哦对还有一个性质就是我们一定可以钦定一段左边在右边前面。交换就行了。
*
* 我们不妨定一个 01 序列吧。让这个序列最小。1 的位置表示左边的位置。
*
* 依旧是那个问题。如何生成？能生成，如何计数？
*
* 是不是就是两个单调递减的序列，然后能往其中一个放就放啊。哦哦哦那对完了。那代表元结束了。
*
* 因此我们考虑两个问题。
* dp[i][j] 表示前 i 个，然后扩展到了 j。
*
* 一个转移是右侧扩展，另一个是左侧填一个数。然后我们发现性质就是左侧数的个数是永远小于右侧的个数的。
*
* 这个很难维护，因此我们不妨维护空隙。表示还有几个数右侧可以扩展。结束。
*
* 我们的目标是 dp[k][*]。
*
* 后面反正随便填。
*
* 哦哦转移复杂度是不是炸了。
*
* 考虑状态转移。
*
* dp[i][j] 表示填好了前 i 个，并且右侧还有 j 个需要扩展。那显然你右侧需要有 j 个可以连边的对吧？
*
* 然后我们认为都是一样的，你只需要往下几个。
*/