Submission #69346434

---

Source Code Expand

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
template<typename T> bool chmin(T& a, T b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, T b){if(a < b){a = b; return true;} return false;}
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
constexpr ll mod=1000000007;
constexpr ll inf=3e18;

ll gcd(ll a,ll b){
	if(!b)return a;
	return gcd(b,a%b);
}
ll lcm(ll a,ll b){
	ll g=gcd(a,b);
	a/=g;
	b/=g;
	if(log10(a)+log10(b)+log10(g)>18.1)return -1;
	else return a*b*g;
}

ll binom[22][22];

int main(){
	ll n,m,y;
	cin>>n>>m>>y;
	vector<ll>a(n);
	rep(i,n)cin>>a[i];
	ll sum=0;
	vector<ll>subset(1<<n);
	rep(i,1<<n){
		ll L=1;
		rep(j,n){
			if(L==-1)break;
			if(i&(1<<j)){
				L=lcm(L,a[j]);
			}
		}
		if(L!=-1){
			subset[i]=y/L;
		}
	}

	binom[0][0]=1;
	rep(i,20){
		rep(j,i+1){
			binom[i+1][j]+=binom[i][j];
			binom[i+1][j+1]+=binom[i][j];
		}
	}
	vector<ll>ptn(n+1);
	rep(i,n+1){
		if(i==m)ptn[i]=1;
		else if(i>m){
			ll sum=0;
			for(int j=m;j<i;j++){
				sum-=binom[i][j]*ptn[j];
			}
			ptn[i]=sum;
		}
		//cout<<ptn[i]<<endl;
	}


	ll ans=0;
	rep(i,1<<n){
		ans+=subset[i]*ptn[__builtin_popcount(i)];
	}
	cout<<ans<<endl;


}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:39:12: warning: unused variable ‘sum’ [-Wunused-variable]
   39 |         ll sum=0;
      |            ^~~

Judge Result