menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP]BZOJ4321【queue2】题解
apps BZOJ
local_offer 查看标签
comment 0 条评论

题目概述

求不存在 $|a_i-a_{i+1}|=1,i<n$ 的 $n$ 的排列 $\{a_n\}$ 的个数。

解题报告

定义 $f_{i,j,0/1}$ 表示前 $i$ 个数,有 $j$ 个数相邻,其中 $i$ 是否和 $i-1$ 相邻的方案数,讨论一下就可以转移了。

这种套路好像被称为加强条件……就是自行加一个有 $m$ 个数相邻这个条件,发现更容易想。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000,MOD=7777777;

int n,f[maxn+5][maxn+5][2];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);f[1][0][0]=1;
    for (int i=2;i<=n;i++)
        for (int j=0,F;j<i;j++){
            if (F=f[i-1][j][0]){
                f[i][j+1][1]=ADD(f[i][j+1][1],F<<1);
                if (i-2-j>0) f[i][j][0]=ADD(f[i][j][0],MUL(F,i-2-j));
                if (j) f[i][j-1][0]=ADD(f[i][j-1][0],MUL(F,j));
            }
            if (F=f[i-1][j][1]){
                f[i][j][1]=ADD(f[i][j][1],F);
                f[i][j+1][1]=ADD(f[i][j+1][1],F);
                if (i-1-j>0) f[i][j][0]=ADD(f[i][j][0],MUL(F,i-1-j));
                if (j) f[i][j-1][0]=ADD(f[i][j-1][0],MUL(F,j-1));
            }
        }
    printf("%d\n",f[n][0][0]);return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up