题解：AT_arc206_c [ARC206C] Tree Sequence

· · 题解

我们考虑最小的组合：[a_i,a_{i+1}]，那么一定有一个 a_i=i+1 或者是 a_{i+1}=i。我们令 a_i=i+1 为 R，a_{i}=i-1 为 L，否则为 X。那么序列会形如若干个 R，零或一个 X，若干个 L 组成。

我们来看一些特殊的情况，比如在出现 L 之后出现了 R，那么就证明这个序列改不好了。答案为 0。如果给出的序列里面有出现 X，那么就只能老实左边全填 R 右边全填 L 了。如果这个 X 出现在两侧（不一定相邻）都有 R 或者都有 L 的地方，那么也是不行的，因为不符合我们推出来的结论。

那么我们首先 X 能出现的地方是最后一个 R 的后面（记作 l）以及第一个 L 前面（记作 r）。考虑出现过 X 时，要保证 X 不会变成 L 和 R，那么每个位置有 n-2 种情况。这里情况总数为 (n-2)(r-l+1)。

其次考虑 X 变成 L 或 R，考虑这个区间里能出现 [0,r-l+1] 个 L，因为 L 连续，则这里有 (r-l+2) 种情况。

合并一下变成 (n-1)(r-l+1)+1 种情况。

#include<bits/stdc++.h>

#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
    for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

#define maxn 200050

int n,a[maxn];

void work() {
    in1(n);
    For(i,1,n) in1(a[i]);
    int l=0,r=n+1,flg=0;
    For(i,1,n) {
        if(a[i]==-1) continue;
        if(i<a[i]) l=max(l,i);
        if(i>a[i]) r=min(r,i);
        if(abs(i-a[i])!=1) {
            if(!flg) flg=i;
            else return cout<<0,void();
        }
    }
    if(flg) return cout<<(l<=flg&&flg<=r),void();
    else if(l>r) return cout<<0,void();
    cout<<(1ll*(r-l-1)*(n-1)+1)%mod;
}

signed main() {
//  freopen("data.in","r",stdin);
//  freopen("myans.out","w",stdout);
//  ios::sync_with_stdio(false); 
//  cin.tie(0); cout.tie(0);
    double stt=clock();
    int _=1;
//  _=read();
//  cin>>_;
    For(i,1,_) {
        work();
    }
    cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
    return 0;
}