[yYOI] 小 y 的排列 题解

Cindy_Li · 2024-09-28 11:26:21 · 个人记录

发现“好的”标准比较松，维护还需要分类，但是“不好”需满足 a_{i-1}<a_i>a_{i+1}，比较严格。

正难则反，考虑“不好”的位置有什么关系。

如果我们从小到大插入数字，显然要满足上述条件，就要求 a_i 后插入。

这就是明显的无后效性，考虑 dp。

设 f[i][j] 表示当前插入了 1\rightarrow i-1，”不好“的位置有 j 个的方案数。

考虑插入一个新数字 i 对答案的影响。

• 没有插入在这 j 个位置的两侧，由于两边的数一定比 i 小（认为两头都是 0 ），更新 f[i][j]\times(i-2j)\rightarrow f[i+1][j+1]。

• 插入在这 j 个位置两侧（注意到这 j 个位置一定不相邻），原来”不好“的数变好了，但 i 成为了新的”不好“的数，更新 f[i][j]\times 2j \rightarrow f[i+1][j]。

初值 f[1][0]=1，答案 \sum_{i=0}^{n-k}f[n+1][i]。

预处理 f，对每个询问直接输出答案。

复杂度 O(n^2)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define LL long long

const int N=3005;
const LL mod=1e9+7;
inline LL pls(LL a,LL b){
    return (a+b>=mod? a+b-mod:a+b);
}
inline LL mul(LL a,LL b){
    return a*b%mod;
}
LL f[N][N];

int Q,n,k;
int main(){
    f[1][0]=1;
    rep(i,1,3001) rep(j,0,i/2){
        f[i+1][j+1]=pls(f[i+1][j+1],mul(f[i][j],i-2*j));
        f[i+1][j]=pls(f[i+1][j],mul(f[i][j],2*j));
    }

    cin>>Q;
    rep(q,1,Q){
        cin>>n>>k;
        LL ans=0;
        rep(i,0,n-k) ans=pls(ans,f[n+1][i]);
        printf("%lld\n",ans);
    }
    return 0;
}