CF1205E Expected Value Again （border性质+莫比乌斯反演）
木xx木大
·
2021-04-02 18:29:18
·
题解
算法一
### 算法二
- 一个字符串 $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 ）
那么答案即为 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) 。
#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)
#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;
}