题解：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

种情况。

CPP

#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;
}

题解：AT_arc206_c [ARC206C] Tree Sequence

文章操作

相关推荐

评论

题解：AT_arc206_c [ARC206C] Tree Sequence