题目内容

给定 n(n\leq20),求 n 个不同大小元素大小大小错位排列的方案数

解题思路

不妨从小问题开始考虑起,考虑我们已经摆好了前 i-1 个元素,现在要摆最大的第 i 个元素。显然,它前面的两个元素必须是高-低型的,后面的两个元素必须是低-高型的。

所以设 f_{i,0}i 个元素最后两个为高低的方案数,f_{i,1} 表示开头两个是低高的方案数。

转移时从 0i-1 循环,表示 i 插入时前面的元素个数,那么显然后面的元素就有 i-j-1 个。前面 j 个元素的组合应有 \binom {i-1}{j} 种。那么 i 个元素的总方案数应为

ans_i=\sum_{0\leq j<i}\binom{i-1}j f_{j,0}f_{i-j-1,1}

同时我们也可以得到,f_{i,0}=f_{i,1}=\frac 1 2 ans_i,记得 n>1 时输出乘二即可。

边界条件为 f_{0,0}=f_{0,1}=f_{1,0}=f_{1,1}=1

不开 long long 会炸掉

#include <cstdio>
#include <cctype>
#include <cstring>

typedef unsigned long long ll;

inline ll read()
{
    char c = getchar();
    ll s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

ll f[21][2],c[21][21],p,d,n,cnt;

int main()
{
    for(int i=1;i<=20;i++)
    {
        c[i][0]=c[i][i]=1;
        for(int j=1;j<i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    }//提前处理组合数
    f[1][1]=f[0][1]=f[1][0]=f[0][0]=1;
    for(int i=2;i<=20;i++)
    {
        ll tot=0;//统计 i 个元素的总方案数
        for(int j=0;j<i;j++)
            tot+=f[j][0]*f[i-j-1][1]*c[i-1][j];
        f[i][0]=f[i][1]=tot/2;//除以二得到f数组
    }
    cnt=1;
    p=read();
    while(p--)
    {
        d=read(),n=read();
        if(n==1)
            printf("%lld 1\n",d);
        else
            printf("%lld %lld\n",d,f[n][0]<<1);//n>1 时输出乘二
    }
    return 0;
}
最后修改日期:2020年9月5日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。