答辩翻译捏，最关键的题意没翻译出来，求满足条件的集合个数到底是啥条件啊?。给定 \(n\) 个数的序列 \(a\)，令 \(N = \Pi_{i = 1}^{n} a_i\)，求选取 \(N\) 的约数组成可重集，集合中至少有一对不互质的数的集合个数。
转化问题为总集合数减去集合中的数全都两两互质的集合数。先对 \(n\) 个数进行质因数分解，可以直接 \(\sqrt{a_i}\) 的暴力枚举因子，这并不是瓶颈所在。总集合数量是好算的，如何对要求的后者进行计数。考虑 DP，设有 \(T\) 个不同的质因子，设 \(f_{i,j}\) 表示当前考虑到第 \(i\) 个质因子，构建的集合大小为 \(j\) 的总数；\(g_i\) 表示第 \(i\) 种质因子的总个数。显然边界为 \(f_{0,0} = 1\)。转移方程分为三类：
- \(f_{i + 1,j} += f_{i,j}\)，不使用第 \(i\) 种质因子；
- \(f_{i + 1,j} += f_{i,j} \times j \times g_i\)，乘法原理，第 \(i\) 种质因子可以和任意其他 \(j\) 种因子搭配构成另一种新因子；
- \(f_{i + 1,j + 1} += f_{i,j} \times g_i\)，新构建一个 \(N\) 的因子。
最后用总集合数减去 \(\sum_{i = 1}^{T} f_{T,i}\) 即可。注意这是我们求出的答案并没有考虑到 \(1\) 的存在，事实上任何一个集合加上 \(1\) 都是合法的，所以最后答案要乘二。上述算法的复杂度为 \(\mathcal O(T^2)\)，不过冷静一下可以发现 \(T\) 的上限最多也不过三千左右，至此可以通过本题。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y) (__lg((x),(y)))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
if(ch!='~') putchar(ch);
return;
}
}
using namespace FastIO;
namespace MTool
{
#define TA template<typename T,typename... Args>
#define TT template<typename T>
static const int Mod=1e9+7;
TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
TT inline void cmax(T &a,T b) {a=max(a,b);}
TT inline void cmin(T &a,T b) {a=min(a,b);}
TA inline void cmax(T &a,T b,Args... args) {a=max({a,b,args...});}
TA inline void cmin(T &a,T b,Args... args) {a=min({a,b,args...});}
TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
TT inline T Cmul(T a,T b) {return a*b%Mod;}
TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
#undef TT
#undef TA
}
using namespace MTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=6010;
static const int inf=2147483647;
static const int INF=4557430888798830399;
static const int mod=1e9+7;
static const int bas=131;
int n,m,x,ans=1,all=1,k,f[MAX][MAX];
unordered_map<int,int> cnt;
inline void lmy_forever()
{
read(n);
for(int i=1;i<=n;++i)
{
read(x);
for(int j=2,con=0;j<=100000;++j,con=0)
{
if(j>x) break;
while(x%j==0) ++con,x/=j;
if(con) cnt[j]+=con;
}
if(x>1) ++cnt[x];
}
for(auto [_,num]:cnt) (all*=num+1)%=Mod-1;
m=cnt.size(),ans=qpow(2ll,all-1)-1,f[0][0]=1;
for(auto [_,num]:cnt)
{
for(int j=0;j<=m;++j) Madd(f[k+1][j],Cmul(Cadd(Cmul(j,num),1ll),f[k][j])),Madd(f[k+1][j+1],Cmul(num,f[k][j]));
++k;
}
for(int i=1;i<=m;++i) Mdel(ans,f[m][i]);
write(Cmul(ans,2ll),'\n');
return;
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::lmy_forever();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}