Submission #36264066

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353;
vector<int> c = {1, 2, 3, 2, 1};
int main(){
  int N, M;
  cin >> N >> M;
  int mx = N + M / 3;
  vector<long long> inv(mx + 1);
  inv[1] = 1;
  for (int i = 2; i <= mx; i++){
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
  }
  vector<long long> fact(mx + 1);
  vector<long long> finv(mx + 1);
  fact[0] = 1;
  finv[0] = 1;
  for (int i = 1; i <= mx; i++){
    fact[i] = fact[i - 1] * i % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
  vector<long long> f(N * 2 + 3, 0);
  for (int i = 0; i <= N - 1; i++){
    for (int j = 0; j < 5; j++){
      f[i + j + N - 1] += fact[N - 1] * finv[i] % MOD * finv[N - 1 - i] % MOD * c[j];
      f[i + j + N - 1] %= MOD;
    }
  }
  vector<long long> g(M + 1, 0);
  for (int i = 0; i * 3 <= M; i++){
    g[i * 3] = fact[i + N] * finv[i] % MOD * finv[N] % MOD;
  }
  long long ans = 0;
  for (int i = 0; i <= N * 2 + 2; i++){
    if (i <= M){
      ans += f[i] * g[M - i] % MOD;
    }
  }
  ans %= MOD;
  cout << ans << endl;
}

Submission Info

Submission Time
Task G - Count Sequences
User SSRS
Language C++ (GCC 9.2.1)
Score 600
Code Size 1092 Byte
Status AC
Exec Time 1005 ms
Memory 550272 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 49
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_smallNM_00.txt, 01_smallNM_01.txt, 01_smallNM_02.txt, 01_smallNM_03.txt, 01_smallNM_04.txt, 01_smallNM_05.txt, 01_smallNM_06.txt, 01_smallNM_07.txt, 01_smallNM_08.txt, 01_smallNM_09.txt, 01_smallNM_10.txt, 01_smallNM_11.txt, 02_smallN_00.txt, 02_smallN_01.txt, 02_smallN_02.txt, 02_smallN_03.txt, 02_smallN_04.txt, 02_smallN_05.txt, 02_smallN_06.txt, 03_rnd_00.txt, 03_rnd_01.txt, 03_rnd_02.txt, 03_rnd_03.txt, 03_rnd_04.txt, 03_rnd_05.txt, 03_rnd_06.txt, 03_rnd_07.txt, 04_max_00.txt, 04_max_01.txt, 04_max_02.txt, 04_max_03.txt, 04_max_04.txt, 04_max_05.txt, 04_max_06.txt, 04_max_07.txt, 04_max_08.txt, 04_max_09.txt, 04_max_10.txt, 04_max_11.txt, 04_max_12.txt, 04_max_13.txt, 04_max_14.txt, 04_max_15.txt, 04_max_16.txt, 04_max_17.txt, 04_max_18.txt, 04_max_19.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 8 ms 3420 KiB
00_sample_01.txt AC 186 ms 159332 KiB
01_smallNM_00.txt AC 1 ms 3556 KiB
01_smallNM_01.txt AC 2 ms 3516 KiB
01_smallNM_02.txt AC 1 ms 3600 KiB
01_smallNM_03.txt AC 2 ms 3588 KiB
01_smallNM_04.txt AC 1 ms 3412 KiB
01_smallNM_05.txt AC 2 ms 3544 KiB
01_smallNM_06.txt AC 2 ms 3596 KiB
01_smallNM_07.txt AC 2 ms 3464 KiB
01_smallNM_08.txt AC 2 ms 3604 KiB
01_smallNM_09.txt AC 2 ms 3544 KiB
01_smallNM_10.txt AC 2 ms 3600 KiB
01_smallNM_11.txt AC 1 ms 3500 KiB
02_smallN_00.txt AC 191 ms 159444 KiB
02_smallN_01.txt AC 183 ms 159552 KiB
02_smallN_02.txt AC 187 ms 159412 KiB
02_smallN_03.txt AC 187 ms 159460 KiB
02_smallN_04.txt AC 184 ms 159552 KiB
02_smallN_05.txt AC 194 ms 159444 KiB
02_smallN_06.txt AC 187 ms 159444 KiB
03_rnd_00.txt AC 639 ms 360792 KiB
03_rnd_01.txt AC 250 ms 161960 KiB
03_rnd_02.txt AC 551 ms 303084 KiB
03_rnd_03.txt AC 635 ms 363996 KiB
03_rnd_04.txt AC 396 ms 223488 KiB
03_rnd_05.txt AC 411 ms 262692 KiB
03_rnd_06.txt AC 631 ms 343052 KiB
03_rnd_07.txt AC 207 ms 134844 KiB
04_max_00.txt AC 1005 ms 550116 KiB
04_max_01.txt AC 594 ms 354864 KiB
04_max_02.txt AC 387 ms 257076 KiB
04_max_03.txt AC 278 ms 208232 KiB
04_max_04.txt AC 232 ms 183680 KiB
04_max_05.txt AC 979 ms 550272 KiB
04_max_06.txt AC 972 ms 550032 KiB
04_max_07.txt AC 974 ms 550180 KiB
04_max_08.txt AC 990 ms 550044 KiB
04_max_09.txt AC 979 ms 550136 KiB
04_max_10.txt AC 971 ms 550164 KiB
04_max_11.txt AC 978 ms 550052 KiB
04_max_12.txt AC 971 ms 550080 KiB
04_max_13.txt AC 973 ms 550040 KiB
04_max_14.txt AC 969 ms 550040 KiB
04_max_15.txt AC 971 ms 550272 KiB
04_max_16.txt AC 976 ms 550112 KiB
04_max_17.txt AC 972 ms 550184 KiB
04_max_18.txt AC 977 ms 550168 KiB
04_max_19.txt AC 973 ms 550032 KiB