感谢大哥送来的 Fe

· · 题解

赛时送我打铁的一道题，写篇题解纪念一下。

特殊性质 A：所有 p_i=0

考虑序列 dp，记 f_{i,j} 为在 [1,i] 的一段前缀中第 i 个数的排名（以下排名均为从大到小）的幸运值之和，可以轻松得出转移方程：

f_{i,j}= \sum_{k=j+1}^i f_{i-1,k}\times w_{i-1}~+\sum_{k=1}^j f_{i-1,k}

由于我们最终的形态是一个排列，每一种局面到最后都会对应唯一的一种状态，这样做就可以做到不重不漏。

正解

我们记第 i 个位置往前的第一个有值 p_i 为 l_i

由于题面保证存在的 l_i 单调递增，我们肯定要做序列 dp，考虑延续特殊性质 A 的做法，尝试对于每一个 l_i 更新钦定当前有多少个数小于他。但这样很明显是错误的，因为我们无法保证最终对于每一个有值的相邻 p_i 之间的数有恰好 p_i-p_{i-1} 个值。

如何解决？我们可以记录有多少个已填入的数大于 l_i，记这个数为 j。

通过一些简单的计算可以得出有多少个小于 l_i 的可填入数的个数，这样我们就可以避免出现相邻的 l_i 之间填不齐的情况了。

当然我们还需要知道填入的数之间的相对大小来进行转移。

如果一个数小于 l_i，我们需要知道小于当前数的可填入数的个数来获取他的相对大小，记这个数为 k。

如果一个数大于 l_i，我们就不关心他的具体数值是什么了，我们可以像再特殊性质 A 中一样，仅通过记录他的排名来获取信息，记他的排名也为 k。

当 l_i\to l_{i+1} 时，我们就可以钦定当前有多少个大于 l_{i} 数小于 l_{i+1}，类似于下图的过程：

这时我们需要钦定 j-k 个数的位置，也就是乘上一个 \binom{j-k}{l_i-l_{i-1}-1}。

至此我们发现所有的转移都可以使用前缀和优化，时间复杂度 O(n^3)。

具体实现见代码。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=505;

int p[N],w[N];
int C[N][N];
int f[2][N][N],g[2][N][N];
//f:当前填的数比l_i大 g:当前填的数比l_i小
//第i个数 存在j个数比lim_i大 f:当前数的排名 g:比当前数还小的能填的数的个数
int num[N],L[N],R[N];
int sum[N];

int ascend(int c,int n,int m,vector<int> P,vector<int> W)
{
    const int MOD=m;
    auto add=[&](int &x,const int &y)
    {x=x+y>=MOD?x+y-MOD:x+y;};
    for(int i=1;i<=n;i++) 
        p[i]=P[i-1],w[i]=(W[i-1]-1+MOD)%MOD;
    for(int i=1;i<=n;i++)
    {
        if(p[i]) L[i]=p[i];
        else L[i]=L[i-1];
        R[i]=R[i-1]+(p[i]==0);
        num[i]=L[i]-i;
//      cout<<R[i]<<" "<<lim[i]<<'\n';
    }
    C[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        C[i][0]=1,C[i][1]=i;
        for(int j=2;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%MOD;
    }
    memset(f,0,sizeof f);
    memset(g,0,sizeof g);
    if(p[1]) g[1][0][p[1]-1]=1;
    else f[1][1][1]=1;
    for(int i=2;i<=n;i++)
    {
        int now=i&1,pre=now^1;
        memset(f[now],0,sizeof f[now]);
        memset(g[now],0,sizeof g[now]);
        if(p[i])
        {
            for(int j=0;j<=R[i];j++)
            {
                for(int k=0;k<=j+1;k++) sum[k]=0;
                for(int k=0;k<=num[i-1]+j;k++) add(sum[j+1],g[pre][j][k]);
                for(int k=j;k;k--) 
                    sum[k]=(sum[k+1]+f[pre][j][k])%MOD;
                for(int k=0;k<=j;k++)
                {
                    int les=p[i]-i+k;
                    if(j-k>p[i]-L[i-1]-1) continue;
                    int xs=C[p[i]-L[i-1]-1][j-k];
                    add(g[now][k][les],1ll*xs*((sum[1]+1ll*sum[k+1]*w[i-1]%MOD)%MOD)%MOD);
                }
            }
        }
        else
        {
            for(int j=0;j<=R[i];j++)
            {
                int lim=num[i]+j;
                if(lim+1<0) continue;
                //g -> g/f
                for(int k=0;k<=lim+1;k++) sum[k]=0;
                for(int k=0;k<=lim+1;k++) 
                    sum[k]=((k?sum[k-1]:0)+g[pre][j][k])%MOD;
                for(int k=0;k<=lim;k++)
                    add(g[now][j][k],(sum[lim+1]+1ll*sum[k]*w[i-1])%MOD);
                if(j!=R[i]) for(int k=1;k<=j+1;k++) 
                    add(f[now][j+1][k],1ll*sum[lim+1]*(w[i-1]+1)%MOD);
                //f -> g/f
                for(int k=0;k<=j+1;k++) sum[k]=0;
                for(int k=j;k;k--) 
                    sum[k]=(sum[k+1]+f[pre][j][k])%MOD;
                for(int k=0;k<=lim;k++)
                    add(g[now][j][k],sum[1]);
                if(j!=R[i]) for(int k=1;k<=j+1;k++)
                    add(f[now][j+1][k],(sum[1]+1ll*sum[k]*w[i-1])%MOD);
            }
        }
    }
    int res=g[n&1][n-L[n]][0];
    for(int i=1;i<=n-L[n];i++)
        add(res,f[n&1][n-L[n]][i]);
    return res;
}