#890995 (C++17) No.2383 Naphthol

• 問題: No.2383 Naphthol
• ユーザー: 沙耶花
• 提出日時: 2023-07-14 21:48:52
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 25 ms / 2,000 ms
• コード長: 1,909 bytes
• コンパイル時間: 4,704 ms
• コンパイル使用メモリ: 262,180 KB
• 最終ジャッジ日時: 2025-02-15 13:55:51
• ジャッジサーバーID （参考情報）: judge2 / judge2

ファイルパターン	結果
sample	AC * 3
other	AC * 18

ソースコード

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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <stdio.h>
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define Inf32 1000000001
#define Inf64 4000000000000000001
struct combi{
    deque<mint> kaijou;
    deque<mint> kaijou_;
    
    combi(int n){
        kaijou.push_back(1);
        for(int i=1;i<=n;i++){
            kaijou.push_back(kaijou[i-1]*i);
        }
        
        mint b=kaijou[n].inv();
        
        kaijou_.push_front(b);
        for(int i=1;i<=n;i++){
            int k=n+1-i;
            kaijou_.push_front(kaijou_[0]*k);
        }
    }
    
    mint combination(int n,int r){
        if(r>n)return 0;
        if(r<0)return 0;
        mint a = kaijou[n]*kaijou_[r];
        a *= kaijou_[n-r];
        return a;
    }
    
    mint junretsu(int a,int b){
        mint x = kaijou_[a]*kaijou_[b];
        x *= kaijou[a+b];
        return x;
    }
    
    mint catalan(int n){
        return combination(2*n,n)/(n+1);
    }
    
};
combi C(1000000);
vector<int> get(vector<int> t){
    vector<int> ret = t;
    rep(i,2){
        rep(j,10){
            t.push_back(t[0]);
            t.erase(t.begin());
            ret = min(ret,t);
        }
        reverse(t.begin(),t.end());
    }
    return ret;
}
int main(){
    
    int N,K;
    cin>>N>>K;
    
    if(N==1){
        set<vector<int>> S;
        rep(i,1<<6){
            if(__builtin_popcount(i)!=K)continue;
            vector<int> t(6);
            rep(j,6)t[j] = (i>>j)&1;
            S.insert(get(t));
        }
        cout<<S.size()<<endl;
    }
    else{
        mint ans = 0;
        //不動
        ans += C.combination(2*N+4,K);
        //上下
        if(K%2==0)ans += C.combination(N+2,K/2);
        //左右
        if(N%2==1){
            rep(i,2){
                rep(j,2){
                    int k = K-i-j;
                    if(k%2==1)continue;
                    k /= 2;
                    rep(l,N/2+2){
                        ans += C.combination(N/2+1,l) * C.combination(N/2+1,k-l);
                    }
                }
            }
        }
        else{
            int k = K;
            if(k%2==0){
                k /= 2;
                rep(l,N/2+2){
                    ans += C.combination(N/2+1,l) * C.combination(N/2+1,k-l);
                }
            }
        }
        
        //上下左右
        if(K%2==0)ans += C.combination(N+2,K/2);
        
        ans /= 4;
        cout<<ans.val()<<endl;
    }
    
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX