Submission #17992965

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, X;
vector<ll> A(60, 0);
const ll M = 100000;
ll memo[60][M] = {};
ll cnt(ll index, ll zan) {
  if (zan < M && memo[index][zan] > 0) return memo[index][zan];
  if (index == 0) return 1;
  if (zan == 0) return 1;
  ll temp = zan / A[index];
  ll zan1 = zan - A[index] * temp;
  ll zan2 = abs(zan - A[index] * (temp + 1));
  ll ans;
  if (temp == 0 && index != N - 1) ans = cnt(index - 1, zan1);
  else if (zan1 == 0) ans = cnt(index - 1, zan2);
  else if (zan2 == 0) ans = cnt(index - 1, zan1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, X;
vector<ll> A(60, 0);
const ll M = 100000;
ll memo[60][M] = {};

ll cnt(ll index, ll zan) {
  if (zan < M && memo[index][zan] > 0) return memo[index][zan];
  if (index == 0) return 1;
  if (zan == 0) return 1;
  ll temp = zan / A[index];
  ll zan1 = zan - A[index] * temp;
  ll zan2 = abs(zan - A[index] * (temp + 1));

  ll ans;
  if (temp == 0 && index != N - 1) ans = cnt(index - 1, zan1);
  else if (zan1 == 0) ans = cnt(index - 1, zan2);
  else if (zan2 == 0) ans = cnt(index - 1, zan1);
  else ans = cnt(index - 1, zan1) + cnt(index - 1, zan2);
  if (zan < M) memo[index][zan] = ans;
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  cin >> N;
  cin >> X;
  for (ll i = 0; i < N; i++) {
    cin >> A[i];
  }
  ll ans = cnt(N - 1, X);
  cout << ans << '\n';
  return 0;
}

Submission Info

Judge Result