啊啊啊我在干什么啊。怎么这么颓一道题做这么久。。
又记错莫比乌斯反演式子了(╯‵□′)╯︵┻━┻
(Description)
给定(n)。有一个初始为空的集合(S)。令(g)表示S中所有数的(gcd)。每次随机选择一个([1,n])中的数加到集合(S)中去，直到(g=1)。求集合(S)的期望大小。（原题目描述为数列长度，(n)是指(m)，我自己都看混了=-=）
(nleq10^5)。
(Solution)
首先不要想(f[i][j])这种奇奇怪怪的二维DP状态。。
令(f[x])表示(g=x)时集合的期望大小。那么有$$egin{aligned}f[x]&=1+frac1nsum_{i=1}^nf[gcd(i,x)]&=1+frac1nsum_{dmid x}f[d]sum_{i=1}^n[(i,x)=d]&=1+frac1nsum_{dmid x}f[d]sum_{i=1}^{lfloorfrac nd
floor}[(i,lfloorfrac xd
floor)=1]end{aligned}$$
问题在于求(sum_{i=1}^{lfloorfrac nd
floor}[(i,lfloorfrac xd
floor)=1])。不妨设(g(n,k)=sum_{i=1}^n[(i,k)=1])。
若限制不是([(i,k)=1])而是([xmid (i,k)])，显然答案就是([xmid k]lfloorfrac nx
floor)。
所以令(f(d)=sum_{i=1}^n[(i,k)=d])，(F(d)=sum_{i=1}^n[dmid(i,k)]=[dmid k]lfloorfrac nd
floor)，有$$egin{aligned}g(n,k)=f(1)&=sum_{i=1}^nmu(i)F(i)&=sum_{i=1}^nmu(i)[imid k]lfloorfrac ni
floor&=sum_{dmid k}mu(d)lfloorfrac nd
floorend{aligned}$$
那么直接这样计算一次(g(n,k))的复杂度是(O(约数个数))的。(1sim n)的约数个数均摊应该是(O(log n))的？
发现转移的时候两边都有(f[x])。移下项，$$(1-frac1nsum_{i=1}^{lfloorfrac nx floor}[(i,1)=1])f[x]=1+frac1nsum_{dmid x,d eq x}f[d]sum_{i=1}^{lfloorfrac nd floor}[(i,lfloorfrac xd floor)=1]f[x]=frac{1+frac1nsum_{dmid x,d eq x}f[d]sum_{i=1}^{lfloorfrac nd floor}[(i,lfloorfrac xd floor)=1]}{1-frac1nlfloorfrac nx floor}=frac{n+sum_{dmid x,d eq x}f[d]sum_{i=1}^{lfloorfrac nd floor}[(i,lfloorfrac xd floor)=1]}{n-lfloorfrac nx floor}$$
这样就可以啦。答案是(sum_{i=1}^nfrac1nf[i])。
复杂度大概是(O(nlog^2n))的？
还有其它更优的做法，不想看惹（甚至有线性的，瑟瑟发抖）。
//140ms 10900KB
#include <cstdio>
#include <vector>
#include <algorithm>
#define mod 1000000007
typedef long long LL;
const int N=1e5+5;
int P[N>>2],mu[N],f[N],inv[N];
bool notP[N];
std::vector<int> fac[N];
inline int FP(int x,int k)
{
int t=1;
for(; k; k>>=1,x=1ll*x*x%mod) k&1&&(t=1ll*t*x%mod);
return t;
}
inline int G(int n,int k)
{
LL ans=0;
for(int i=0,l=fac[k].size(); i<l; ++i) ans+=mu[fac[k][i]]*(n/fac[k][i]);
return ans%mod;
}
void Init(const int n)
{
mu[1]=1;
for(int i=2,cnt=0; i<=n; ++i)
{
if(!notP[i]) P[++cnt]=i, mu[i]=-1;
for(int j=1,v; j<=cnt&&(v=i*P[j])<=n; ++j)
{
notP[v]=1;
if(i%P[j]) mu[v]=-mu[i];
else break;
}
}
for(int i=1; i<=n; ++i)
for(int j=i; j<=n; j+=i) fac[j].push_back(i);
}
int main()
{
int n; scanf("%d",&n);
Init(n);
f[1]=1, inv[1]=1;
for(int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int x=2; x<=n; ++x)
{
LL tmp=n;
const std::vector<int> &v=fac[x];
for(int i=0,l=v.size(),d; i+1<l; ++i) d=v[i], tmp+=1ll*f[d]*G(n/d,x/d);
f[x]=tmp%mod*inv[n-n/x]%mod;
}
LL ans=0;
for(int i=1; i<=n; ++i) ans+=f[i];
printf("%d
",int(ans%mod*inv[n]%mod));
return 0;
}