#891165 (C++23) No.2383 Naphthol

• 問題: No.2383 Naphthol
• ユーザー: butsurizuki
• 提出日時: 2023-07-14 22:07:40
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 20 ms / 2,000 ms
• コード長: 2,511 bytes
• コンパイル時間: 2,877 ms
• コンパイル使用メモリ: 245,824 KB
• 実行使用メモリ: 19,876 KB
• 最終ジャッジ日時: 2024-09-16 07:10:15
• 合計ジャッジ時間: 3,996 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include<bits/stdc++.h>
using namespace std;
//
// string gen(int x,int n){
//   string res;
//   for(int i=0;i<n;i++){
//     if(x%2){res.push_back('1');}
//     else{res.push_back('0');}
//     x/=2;
//   }
//   return res;
// }
//
// string half(int n,string s){
//   string res;
//   for(int i=0;i<n;i++){
//     res.push_back(s[(i+(n/2))%n]);
//   }
//   return res;
// }
//
// int main(){
//   for(int n=1;n<=8;n++){
//     cout << "n = " << n << " : ";
//     set<string> st;
//     vector<int> bk(2*n+4+1,0);
//     for(int i=0;i<(1<<(2*n+4));i++){
//       string s=gen(i,2*n+4);
//       if(st.find(s)!=st.end()){continue;}
//       bk[__builtin_popcount(i)]++;
//       string hs=half(2*n+4,s);
//       st.insert(s);
//       st.insert(hs);
//       reverse(s.begin(),s.end());
//       reverse(hs.begin(),hs.end());
//       st.insert(s);
//       st.insert(hs);
//     }
//     for(auto &nx : bk){cout << nx << " ";}cout << "\n";
//   }
//   return 0;
// }
#define mod 998244353
#define FACSIZE 1048576
long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}
long long modular_inverse(long long n){
  return power(n,mod-2);
}
long long factorial[FACSIZE];
long long invfact[FACSIZE];
void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<FACSIZE;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]);
  for(i=FACSIZE-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}
long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}
long long A226048(long long n,long long k){
  long long res;
  if(k%2==0){
    res=calcnCr(2*n,k);
    res+=3*calcnCr(n,k/2);res%=mod;
    res*=modular_inverse(4);res%=mod;
  }
  else{
    res=calcnCr(2*n,k);
    if(n%2){
      res+=2*calcnCr(n-1,(k-1)/2);
    }
    res*=modular_inverse(4);res%=mod;
  }
  return res;
}
int main(){
  cfact();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  long long n,k;
  cin >> n >> k;
  if(n==1){
    if(k==1){
      cout << "1\n";
    }
    if(k==2){
      cout << "3\n";
    }
    if(k==3){
      cout << "3\n";
    }
    if(k==4){
      cout << "3\n";
    }
    if(k==5){
      cout << "1\n";
    }
    if(k==6){
      cout << "1\n";
    }
    return 0;
  }
  cout << A226048(n+2,k) << "\n";
  return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX