#943654 (C++14) No.2605 Pickup Parentheses

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX