test/aoj/2446/main.test.cpp

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446

Depends on

• Fast Möbius transform (Subsets) (Mylib/Convolution/fast_mobius_transform_subset.cpp)
• Input vector (Mylib/IO/input_vector.cpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446"
#define ERROR 1e-7

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
#include "Mylib/Convolution/fast_mobius_transform_subset.cpp"
#include "Mylib/IO/input_vector.cpp"

namespace hl = haar_lib;

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

  int64_t n, m;
  std::cin >> n >> m;

  auto a = hl::input_vector<int64_t>(n);
  auto p = hl::input_vector<double>(n);

  for (auto &x : p) x /= 100.0;

  std::vector<int64_t> dp(1 << n);
  for (int i = 1; i < 1 << n; ++i) {
    int64_t l = 1;
    for (int j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        int64_t g = std::gcd(l, a[j]);

        long long int k;
        if (__builtin_smulll_overflow(l / g, a[j], &k)) {
          l = m + 1;
          break;
        }
        l = (l / g) * a[j];
      }
    }
    dp[i] = m / l;
  }

  dp = hl::fast_mobius_transform_subset(dp);

  double ans = 0.0;

  for (int i = 0; i < (1 << n); ++i) {
    double q = 1.0;
    for (int j = 0; j < n; ++j) {
      if (i >> j & 1)
        q *= p[j];
      else
        q *= 1.0 - p[j];
    }
    ans += q * std::abs(dp[i]);
  }

  std::cout << std::fixed << std::setprecision(12) << ans << std::endl;

  return 0;
}

#line 1 "test/aoj/2446/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446"
#define ERROR 1e-7

#include <iomanip>
#include <iostream>
#include <numeric>
#include <vector>
#line 2 "Mylib/Convolution/fast_mobius_transform_subset.cpp"
#include <cassert>
#include <functional>
#line 5 "Mylib/Convolution/fast_mobius_transform_subset.cpp"

namespace haar_lib {
  template <typename T, typename Func = std::minus<T>>
  std::vector<T> fast_mobius_transform_subset(std::vector<T> f, const Func &op = std::minus<T>()) {
    const int N = f.size();
    assert((N & (N - 1)) == 0 && "N must be a power of 2");
    for (int i = 1; i < N; i <<= 1) {
      for (int j = 0; j < N; ++j) {
        if (j & i) f[j] = op(f[j], f[j ^ i]);
      }
    }
    return f;
  }
}  // namespace haar_lib
#line 4 "Mylib/IO/input_vector.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<T> input_vector(int N) {
    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) std::cin >> ret[i];
    return ret;
  }

  template <typename T>
  std::vector<std::vector<T>> input_vector(int N, int M) {
    std::vector<std::vector<T>> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = input_vector<T>(M);
    return ret;
  }
}  // namespace haar_lib
#line 10 "test/aoj/2446/main.test.cpp"

namespace hl = haar_lib;

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

  int64_t n, m;
  std::cin >> n >> m;

  auto a = hl::input_vector<int64_t>(n);
  auto p = hl::input_vector<double>(n);

  for (auto &x : p) x /= 100.0;

  std::vector<int64_t> dp(1 << n);
  for (int i = 1; i < 1 << n; ++i) {
    int64_t l = 1;
    for (int j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        int64_t g = std::gcd(l, a[j]);

        long long int k;
        if (__builtin_smulll_overflow(l / g, a[j], &k)) {
          l = m + 1;
          break;
        }
        l = (l / g) * a[j];
      }
    }
    dp[i] = m / l;
  }

  dp = hl::fast_mobius_transform_subset(dp);

  double ans = 0.0;

  for (int i = 0; i < (1 << n); ++i) {
    double q = 1.0;
    for (int j = 0; j < n; ++j) {
      if (i >> j & 1)
        q *= p[j];
      else
        q *= 1.0 - p[j];
    }
    ans += q * std::abs(dp[i]);
  }

  std::cout << std::fixed << std::setprecision(12) << ans << std::endl;

  return 0;
}

Back to top page