CF1205E Expected Value Again （border性质+莫比乌斯反演）
木xx木大
2021-04-02 18:29:18
### 算法一
$O(k^n)$ 暴力枚举
### 算法二
- 一个字符串 $s$ 有长度为 $i$ 的 border 就有长度为 $|s|−i$ 的 period（一个字符串 $s$ 有长度为 $l$ 的 period 当且仅当对于所有的 $1\le i\le |s|−l$ 都有 $s_i=s_{i+l}$），于是把 border 个数转为求 period 个数
- 首先转化一下问题：$f(s)^2$ 相当于枚举两个 $1\le i,j<n$，使得 $s$ 同时存在 $i,j$ 两个 period，于是可以考虑算出每一对 $1≤i,j<n$ 的贡献后加起来
- 现在考虑对于一对 $i,j$，有多少个长度为 $n$ 的字符串 $s$ 满足 $s$ 同时存在 $i,j$ 两个 period
- 这相当于 $n$ 个点，在编号差为 $i$ 或 $j$ 的点对之间连边表示这两个下标上的字符相等，计算出连通块个数为 $cnt$，则这对 $i,j$ 的贡献为 $k^{cnt}$
### 算法三
一个结论：$cnt=\max(\gcd(i,j),i+j-n)$
>证明：（以下假设 $i\le j$）
>
>* $i+j \le n$ 时，因为有周期 $i$，形成了模 $i$ 意义下的剩余系，于是只需考虑前 $i$ 个点，因为前 $i$ 个点都能向后连一条长度为 $j$ 的边，因此得到 $\gcd(i,j)$ 个连通块。（即 zzc 巨佬讲的弱周期引理）
>* $i+j>n$ 时，只有前 $n−j$ 个点能向后连边，每连一条边都有可能使连通块个数减一，但当连边形成环时，连通块个数不变，得连通块个数为 $i-(n-j)$ 加上环的个数。环的个数为 $\max(n−j−(i−\gcd(i,j)),0)$。
那么答案即为 $ans\times k^n=\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{n-1}k^{\max(\gcd(i,j),i+j-n)}$。
### 算法四
枚举 $i+j$ 和 $\gcd(i,j)$，算对应的 $(i,j)$ 的个数。
$$
\begin{aligned}
&\sum_{s=2}^{2n-2}\sum_{g=1}^{n-1}\sum_{i=\max(1,s-n+1)}^{\min(n-1,s-1)}[\gcd(i,s-i)=g]\\
=&\sum_{s=2}^{2n-2}\sum_{g|s}\sum_{i=\max(1,\frac{s}{g}-\lfloor\frac{n-1}{g}\rfloor)}^{\min(\lfloor\frac{n-1}{g}\rfloor,\frac{s}{g}-1)}[\gcd(i,\frac{s}{g}-i)=1]\\
\end{aligned}
$$
设 $l=\max(1,\frac{s}{g}-\lfloor\frac{n-1}{g}\rfloor),r=\min(\lfloor\frac{n-1}{g}\rfloor,\frac{s}{g}-1)$
$$
\begin{aligned}
&\sum_{s=2}^{2n-2}\sum_{g|s}\sum_{i=l}^{r}[\gcd(i,\frac{s}{g}-i)=1]\\
=&\sum_{s=2}^{2n-2}\sum_{g|s}\sum_{d|\frac{s}{g}}\mu(d)\sum_{i=l}^{r}[d|i]\\
=&\sum_{s=2}^{2n-2}\sum_{g|s}\sum_{d|\frac{s}{g}}\mu(d)\left(\left\lfloor\frac{r}{d}\right\rfloor-\left\lfloor\frac{l-1}{d}\right\rfloor\right)
\end{aligned}
$$
复杂度 $O(n\log^2n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
int n,m;
const int N=2e5+5,mo=1e9+7;
int vis[N],mu[N],p[N],cnt,pw[N],ans;
vector<int> g[N];
int inv(int x)
{
int s=1,y=mo-2;
while(y)
{
if(y&1)s=1ll*s*x%mo;
x=1ll*x*x%mo;
y>>=1;
}
return s;
}
void init()
{
mu[1]=1,pw[0]=1,pw[1]=m;
for(int i=2;i<=2*n;i++)
{
pw[i]=1ll*pw[i-1]*m%mo;
if(!vis[i])p[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&p[j]*i<=2*n;j++)
{
vis[p[j]*i]=1;
if(i%p[j]==0)break;
mu[p[j]*i]=-mu[i];
}
}
for(int i=1;i<=2*n;i++)
for(int j=i;j<=2*n;j+=i)
g[j].push_back(i);
}
int calc(int x,int y)
{
if(y<=0||x<=1)return 0;
int l=max(1,x-y),r=min(y,x-1),sum=0;
if(l>r)return 0;
for(int i=0;i<g[x].size();i++)
sum=(sum+mu[g[x][i]]*(r/g[x][i]-(l-1)/g[x][i])%mo)%mo;
return (sum+mo)%mo;
}
void work()
{
scanf("%d%d",&n,&m);
init();
for(int s=2;s<=2*n-2;s++)
for(int i=0;i<g[s].size();i++)
ans=(ans+1ll*calc(s/g[s][i],(n-1)/g[s][i])*pw[max(s-n,g[s][i])]%mo)%mo;
printf("%lld",1ll*ans*inv(pw[n])%mo);
}
}
int main()
{
FGF::work();
return 0;
}
```
### 算法五
考虑容斥。先假设所有 $(i,j)$ 均取 $i+j-n$，那么此时贡献为
$$
\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{n-1}k^{i+j-n}
$$
枚举 $i+j$ ，计算一下其出现次数即可。预处理 $k$ 的幂，可做到 $O(n)$。
然后修正答案
$$
\begin{aligned}
&\sum_{p=1}^{n-1}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=p][i+j-n<p](k^p-k^{i+j-n})\\=
&\sum_{p=1}^{n-1}\sum_{i=1}^{\lfloor\frac{n-1}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{p}\rfloor}[\gcd(i,j)=1][(i+j)p-n<p](k^p-k^{(i+j)p-n})\\=
&\sum_{p=1}^{n-1}\sum_{i=1}^{\lfloor\frac{n-1}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{p}\rfloor}\sum_{d|i,d|j}\mu(d)[(i+j)p-n<p](k^p-k^{(i+j)p-n})\\=
&\sum_{p=1}^{n-1}\sum_{d=1}^{\lfloor\frac{n-1}{p}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{n-1}{dp}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{dp}\rfloor}[(i+j)dp-n<p](k^p-k^{(i+j)dp-n})\\=
&\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor\frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{T}\rfloor}[(i+j)T-n<d](k^d-k^{(i+j)T-n})
&
\end{aligned}
$$
拆成两部分分别算
$$
\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor\frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{T}\rfloor}k^{(i+j)T-n}[(i+j)T-n<d]
$$
先把 $k^{-n}$ 提出来。后面部分可以看作一个关于 $k^T$ 的多项式。
$$
\because(i+j)T-n<d\\
\therefore i+j\le\lfloor\frac{d+n-1}{T}\rfloor\\
\because d\le T\\
\therefore i+j\le\lfloor\frac{d+n-1}{T}\rfloor\le\lfloor\frac{n-1}{T}\rfloor+1
$$
相当于枚举一个 $x=i+j\ (xT\le 2n-2,x\le\lfloor\frac{d+n-1}{T}\rfloor)$，每个这样的 $x$ 会出现 $x-1$ 次，因此把答案多项式的 $xT$ 项减去 $(x-1)\mu(\frac{T}{d})$。具体实现时枚举 $T$，然后用一个数组存储这个 $T$ 导致的答案多项式的变化量，其中第 $x$ 个位置对应答案多项式的第 $xT$ 项。枚举 $d$ 时对这个数组打上标记，然后枚举完 $d$ 后按标记算出变化量即可。这样处理后，这部分的后半部分可以 $O(1)$ 算。
$$
\sum_{T=1}^{n-1}\sum_{d|T}\mu(\frac{T}{d})\sum_{i=1}^{\lfloor\frac{n-1}{T}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{T}\rfloor}[(i+j)T-n<d]k^d
$$
对于 $x=i+j\le\lfloor\frac{n-1}{T}\rfloor+1$，每个这样的 $x$ 会出现 $x-1$ 次，故这个式子后半部分的值为 $\sum_{x=2}^{\lfloor\frac{n-1}{T}\rfloor+1}(x-1)k^d=\lfloor\frac{n-1}{T}\rfloor\times(\lfloor\frac{n-1}{T}\rfloor-1)k^d$
所以原式的后半部分均可以 $O(1)$ 算，总复杂度为枚举 $T,d$ 的 $O(n\log n)$
（这个式子太阴间了于是有了算法六）
### 算法六
$$
\begin{aligned}&\sum_{p=1}^{n-1}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=p][i+j-n<p](k^p-k^{i+j-n})\\
=&\sum_{p=1}^{n-1}\sum_{i=1}^{\lfloor\frac{n-1}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{p}\rfloor}[\gcd(i,j)=1][(i+j)p-n<p](k^p-k^{(i+j)p-n})\\
=&\sum_{p=1}^{n-1}\sum_{i=1}^{\lfloor\frac{n-1}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{n-1}{p}\rfloor}[\gcd(i,j)=1][(i+j)\le\lfloor\frac{n-1}{p}\rfloor+1](k^p-k^{(i+j)p-n})\\
=&\sum_{p=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{p}\rfloor+1}\sum_{i=1}^{s-1}[\gcd(i,s-i)=1](k^p-k^{sp-n})\\
=&\sum_{p=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{p}\rfloor+1}\sum_{i=1}^{s-1}[\gcd(i,s)=1](k^p-k^{sp-n})\\
\end{aligned}
$$
前半部分
$$
\begin{aligned}
&\sum_{p=1}^{n-1}\sum_{s=1}^{\lfloor\frac{n-1}{p}\rfloor+1}\sum_{i=1}^{s-1}[\gcd(i,s)=1]k^p\\=
&\sum_{p=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{p}\rfloor+1}\phi(s)k^p\\
\end{aligned}
$$
预处理一下 $\phi$ 的前缀和即可 $O(n)$ 算。
后半部分
$$
\begin{aligned}
\sum_{p=1}^{n-1}\sum_{s=2}^{\lfloor\frac{n-1}{p}\rfloor+1}\phi(s)k^{sp-n}
\end{aligned}
$$
我们在算 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{n-1}k^{i+j-n}$ 的时候只考虑 $i+j-n>0$ 的情况，则这里也只需要考虑 $i+j-n>0$ 的情况。如果 $sp-n>0$，那么 $sp>n$ 。$p\nmid n$ 时$s\ge \lfloor\frac{n-1}{p}\rfloor+1$，上式就可以变为 $\sum_{p=1}^{n-1}\phi(\lfloor\frac{n-1}{p}\rfloor+1)k^{(\lfloor\frac{n-1}{p}\rfloor+1)p-n}$，可以 $O(n)$ 算；$p|n$ 时 $s>\frac{n}{p}=\lfloor\frac{n-1}{p}\rfloor+1$，此时 $s$ 不存在，如果按上式算的话会贡献到 $(\lfloor\frac{n-1}{p}\rfloor+1)p-n=0$ 次项上，又因为最后统计答案的时候不会统计 0 次项，所以对答案没有影响，详见代码。
总复杂度 $O(n)$
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FGF
{
int n,m;
const int N=2e5+5,mo=1e9+7;
int p[N],phi[N],s[N],cnt,ans,c[N];
int qpow(int x,int y)
{
int s=1;
while(y)
{
if(y&1)s=1ll*s*x%mo;
x=1ll*x*x%mo;
y>>=1;
}
return s;
}
void init()
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!phi[i])p[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&p[j]*i<=n;j++)
{
if(i%p[j]==0){phi[i*p[j]]=phi[i]*p[j];break;}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
}
void work()
{
scanf("%d%d",&n,&m);
init();
for(int i=2;i<=n;i++)
s[i]=(s[i-1]+phi[i])%mo;
for(int i=1;i<n-1;i++)
c[i]=n-i-1;
for(int i=1,d;i<n;i++)
d=(n-1)/i,c[i]=(c[i]+s[d+1])%mo,c[(d+1)*i-n]=(c[(d+1)*i-n]-phi[d+1]+mo)%mo;
for(int i=1,k=m;i<n;i++,k=1ll*k*m%mo)
ans=(ans+1ll*c[i]*k%mo)%mo;
printf("%lld",1ll*ans*qpow(m,mo-1-n)%mo);
}
}
int main()
{
FGF::work();
return 0;
}
```