题解：AT_abc457_f [ABC457F] Second Gap

· · 题解

Update on 2026/05/12: 代码贴错了，现在已经修正。

题意：对于一个长度为 n 的排列，对于每一个长度 >1 的后缀都要求最大值与次大值的位置的差 =d_i。问满足要求的排列数。对大素数 998244353 取余数。

我们先把序列反转一下，那么问题就变成前缀了，看起来舒服一点（笑）。

我们考虑 \rm {dp}，考虑要记录哪些状态。我们从左往右考虑前缀，假设现在考虑到前缀 1,\cdots,k。我们发现不需要记录每个值是什么，只需要记录前面 k 个值的大小关系，然后枚举第 k+1 个数在前面 k 个数中比几个大即可，这是做排列相关问题的一种常用方法。我们还可以观察到最大值和次大值一定都是不减的，所以我们只需要记录最大值位置，次大值位置就可以了，在转移的时候讨论三种情况：比最大值大，位于最大值和次大值中间，比次大值小。现在我们可以写出一个 \mathcal O(n^3) 的 \rm {dp}。

考虑进行优化。首先考虑缩减状态空间。我们发现次大值的位置不重要。因为在前两种情况中，次大值会被抛弃；在最后一种情况中，不会更新结果。因此我们永远不会利用到次大值的位置信息。这压根就得到了一个 \mathcal O(n^2) 的做法。这样状态数看起来不能再优化了。

然后我们考虑一下转移。记 f_{i,j} 为当前考虑 1,\cdots,i 前缀，最大值位置在 j 的方案数。显然边界情况是 f_{2,1}=f_{2,2}=1。我们先对三种情况写出转移的式子（假设下标都合法）：

然后我们考虑 f_{i,\cdot} 与 f_{i+1,\cdot}。可以发现，大部分下标的值都是统一地 \times (i-1) 或者不继承 f_{i,\cdot} 的值。因此我们可以考虑记 g_{i,x}=\frac{f_{i,x}}{(i-2)!}。这样转移就变成如下：

这个转移是好实现的。需要的转移数是 \mathcal O(n) 的，以下证明之：

::::info[时间复杂度证明] 我们考虑 p_i 为 \sum\limits_{x=1}^{i}[g_{i,x}\neq g_{i+1,x}]。那么我们需要的转移数不超过 \sum\limits_{i=2}^{n-1}p_i ::::

由于笔者使用 \rm map 实现，时间复杂度 \mathcal O(n\log n)，空间复杂度 \mathcal O(n)。当然从上面的分析可知，可以通过精细的实现将时间复杂度优化到 \mathcal O(n)。

以下给出笔者的 \rm cpp 代码实现。

::::info[代码]

#include<cstdio>
#include<algorithm>
#include<map>
const int mod=998244353;
int n,f[200005];
long long inv[200005],fac[200005],s=0;
std::map<int,long long> dp;
long long fp(long long x,int y){return !y?1:(y&1?x:1)*fp(x*x%mod,y/2)%mod;}
int main()
{
    scanf("%d",&n);
    for (int i=2;i<=n;i++) scanf("%d",&f[i]);
    std::reverse(f+2,f+n+1);
    if (f[2]!=1) return puts("0"),0;
    for (int i=1;i<=n;i++) inv[i]=fp(i,mod-2);
    fac[0]=1;for (int i=1;i<=n-2;i++) fac[i]=fac[i-1]*i%mod;
    dp[1]=dp[2]=1;
    for (int i=2;i<n;i++)
    {
        long long val=0;
        if (f[i+1]<(i+1)) val=dp[(i+1)-f[i+1]]*inv[i-1]%mod;
        if (f[i+1]!=f[i]) dp.clear();
        dp[(i+1)-f[i+1]]=(dp[(i+1)-f[i+1]]+val)%mod;
        dp[i+1]=(dp[i+1]+val)%mod;
    }
    for (int i=1;i<=n;i++) s=(s+dp[i])%mod;
    s=s*fac[n-2]%mod;
    printf("%lld\n",s);
    return 0;
}

::::