题目描述
俗话说，有钱就是任性。我们的高富帅鱼丸同学打算去看电影。鱼丸到了电影院以后，发现座位的编号正好是 $1$ 到 $200$ 。但是有一些座位号对应的座位坏掉了，没法坐，不妨假设还剩下 $N$ 个能坐的椅子。电影的老板告诉鱼丸，如果你要包下一个集合 $S$ 里的所有椅子，就要付出这些椅子的编号的最小公倍数的钱。鱼丸很任性地同意了。
来这里玩了很多天以后，鱼丸发现自己正好来了 $2^N-1$ 天，并且由于他非常任性，对于这 $N$ 个椅子的每一种可能的非空子集，他都包下过来看电影。鱼丸大少爷虽然不在乎花了多少钱，但你毕竟是他的助理，于是你想知道鱼丸一共花了多少钱。由于钱的数量实在太大，请对答案 $mod~1e9+7$ 之后输出。
数据范围
对于 $100\%$ 的数据，有 $N le 200$
题解
考虑到一个数，超过 $13$ 的质因子不超过 $1$ 个
所以设 $f_{a,b,c,d,e,f}$ 表示 $lcm$ 中 $2$ 的次数 $a$ ， $3$ 的次数 $b$ ， $5$ 的次数 $c$ ， $7$ 的次数 $d$ ， $11$ 的次数 $e$ ， $13$ 的次数 $f$ 的总和
然后可以将相同的大质数一起做，具体来说就是多记 $g$ 和 $h$ ，然后 $h$ 表示内部的 $dp$ 值，最后乘上质数即可，然后 $g$ 是在 $f$ 的基础上和 $h$ 一样的转移，最后 $-f-h$ 就是这些数和之前的数的 $lcm$ ，同样最后乘上质数即可，再用 $g$ 和 $h$ 去更新 $f$ 就好了
细节有点多，考场上心态有点崩（暴力写挂了qwq
代码
#include <bits/stdc++.h> using namespace std; const int P=1e9+7,N=205; int n,f[8][5][4][3][3][3],g[8][5][4][3][3][3],h[8][5][4][3][3][3],w[8][5][4][3][3][3],p[6]={2,3,5,7,11,13},k[6]={7,4,3,2,2,2},d[6],s,ans; struct O{int t[6],x;}a[N]; bool cmp(O A,O B){return A.x<B.x;} void dfs(int x,int y){ if (x>5){ (f[max(a[y].t[0],d[0])][max(a[y].t[1],d[1])][max(a[y].t[2],d[2])][max(a[y].t[3],d[3])][max(a[y].t[4],d[4])][max(a[y].t[5],d[5])]+= f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]])%=P; (h[max(a[y].t[0],d[0])][max(a[y].t[1],d[1])][max(a[y].t[2],d[2])][max(a[y].t[3],d[3])][max(a[y].t[4],d[4])][max(a[y].t[5],d[5])]+= h[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]])%=P; return; } for (int i=k[x];~i;i--) d[x]=i,dfs(x+1,y); } void geth(int x){ if (x>5){ (s+=1ll*h[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]*w[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]%P)%=P; return; } for (int i=k[x];~i;i--) d[x]=i,geth(x+1); } void getf(int x,int y){ if (x>5){ f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]-=((g[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]+h[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]])%P); if (f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]<0) f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]+=P; (g[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]+=1ll*(f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]+h[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]])%P*y%P)%=P; (s+=1ll*f[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]*w[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]]%P)%=P; return; } for (int i=k[x];~i;i--) d[x]=i,getf(x+1,y); } void getw(int x){ if (x>5){ int &F=w[d[0]][d[1]][d[2]][d[3]][d[4]][d[5]];F=1; for (int i=0;i<6;i++) for (int j=1;j<=d[i];j++) F=1ll*p[i]*F%P; return; } for (int i=k[x];~i;i--) d[x]=i,getw(x+1); } int main(){ scanf("%d",&n);getw(0); for (int y,i=1;i<=n;i++){ scanf("%d",&y); for (int j=0;j<6;j++) while(y%p[j]==0) a[i].t[j]++,y/=p[j]; a[i].x=y; } sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++){ if (a[i].x==1 || a[i].x!=a[i-1].x) memcpy(f,g,sizeof f),memset(h,0,sizeof h);dfs(0,i); f[a[i].t[0]][a[i].t[1]][a[i].t[2]][a[i].t[3]][a[i].t[4]][a[i].t[5]]++; h[a[i].t[0]][a[i].t[1]][a[i].t[2]][a[i].t[3]][a[i].t[4]][a[i].t[5]]++; if (a[i].x==1 || a[i].x!=a[i+1].x){ s=0;geth(0);(ans+=1ll*s*a[i].x%P)%=P; s=0;getf(0,a[i].x);(ans+=1ll*s*a[i].x%P)%=P; } } return printf("%d ",ans),0; }