Submission #50246111

---

Source Code Expand

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
#define int long long
using namespace std;
inline int read() {
  int x = 0; bool op = false;
  char c = getchar();
  while(!isdigit(c))op |= (c == '-'), c = getchar();
  while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
  return op ? -x : x;
}
const int N = 2e3 + 10;
const int P = 998244353;
void add(int &a, int b) {a += b; a >= P ? a -= P : 0;}
void sub(int &a, int b) {a -= b; a < 0 ? a += P : 0;}
int ksm(int x, int k) {
  int res = 1;
  for(int pw = x; k; (k & 1) ? res = 1ll * res * pw % P : 0, pw = 1ll * pw * pw % P, k >>= 1);
  return res;
}
int n, m;
int a[N], f[N], sf[N], fac[N], ifac[N];
void init() {
  fac[0] = ifac[0] = 1;
  for(int i = 1; i < N; i++)fac[i] = 1ll * fac[i - 1] * i % P;
  ifac[N - 1] = ksm(fac[N - 1], P - 2);
  for(int i = N - 2; i; i--)ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
  return ;
}
int pre[N], suf[N];
int calc(int x, int n) {
  if(x <= n)return sf[x];
  pre[0] = suf[n + 1] = 1;
  for(int i = 1; i <= n; i++)pre[i] = suf[i] = (x - i) % P;
  for(int i = 1; i <= n; i++)pre[i] = 1ll * pre[i - 1] * pre[i] % P;
  for(int i = n; i; i--)suf[i] = 1ll * suf[i + 1] * suf[i] % P;
  int res = 0;
  for(int i = 1; i <= n; i++) {
    int c1 = 1ll * ifac[i - 1] * ifac[n - i] % P;
    int c2 = 1ll * pre[i - 1] * suf[i + 1] % P;
    int val = 1ll * c1 * c2 % P * sf[i] % P;
    ((n - i) & 1) ? sub(res, val) : add(res, val);
  }
  return res;
} 
signed main() {
  init();
  n = read(); m = read();
  for(int i = 1; i <= n; i++)a[i] = read();
  int lim = m;
  for(int i = 1; i <= min(lim, n + 2); i++)f[i] = 1;
  for(int i = n; i; i--) {
    for(int j = 1; j <= min(lim, n + 2); j++)sf[j] = (sf[j - 1] + f[j]) % P;
    int val = calc(lim, n + 2); lim /= a[i]; 
    // cout << i << ' ' << val << ' ' << lim << endl;
    for(int j = 1; j <= min(lim, n + 2); j++)f[j] = (val - calc(j * a[i] - 1, n + 2) + P) % P;
    // for(int j = 1; j <= min(lim, n + 10); j++)printf("%lld ", f[j]); putchar('\n');
  }
  for(int j = 1; j <= min(lim, n + 2); j++)sf[j] = (sf[j - 1] + f[j]) % P;
  printf("%lld\n", calc(lim, n + 2));
  return 0;
}

Submission Info

Judge Result