結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー tokitsukaze
提出日時 2026-01-22 15:01:48
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 29 ms / 2,000 ms
コード長 1,600 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,163 ms
コンパイル使用メモリ 218,464 KB
実行使用メモリ 11,108 KB
最終ジャッジ日時 2026-01-22 15:01:52
合計ジャッジ時間 3,968 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const int MAX=2e5+10;
const int mod=998244353;
ll qpow(ll a,ll b)
{
	ll res=1;
	while(b>0)
	{
		if(b&1) res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll inv(ll x){return qpow(x,mod-2);}
int ord[MAX],id[MAX],fa[MAX],sz[MAX],to[MAX][2];
int a[MAX],l[MAX],r[MAX];
void del(int x)
{
	l[r[x]]=l[x];
	r[l[x]]=r[x];
}
int main()
{
	int n,i,ok,x,tot,fz,fm;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		l[i]=i-1;
		r[i]=i+1;
		fa[i]=0;
		sz[i]=1;
		to[i][0]=to[i][1]=-1;
	}
	queue<int> q;
	for(i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			q.push(i);
			del(i);
		}
	}
	ok=1;
	tot=0;
	while(!q.empty())
	{
		x=q.front();
		q.pop();
		ord[x]=++tot;
		id[tot]=x;
		if(l[x]>=1)
		{
			if(a[l[x]]==0)
			{
				ok=0;
				break;
			}
			to[x][0]=l[x];
			a[l[x]]--;
			if(a[l[x]]==0)
			{
				q.push(l[x]);
				del(l[x]);
			}
		}
		if(r[x]<=n)
		{
			if(a[r[x]]==0)
			{
				ok=0;
				break;
			}
			to[x][1]=r[x];
			a[r[x]]--;
			if(a[r[x]]==0)
			{
				q.push(r[x]);
				del(r[x]);
			}
		}
	}
	if(tot!=n) ok=0;
	if(ok==0)
	{
		puts("0");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		if(to[i][0]==-1 && to[i][1]==-1) continue;
		if(to[i][0]==-1) fa[i]=to[i][1];
		else if(to[i][1]==-1) fa[i]=to[i][0];
		else
		{
			if(ord[to[i][0]]<ord[to[i][1]]) fa[i]=to[i][0];
			else fa[i]=to[i][1];
		}
	}
	for(i=1;i<=n;i++) sz[fa[id[i]]]+=sz[id[i]];
	fz=fm=1;
	for(i=1;i<=n;i++)
	{
		fz=1LL*fz*i%mod;
		fm=1LL*fm*sz[i]%mod;
	}
	printf("%lld\n",1LL*fz*inv(fm)%mod);
	return 0;
}
0