ARC068F Solitaire <计数DP>

Posted on Symbols count in article: 770 Reading time ≈ 3 mins.

Problem

Solitaire

Time  limit:  2  Sec\mathrm{Time\;limit:\;2\;Sec}
Memory  limit:  256  MB\mathrm{Memory\;limit:\;256\;MB}

Statement

Snuke has decided to play with NN cards and a deque (that is, a double-ended queue). Each card shows an integer from 11 through NN, and the deque is initially empty.
Snuke will insert the cards at the beginning or the end of the deque one at a time, in order from 11 to NN. Then, he will perform the following action NN times: take out the card from the beginning or the end of the deque and eat it.
Afterwards, we will construct an integer sequence by arranging the integers written on the eaten cards, in the order they are eaten. Among the sequences that can be obtained in this way, find the number of the sequences such that the KthK^{th} element is 11. Print the answer modulo 109+710^9+7.

Constraints

1≤K≤N≤20001\le K\le N\le2000

Input

The input is given from Standard Input in the following format:
N  KN\;K

Output

Print the answer modulo 109+710^9+7.

Sample

Input #1

1
2 1

Output #1

1
1

Explanation #1
There is one sequence satisfying the condition: 1,21,2. One possible way to obtain this sequence is the following:
Insert both cards, 11 and 22, at the end of the deque.
Eat the card at the beginning of the deque twice.
Input #2

1
17 2

Output #2

1
262144

Input #3

1
2000 1000

Output #3

1
674286644

标签：计数DP

Translation

有一个双端队列，将1∼n1\sim n顺序加入其中，加在队头或队尾任意。随后将所有数弹出，每次弹队头或队尾任意。求有多少种出队序列使得11在第kk个。

Solution

考虑双端队列的形态，其一定是开头从大到小直到11，再从小到大直到最后。这样当11在第kk个出队时，第1∼(k−1)1\sim(k-1)个数一定可以划分为两个递减子序列。用fi,jf_{i,j}表示第1∼i1\sim i个数，最小值较小的子序列的最小值为jj的序列种数。考虑fi,pf_{i,p}能由哪些状态转移，若第ii个数取pp，则有∑q>pfi−1,q\sum_{q>p}f_{i-1,q}种序列；若第ii个数比pp大，则一定由fi−1,pf_{i-1,p}转移，于是有fi,p=∑q≥pfi−1,qf_{i,p}=\sum_{q\ge p}f_{i-1,q}。前缀和优化即可做到O(k)O(k)。

对这个队列进行出队到11时，一定是11前面没有数或11后面没有数，那么队列中剩下的一定是一个递增序列或递减序列。那么在11出队后，一定是要么弹出剩下的最小的数，要么弹出剩下的最大的数。可以知道对于每种出队序列第1∼(k−1)1\sim(k-1)个数的情况，第(k+1)∼n(k+1)\sim n个数一定有2n−k−12^{n-k-1}种情况，于是答案为fk−1,2×2n−k−1f_{k-1,2}\times 2^{n-k-1}。总复杂度O(k)O(k)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
#define MAX_N 2000
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, f[2][MAX_N+5];
int main() {
    read(n), read(m);
    for (int i = 1; i <= n+1; i++) f[0][i] = 1;
    for (int i = 1, c = 1; i < m; i++, c ^= 1) {
        memset(f[c], 0, sizeof f[c]);
        for (int j = 1; j <= n-i+1; j++) f[c][j] = f[c^1][j];
        for (int j = n; j; j--) f[c][j] = (f[c][j]+f[c][j+1])%P;
    }
    int ans = f[(m-1)&1][2];
    for (int i = 1; i <= n-m-1; i++)
        ans = (ans<<1)%P;
    return printf("%d\n", ans), 0;
}