[LOJ6356]四色灯
题目大意：
有\(n(n\le10^9)\)个编号\(1\sim n\)的格子和\(m(m\le20)\)个按钮。每个格子有一个初始为\(0\)的数，每个按钮有一个数字\(a_i\)，表示若这个按钮被选中，编号为\(a_i\)倍数的格子上的数字\(+1\)。
现在随机选取一个按钮的集合，求数值为\(4\)的倍数的格子的期望个数。
思路：
用\(f(S)\)表示\(1\sim n\)中，编号为\(\operatorname{lcm}(S)\)的倍数的格子数。
\(g(S)\)表示\(1\sim n\)中，编号\(x\)为\(\operatorname{lcm}(S)\)的倍数，且不存在集合\(T\)，满足\(S\in T\)且\(\operatorname{lcm}(T)|x\)的格子数。
则答案为\(\sum\limits_{S}g(S)\sum\limits_{k}{|S|\choose 4k}\cdot2^{m-4k}\)。
时间复杂度\(\mathcal O(3^m)\)。
由于相同大小的集合，其贡献可以一起算。因此我们用\(G(x)\)表示\(\sum\limits_{|S|=x}g(S)\)，则最终答案可表示为\(\sum\limits_{i}g(i)\sum\limits_{k}{i\choose 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\n",1ll*ans*inv(1<<m)%mod);
return 0;
}