题解：AT_abc457_f [ABC457F] Second Gap

· · 题解

计数好题！

先考虑 O(n^2) 的 DP。设 dp_{i,j} 表示考虑以 i 为开头的后缀，最大值在 j 的方案数：那么我们有：

dp_{i,i}=dp_{i,i+d_i}=dp_{i+1,i+d_i}

两个状态分别表示 i 为最大值与次大值。此外，若 d_i=d_{i+1}：

dp_{i,j}=dp_{i+1,j} \times (n-i-1)

表示 i 小于次大值，可以是第三至第 n-i+1 大，总共 n-i-1 种。

考虑优化。发现如果 d_i=d_{i+1}，则第二条方程相当于一次全局乘法，否则为全局清空。

那么我们全局乘法时打一个 tag，同时转移第一条的时候记录哪些位置不是 0，清空时只清这些位置就行了。由于第一条方程最多增加一个不是 0 的位置，所以复杂度是 O(n) 的。 :::success[code] 注意：由于我没有实现得太精细，需要 O(\log n) 的求逆元，所以我的代码是 O(n \log n) 的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define lowbit(x) ((x)&(-(x)))
const int N=3e5+10,mod=998244353;
int qpow(int a,int b)
{
    int s=1;
    while(b)
    {
        if(b&1) s=s*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return s;
}
int d[N];
int dp[N]; 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++) cin>>d[i];
    dp[n]=1;
    int ss=1,is=1;
    vector<int>vec;
    vec.push_back(n); 
    for(int i=n-1;i>=1;i--)
    {
        int p=i+d[i];
        int tx=dp[p];
        if(i!=n-1&&d[i]==d[i+1])
        {
            ss=ss*(n-i-1)%mod;
            is=is*qpow(n-i-1,mod-2)%mod;
            tx=tx*qpow(n-i-1,mod-2)%mod; 
        }
        else
        {
            for(auto v:vec) dp[v]=0;
            vec.clear();
        }
        dp[i]=(dp[i]+tx)%mod;
        dp[p]=(dp[p]+tx)%mod;
        vec.push_back(i);
        vec.push_back(p);
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[i])%mod; 
    cout<<ans*ss%mod;
    return 0; 
}

:::