[LOJ6356]四色灯

[LOJ6356]四色灯

题目大意：

有(n(nle10^9))个编号(1sim n)的格子和(m(mle20))个按钮。每个格子有一个初始为(0)的数，每个按钮有一个数字(a_i)，表示若这个按钮被选中，编号为(a_i)倍数的格子上的数字(+1)。

现在随机选取一个按钮的集合，求数值为(4)的倍数的格子的期望个数。

思路：

用(f(S))表示(1sim n)中，编号为(operatorname{lcm}(S))的倍数的格子数。

(g(S))表示(1sim n)中，编号(x)为(operatorname{lcm}(S))的倍数，且不存在集合(T)，满足(Sin T)且(operatorname{lcm}(T)|x)的格子数。

则答案为(sumlimits_{S}g(S)sumlimits_{k}{|S|choose 4k}cdot2^{m-4k})。

时间复杂度(mathcal O(3^m))。

由于相同大小的集合，其贡献可以一起算。因此我们用(G(x))表示(sumlimits_{|S|=x}g(S))，则最终答案可表示为(sumlimits_{i}g(i)sumlimits_{k}{ichoose 4k}cdot2^{m-4k})。

时间复杂度(mathcal O(2^mm))。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
#define popcount __builtin_popcount
inline int getint() {
	register char ch;
	while(!isdigit(ch=getchar()));
	register int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
typedef long long int64;
const int M=21,mod=998244353;
int a[M],f[M],g[M],c[M][M];
void exgcd(const int &a,const int &b,int &x,int &y) {
	if(!b) {
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
inline int inv(const int &x) {
	int ret,tmp;
	exgcd(x,mod,ret,tmp);
	return (ret%mod+mod)%mod;
}
int main() {
	const int n=f[0]=getint(),m=getint();
	for(register int i=0;i<=m;i++) {
		for(register int j=c[i][0]=1;j<=i;j++) {
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
	}
	for(register int i=0;i<m;i++) {
		a[i]=getint();
	}
	for(register int s=1;s<1<<m;s++) {
		int64 lcm=0;
		for(register int i=0;i<m;i++) {
			if((s>>i)&1) {
				lcm=lcm?lcm*a[i]/std::__gcd(lcm,1ll*a[i]):a[i];
			}
			if(lcm>n) break;
		}
		(f[popcount(s)]+=n/lcm)%=mod;
	}
	std::copy(&f[0],&f[m]+1,g);
	for(register int i=m;i>=0;i--) {
		for(register int j=i+1;j<=m;j++) {
			g[i]-=1ll*g[j]*c[j][i]%mod;
			(g[i]+=mod)%=mod;
		}
	}
	int ans=0;
	for(register int i=0;i<=m;i++) {
		int tmp=0;
		for(register int j=0;j<=i;j+=4) {
			(tmp+=1ll*c[i][j]*(1<<(m-i))%mod)%=mod;
		}
		(ans+=1ll*g[i]*tmp%mod)%=mod;
	}
	printf("%lld
",1ll*ans*inv(1<<m)%mod);
	return 0;
}