5235. 【NOIP2017模拟8.7A组】好的排列

(File IO): input:permutation.in output:permutation.out

Time Limits: 1000 ms Memory Limits: 524288 KB Detailed Limits

Description

对于一个1->n的排列，定义A中的一个位置i是好的，当且仅当Ai-1>Ai 或者Ai+1>Ai。对于一个排列A，假如有不少于k个位置是好的，那么称A是一个好的排列。

现在有q个询问，每个询问给定n,k，问有多少排列是好的。答案对10^9+7取模。

Input

输入文件名为permutation.in。

首先输入q。

接下来输入q个询问n,k 。

Output

输出文件名为permutation.out。

输出q行，每行一个整数代表答案。

Sample Input

8

4 3

6 4

10 7

20 14

50 40

100 72

1000 900

3000 2000

Sample Output

8

448

1433856

868137807

908422882

609421284

150877522

216180189

Data Constraint

对于20%的数据，n<=10,q=1

对于40%的数据，n<=20,q=1

对于60%的数据，n<=100

对于100%的数据，n,k<=3000,q<=10000

题解

dp题

题目中好处定义是当且仅当Ai−1>Ai 或者Ai+1>Ai

这个不好处理

我们可以转化成坏处为当且仅当Ai−1<Ai>Ai+1

用f[i][j]表示前i个恰有j个坏处的排列数

如果第i个作为坏处，那么它可以放在任何原本不是坏处的两边

f[i−1][j−1]∗(i−j)∗2 −> f[i][j]

如果第i个不作为坏处，那么它可以放在原本的坏处的两边

f[i−1][j]∗(i−(i−1−j)∗2) −> f[i][j]

答案就是

∑i=mnf[n][i]

代码

#include<cstdio>

#include<algorithm>

#define mo 1000000007

#define Q 10010

#define N 3010

long n[Q],m[Q];

long long f[N][N];

int main()

{   long tot,i,j,ans,maxn=0,maxm=0;

    freopen("permutation.in","r",stdin);

    freopen("permutation.out","w",stdout);

    scanf("%ld",&tot);

    for(i=1;i<=tot;i++){

        scanf("%ld%ld",&n[i],&m[i]);

        maxn=std::max(maxn,n[i]);

        maxm=std::max(maxm,m[i]);

    }

    f[1][0]=1;

    for(i=2;i<=maxn;i++)

        for(j=1;j<i;j++){

            f[i][j]=(f[i-1][j-1]*(i-j)*2%mo+f[i-1][j]*(i-(i-1-j)*2)%mo)%mo;

        }

    for(i=1;i<=tot;i++){

        ans=0;

        for(j=n[i];j>=m[i];j--)

            ans=(ans+f[n[i]][j])%mo;

        printf("%ld\n",ans);

    }

    return 0;

}

巴特西

JZOJ 5235. 【NOIP2017模拟8.7A组】好的排列