Submission #69684796

---

Source Code Expand

// Problem: 'E - Count Sequences 2'
// Contest: 'AtCoder - UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 425)'
// URL: 'https://atcoder.jp/contests/abc425/tasks/abc425_e'
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by competitive-companion.el (https://github.com/luishgh/competitive-companion.el)

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 5e3 + 10;

int choose[MAX][MAX];

int m;

ll add(ll a, ll b) {
  ll r = a + b;
  if (r < 0) r += m;
  else if (r >= m) r -= m;
  return r;
}

ll mul(ll a, ll b) {
  return a * b % m;
}

ll fexp(ll a, ll b) {
  ll r = 1;
  while (b) {
    if (b&1) r = mul(r, a);
    a = mul(a, a);
    b >>= 1;
  }
  return r;
}

void solve() {
  int n; cin >> n;
  vector<int> c(n);
  ll tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> c[i];
    tot += c[i];
  }

  ll ans = 1;
  ll pref = 0;

  for (int i = 0; i < n; i++) {
    ans = mul(ans, choose[tot - pref][c[i]]);
    // cerr << i << ' ' << tot - pref << ' ' << c[i] << ' ' << choose[tot-pref][c[i]] << endl;
    pref += c[i];
  }
  cout << ans << endl;
}

int main() {_;
  int t; cin >> t;

  cin >> m;

  for (int i = 0; i < MAX; i++) {
    choose[i][0] = 1;
    for (int j = i + 1; j < MAX; j++)
      choose[i][j] = 0;
  }

  for (int i = 1; i < MAX; i++) {
    for (int j = 1; j < MAX; j++) {
      choose[i][j] = add(choose[i-1][j-1], choose[i-1][j]);
    }
  }


  while (t--) {
    solve();
  }

  return 0;
}

Submission Info

Judge Result