HS
AFO
HS的博客
AT2301 Solitaire

题目链接

AtCoder Grand Contest 024 E
洛谷

题目描述

Snuke has decided to play with $ N $ cards and a deque (that is, a double-ended queue). Each card shows an integer from $ 1 $ through $ N $ , 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 $ 1 $ to $ N $ . Then, he will perform the following action $ N $ 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 $ K $ -th element is $ 1 $ . Print the answer modulo $ 10^{9}\ +\ 7 $ .

题目翻译

将1-n顺序加入双端队列(每次可加头可加尾),再删除(每次可删头可删尾),求有多少种删除序列,使得1是第k个被删的。

输入格式

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

输出格式

Print the answer modulo $ 10^9 \ + \ 7 $ .

输入输出样例

输入 #1

2 1

输出 #1

1

输入 #2

17 2

输出 #2

262144

输入 #3

2000 1000

输出 #3

674286644

说明/提示

$ 1\ \le \ K\ \le \ N\ \le \ 2000 $

分析

显然加入的序列一定是’V’字形,即中间的数字小,两侧的数字大。
设$f_{i,j}$表示考虑到第$i$个数,’V’右边最后取的数字为$j$。
转移
考虑如果取’V’右边的数字
$$
f_{i,j}=\sum_{k=j+1}^{n}f_{i-1,k}
$$
考虑如果取’V’左边的数字(注意这里我们并不需要知道究竟取的是哪个数字,反正是剩下的数字中最大的那个)。
$$
f_{i,j}=f_{i-1,j}
$$
最后我们钦定第$K$个是在’V’右边取到的,反正左边翻转一下就行了。
剩下的$n-K$个数字,$b-K-1$个可以从两边取,最后一个只有一种取法,乘上方案数。
直接暴力转移$O(n^3)$,前缀优化一下就$O(n^2)$了。

一些对我而言的坑

  • $n-K-1$可能$<0$。

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 2010
const int p=1e9+7;
template <typename T>inline T read()
{
    register T sum=0;
    register char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,K,f[maxn];
void Add(int &x,int y)
{
    x+=y;
    if(x>=p)
        x-=p;
}
int mul(int x,int y)
{
    return 1ll*x*y%p;
}
int fpow(int x,int y)
{
    if(y<0)return 1;
    int res=1;
    while(y)
    {
        if(y&1)
            res=mul(res,x);
        x=mul(x,x);
        y>>=1;
    }
    return res;
}
int main()
{
    read(n,K);
    f[n+1]=1;
    for(int i=1;i<=K;i++)
    {
        for(int j=n;j>=1;j--)
        {
            if(n-j+1>=i)
                Add(f[j],f[j+1]);
            else
                f[j]=0;
        }
    }
    printf("%d\n",mul(f[1],fpow(2,n-K-1)));
    return 0;
}

Gluttony

文章作者

发表评论

textsms
account_circle
email

HS的博客

AT2301 Solitaire
前缀优化DP
扫描二维码继续阅读
2020-01-10