ZigZagK的博客
[计数+DP]2020 CCPC 秦皇岛站 H【Holy Sequence】题解
2020年10月29日 19:49
CCPC
查看标签

题目概述

一个合法的整数数列 $\{a_n\}$ 需要满足:

  1. $1\le a_i\le n$ 。
  2. 令 $p_i=\max\{a_k|1\le k\le i\}$ ,则 $p_i\le p_{i-1}+1$

对于所有 $t\in[1,n]$ ,求 $\sum_{a}cnt(a,t)^2$ ,其中 $cnt(a,t)$ 表示 $t$ 在一个合法数列 $a$ 中的出现次数。

解题报告

首先有个套路,$cnt(a,t)^2$ 可以理解为 $t$ 在 $a$ 中可重复的选择两次

根据上面的要求,我们可以定义一个 $f_{i,j}$ 表示前 $i$ 个中,$p_i=j$ 的方案数。

类似的定义一个 $g_{i,j}$ 表示倒着放 $i$ 个,且 $p_{n-i+1}=j$ 的方案数。

不难得出转移:

$$ f_{i,j}=j\cdot f_{i-1,j}+f_{i-1,j-1}\\ g_{i,j}=j\cdot g_{i-1,j}+g_{i-1,j+1} $$

为了避免重复,我们枚举 $t$ 在 $a$ 中的第一次出现的位置 $i$ ,那么前 $i-1$ 位的方案数就是 $f_{i-1,t-1}$ 。

由于 $i$ 位置已经确定放了 $t$ ,我们现在有 $4$ 种情况:

  1. $f_{i-1,t-1}\cdot g_{n-i,t}$ :两个 $t$ 都选 $i$ 。
  2. $2(n-i)f_{i-1,t-1}\cdot g_{n-i-1,t}$ :一个 $t$ 选 $i$ ,另一个 $t$ 不选 $i$ 。
  3. $(n-i)f_{i-1,t-1}\cdot g_{n-i-1,t}$ :两个 $t$ 都不选 $i$ ,且位置相同。
  4. $2{n-i\choose 2}f_{i-1,t-1}\cdot g_{n-i-2,t}$ :两个 $t$ 都不选 $i$ ,且位置不同。

由于 $i$ 位置开始已经有了 $t$ ,所以后面放 $t$ 是一定合法的,我们可以直接把后面放 $t$ 的位置无视掉。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=3000;

int te,n,MOD,f[maxn+5][maxn+5],g[maxn+5][maxn+5];

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
int main(){
    scanf("%d",&te);
    for (int t=1;t<=te;t++){
        scanf("%d%d",&n,&MOD);
        f[0][0]=1;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=i;j++)
                f[i][j]=ADD(f[i-1][j-1],MUL(f[i-1][j],j));
        for (int j=1;j<=n;j++) g[0][j]=1;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                g[i][j]=ADD(j<n?g[i-1][j+1]:0,MUL(g[i-1][j],j));
        printf("Case #%d:\n",t);
        for (int j=1,ans=0;j<=n;j++,ans=0){
            for (int i=j;i<=n;i++){
                int pre=f[i-1][j-1],suf=0;
                suf=ADD(suf,g[n-i][j]);
                if (i<n) suf=ADD(suf,MUL(g[n-i-1][j],n-i));
                if (i<n) suf=ADD(suf,MUL(g[n-i-1][j],n-i)<<1);
                if (i+1<n) suf=ADD(suf,MUL(g[n-i-2][j],(n-i)*(n-i-1)));
                ans=ADD(ans,MUL(pre,suf));
            }
            printf("%d",ans);j<n?putchar(' '):puts("");
        }
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!