結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー vjudge1
提出日時 2026-02-16 17:54:38
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 1,857 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,965 ms
コンパイル使用メモリ 218,964 KB
実行使用メモリ 10,208 KB
最終ジャッジ日時 2026-02-16 17:54:44
合計ジャッジ時間 5,412 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 2 WA * 34
権限があれば一括ダウンロードができます

ソースコード

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 T,op,n,i,ok,x,tot;
	ll fz,fm;
	scanf("%d%d",&T,&op);
	while(T--)
	{
		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;
		}
		l[0]=0;
		r[0]=1;
		l[n+1]=n;
		r[n+1]=n+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");
			continue;
		}
		if(op==0)
		{
			puts("1");
			continue;
		}
		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=fz*i%mod;
			fm=fm*sz[i]%mod;
		}
		printf("%lld\n",fz*inv(fm)%mod);
	}
	return 0;
}
/*
5
0 2 2 0 1
ans=4

5
0 3 0 2 0
ans=8
*/
0