题目概述

一个合法的整数数列 $\{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+1$ 个，且倒数第 $i+1$ 个 $p$ 为 $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;
}