题解 1750G【Doping】

· · 题解

代数推导大脑报废，组合意义巧夺天工。

首先将划分为公差为一的等差数列变成 n 减去所有相邻且差为一的位置数。于是就只需统计相邻差为一的数目。

字典序的限制，不妨先暴力一点直接枚举公共前缀再枚举下一个元素。于是我们有一段后缀，其中元素均可以任意赋值；一段前缀，其中所有元素均已确定。

在值域轴上，前缀中已确定的部分占据了若干点。剩下的未使用元素凭借差一关系构成若干线段。

一个暴力的想法是，二项式反演，钦定若干差一元素必然相邻出现，于是已钦定的部分构成若干连续段，直接一个阶乘即得此时的方案数。除此之外，还要考虑已确定和未确定交界处的对的影响。

将问题抽象。我们可以用什么信息描述一个状态呢？

注意到对于固定的 i 来说，枚举下一个元素，对 j 的影响为不变或加一，对 k 的影响是不变、减一或减二。这意味着，至多仅有线性组不同的 (i,j,k,t)，可以对所有四元组各自考虑。

考虑分析 t 的影响。其事实上是将若干中情况的 j 加一，这个影响是可以在 j 中手动剔除、并贡献给 j+1 的，不在话下。现在仅需考虑 (i,j,k) 三元组。对其二项式反演是简单的，但是复杂度是平方的，无法承受。

考虑对数组 a_i 二项式反演得到 a_i' 的组合意义：在 (0,0) 处放置 a_0，在 (0,1) 处放置 a_1，……，在 (0,n) 处放置 a_n；我们令 向左走一步，权值取反；向上走一步，权值不变，以此在网格图上作路径计数；则，(i,i) 处的权值和，即为二项式反演后的 a'_i。我们有 a_p=(n-i-1-p)!\dbinom kp。

现在考虑 j 的影响，其是将 a_i' 作平移。将整个坐标系向右上平移一位，最终结果数组亦向右上平移一位。并且，这样平移后，对于不产生贡献的位置不会产生额外影响。故所有二项式反演数组可直接表示在同一坐标系上，一起二项式反演（也即路径计数）。

复杂度平方。

#include<bits/stdc++.h>
using namespace std;
int n,mod,fac[2010],a[2010];
bool occ[2010];
int arr[2010][2010];
int C[2010][2010];
int main(){
    scanf("%d%d",&n,&mod);
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
    for(int i=0;i<=n;i++)C[i][0]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=0,j=0,k=n-1;i<n;i++){
        int num[2][3][2];memset(num,0,sizeof(num));
        for(int t=1;t<a[i+1];t++)
            if(!occ[t]){
                int dj=(i&&(t==a[i]+1));
                int dk=0,dt=0;
                if(t>1&&!occ[t-1])dk++;
                if(t<n&&!occ[t+1])dk++,dt=1;
                num[dj][dk][dt]++;
            }
        for(int J=j;J<=j+1;J++)for(int K=k;K>=k-2;K--)for(int T=0;T<2;T++)if(num[J-j][k-K][T]){
            int val=num[J-j][k-K][T];
            // printf("%d %d %d %d:%d\n",i,J,K,T,val);
            for(int p=0;p<=K;p++)
                (arr[p+J][J]+=1ll*fac[(n-i-1)-p]*C[K][p]%mod*val%mod)%=mod;
            if(T){
                for(int p=0;p<=K;p++)
                    (arr[p+J][J]+=mod-1ll*fac[(n-i-1)-p-1]*C[K][p]%mod*val%mod)%=mod;
                for(int p=0;p<=K;p++)
                    (arr[p+J+1][J+1]+=1ll*fac[(n-i-1)-p-1]*C[K][p]%mod*val%mod)%=mod;
            }
        }
        j+=(i&&(a[i+1]==a[i]+1));
        k-=(a[i+1]>1&&!occ[a[i+1]-1]);
        k-=(a[i+1]<n&&!occ[a[i+1]+1]);
        occ[a[i+1]]=true;
    }
    // for(int j=n;j>=0;j--){for(int i=0;i<=n;i++)
    //  printf("%4d ",arr[i][j]);puts("");}
    for(int i=n;i>=0;i--)for(int j=0;j<=n;j++){
        (arr[i][j]+=mod-arr[i+1][j])%=mod;
        if(j)(arr[i][j]+=arr[i][j-1])%=mod;
    }
    for(int i=1;i<=n;i++)printf("%d ",arr[n-i][n-i]);puts("");
    return 0;
}