結果

問題 No.2605 Pickup Parentheses
ユーザー kotatsugame
提出日時 2024-01-12 22:53:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 1,777 bytes
コンパイル時間 2,501 ms
コンパイル使用メモリ 117,352 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2024-09-30 06:28:48
合計ジャッジ時間 8,318 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 68
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cassert>
#include<atcoder/modint>
#include<atcoder/convolution>
using namespace std;
#include<vector>
template<typename T>
struct combination{
	vector<T>fac,ifac;
	combination(size_t N=0):fac(1,1),ifac(1,1)
	{
		make_table(N);
	}
	void make_table(size_t N)
	{
		if(fac.size()>N)return;
		size_t now=fac.size();
		N=max(N,now*2);
		fac.resize(N+1);
		ifac.resize(N+1);
		for(size_t i=now;i<=N;i++)fac[i]=fac[i-1]*i;
		ifac[N]=1/fac[N];
		for(size_t i=N;i-->now;)ifac[i]=ifac[i+1]*(i+1);
	}
	T factorial(size_t n)
	{
		make_table(n);
		return fac[n];
	}
	T invfac(size_t n)
	{
		make_table(n);
		return ifac[n];
	}
	T P(size_t n,size_t k)
	{
		if(n<k)return 0;
		make_table(n);
		return fac[n]*ifac[n-k];
	}
	T C(size_t n,size_t k)
	{
		if(n<k)return 0;
		make_table(n);
		return fac[n]*ifac[n-k]*ifac[k];
	}
	T H(size_t n,size_t k)
	{
		if(n==0)return k==0?1:0;
		return C(n-1+k,k);
	}
};
using mint=atcoder::modint998244353;
combination<mint>C;
mint cat[4<<17];
int N,M;
vector<mint>solve(vector<int>C,int sum)
{
	if(C.empty())return vector<mint>(1,mint::raw(1));
	else if(C.size()==1)
	{
		vector<mint>ret(sum+1);
		ret[0]=mint::raw(1);
		ret[sum]=mint(-cat[sum]);
		return ret;
	}
	vector<int>L,R;
	int Lsum=0,Rsum=0;
	for(int c:C)
	{
		if(Lsum<=Rsum)Lsum+=c,L.push_back(c);
		else Rsum+=c,R.push_back(c);
	}
	return atcoder::convolution(solve(L,Lsum),solve(R,Rsum));
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N>>M;
	for(int i=0;i<2<<17;i++)cat[i*2]=C.factorial(2*i)*C.invfac(i+1)*C.invfac(i);
	vector<int>len(M);
	int sum=0;
	for(int i=0;i<M;i++)
	{
		int l,r;cin>>l>>r;
		sum+=len[i]=r-l+1;
	}
	vector<mint>F=solve(len,sum);
	mint ans=0;
	for(int i=0;i<=sum;i++)
	{
		ans+=F[i]*cat[N-i];
	}
	cout<<ans.val()<<endl;
}
0