提出 #69343283

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define rep(i, s, e) for(int i = s; i <= e; ++i)
#define fep(i, s, e) for(int i = s; i < e; ++i)
#define _rep(i, s, e) for(int i = s; i >= e; --i)
#define _fep(i, s, e) for(int i = s; i > e; --i)

#define int long long
#define pii pair<int, int>

namespace FastIO {
	template <typename _Tp> inline void read(_Tp &x) { int neg = 1; char ch; while(ch = getchar(), !isdigit(ch)) if(ch == '-') neg = -1; x = ch - '0'; while(ch = getchar(), isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ '0'); x *= neg; }
	template <typename _Tp, typename... _Args> inline void read(_Tp &x, _Args &...args) { read(x); read(args...); }
	template <typename _Tp> inline void read(_Tp* begin, _Tp* end) { int len = end - begin; for(int i = 0; i < len; ++i) read(*(begin + i)); }
	template <typename _Tp> inline void write(_Tp x) { if(x < 0) putchar('-'), x = -x; if(x > 9) write(x / 10); putchar(x % 10 + '0'); }
	template <typename _Tp, typename... _Args> inline void write(_Tp x, _Args ...args) { write(x); putchar(' '); write(args...); }
	template <typename _Tp> inline void write(_Tp* begin, _Tp* end) { int len = end - begin; for(int i = 0; i < len; ++i) write(*(begin + i)), putchar(' '); }
}

using namespace std;
using namespace FastIO;

constexpr int inf = numeric_limits<int>::max() / 2;
constexpr int ninf = numeric_limits<int>::min() / 2;
constexpr int mod = 998244353;
constexpr double eps = 0.000001;

int n, m, Y, a[25], dp[1 << 20], sum[1 << 20], x, y, fx, fy, ans;

void solve() {
	read(n, m, Y);
	read(a + 1, a + 1 + n);
	fep(st, 1, 1 << n) {
		int res = 1;
		rep(i, 1, n) if((st >> (i - 1)) & 1) {
			res /= __gcd(res, a[i]);
			if(Y / a[i] >= res) res *= a[i];
			else {
				res = Y + 1;
				break;
			}
		}
		dp[st] = Y / res;
	}
	_rep(st, (1 << n) - 1, 1) {
		x = st >> 10;
		y = st & 1023;
		fx = x ^ 1023;
		fy = y ^ 1023;
		for(int i = fy; ; i = (i - 1) & fy) {
			dp[st] -= sum[x << 10 | (y | i)];
			if(!i) break;
		}
		for(int i = x; ; i = (i - 1) & x) {
			sum[i << 10 | y] += dp[st];
			if(!i) break;
		}
	}
	fep(st, 1, 1 << n) if(__builtin_popcount(st) == m) ans += dp[st];
	write(ans), putchar('\n');
	return;
}

signed main() {
	int T = 1;
	while(T--) solve();
	return 0;
}

提出情報

ジャッジ結果