题意
有\(1-n\)的数和\(m\)个操作。进行\(a_i\)操作时，会将\(a_i\)的倍数权值\(+1\)。
对于每个操作可以选择是否进行，问对于所有情况，权值整除\(4\)的格子总数
\(n \leq 10^9,m \leq 20\)
思路
首先考虑暴力，即对于每个数\(nm\)求出有多少个操作会影响到它，答案即为\(\sum C(cnt,4k)\times 2^{m-cnt}\)
瓶颈在于前半部分。
因为操作个数较少，可以考虑枚举因数集合，设\(f[S]\)表示能整除\(S\)中所有数的\(x\)的个数。
\(f[S]=\frac{n}{lcm(x \in S)}\)。
\(g[S]\)表示\(S\)是\(x\)所有因数的\(x\)的个数，那么可以通过枚举子集的容斥来得到，但是会T。
注意到最后的答案只和个数有关，就是\(|S|\)，所以我们不需要关心具体的集合。
另\(F[i]=\sum_{|S|=i}f[S]\)，\(G[i]=\sum_{|S|=i}g[S]\)。
\(F\)很好求，问题转化为如何容斥求得\(G\)，对于\(F[j]\)和\(G[i](j>i)\)，显然\(F[j]\)会在\(G[i]\)中多算\(C(j,i)\)次。容斥式有点麻烦，我就不写了。
#include <bits/stdc++.h>
const int mu=998244353;
int n,m,a[25],f[25],g[25],ans,c[25][25];
int gcd(int x,int y){
if (x%y==0) return y;
return gcd(y,x%y);
}
int sgn(int x){
return x&1?mu-1:1;
}
int ksm(int x,int y){
int ans=1;
for (;y;y>>=1,x=x*1ll*x%mu)
if (y&1) ans=ans*1ll*x%mu;
return ans;
}
int main(){
scanf("%d%d",&n,&m);
c[0][0]=1;
for (int i=1;i<=20;i++){
c[i][0]=1;
for (int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mu;
}
for (int i=0;i<m;i++) scanf("%d",&a[i]);
for (int i=0;i<1<<m;i++){
long long lcm=1;
int S=0;
for (int j=0;j<m;j++)
if (i&(1<<j)){
S++;
lcm=lcm/gcd(lcm%a[j],a[j])*a[j];
if (lcm>n) break;
}
f[S]+=n/lcm;
}
for (int i=m;i>=0;i--){
g[i]=f[i];
for (int j=i+1;j<=m;j++)
g[i]=(g[i]+sgn(j-i)*1ll*f[j]%mu*c[j][i])%mu;
}
for (int i=0;i<=m;i++)
for (int k=0;k<=m;k+=4)
ans=(ans+g[i]*1ll*c[i][k]%mu*(1<<(m-i)))%mu;
ans=ans*1ll*ksm(1<<m,mu-2)%mu;
printf("%d\n",ans);
}
后记
想不到系列