题解 CF1205E 【Expected Value Again】

· · 题解

给定字符串 s，定义 f(s) 为其 \rm border 的数量，令其长度为 n，字符集为 [1,k]，求 f(s)^2 的期望。答案对 10^9+7 取模。

n\le 10^5,k\le 10^9 \rm Sol:

首先如果存在一个长度为 x 的 \rm border，那么我们有当前字符串会满足对于 i\in [1,x],s_i=s_{i+(n-x)}

考虑 f(s) 的平方，可以考虑经典套路，枚举 (i,j) 且 i,j 均为 s 的 \rm border，那么 (i,j) 的对数就是 f(s)^2

枚举 i,j 不利于计算答案，我们可以考虑枚举 n-x 为 (i,j)，那么对于 \forall k\in [1,n-i],s_k=s_{k+i},s_k=s_{k+j}，暴力的做法是考虑枚举 (i,j) 然后让 x 向 x+i,x+j 连一条边，那么贡献即为 k^{cnt}，其中 cnt 为连通块数量。

更进一步，我们不妨设 a<b，略做观察，我们可以考虑让 i\to i+a 连一条边，这样可以得到以 n\% a 为类的共计 |a| 个组。

我们接下来显然只需要保留每个组的开头，即 i\in [1,a]，然后使 i\to i+b 连边，显然这样即可保证连通性。

显然如果 [1,a] 中的点均连了边，我们可以发现此时图会变成 \gcd(a,b) 个组。

否则，我们发现仅有 (n-b,a] 这个区间内的点没有连边，我们假定之前的 b 边是将 \%a 相同的链串成环，那么其会依次断开每个环的一条边，接着才开始断边，于是我们不难发现，当 a-(n-b)\le \gcd(a,b) 时，边均失效，否则先有 \gcd(a,b) 条失效边，其余情况可以当作森林的情况计算（点数减去边数），最终我们得到连通块数量为 \gcd(a,b)+\max(0,a+b-n-\gcd(a,b))\to \max(a+b-n,\gcd(a,b))

于是我们统计的答案即：

\sum_{i=1}^{n-1} \sum_{j=1}^{n-1} K^{\max(\gcd(i,j),i+j-n)}

不妨枚举 \gcd(i,j)=d，计算贡献我们考虑容斥，先假设所有点均取 i+j-n，那么此时贡献为：

\frac{\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}K^{i+j}}{K^n}

枚举 i+j，计算其出现次数然后乘以贡献即可，复杂度 \mathcal O(n\log n)

另一边，我们需要修正我们的答案，不难注意到所求为：

&\sum_{d=1}^{n}\sum_{i,j}^{n/d}[\gcd(i,j)=1] (K^d-K^{(i+j)d-n})[(i+j)d-n< d] \\&=\sum_{d=1}^{n}\sum_{i,j}^{n/d}\sum_{k|i,k|j} \mu(k)(K^d-K^{(i+j)d-n})[(i+j)d-n< d] \\&=\sum_{d=1}^{n}\sum_{k}^{n/d}\sum_{i,j}[(i+j)kd-n< d]\mu(k)(K^d-K^{(i+j)kd-n}) \\&=\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})\sum_{i,j}[(i+j)T-n< d]\mu(k)K^d-\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})\sum_{i,j}[(i+j)T-n< d] K^{(i+j)T-n} \\&=\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})\sum_{i,j}[(i+j)\le \frac{n+d-1}{T}]K^d-\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})\sum_{i,j}[(i+j)\le \frac{n+d-1}{T}] K^{(i+j)T-n} \\&=\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})f(\frac{n+d-1}{T})K^d-\frac{1}{K^n}\sum_{T=1}^{n}\sum_{d|T}\mu(\frac{T}{d})G(T,\frac{n-1}{T}+1) \end{aligned}

由于边界的不同，您可以看到上述式子推导中边界的问题，我们可以将上界先设为 n，然后减去 i,j 分别有一个 n 对于答案的贡献。

同时，后者的 G(T,\frac{n-1}{T}+1) 是我们放缩的一个界，容易验证此界与标准界的误差至多为 1，所以可以对这个 1 的误差进行特判。

接下来预处理 f(x)，其中 f(x)=\sum_{i,j}^x [i+j\le x]，于是我们可以递推 f，f(x)\to f(x+1) 相当于增加了 i+j=x+1 的数，显然为 x

那么我们的瓶颈在于计算 G(T)，不难注意到内部的 [(i+j)\le ...] 是一个更严的界，所以我们可以直接考虑每个元素对于答案的贡献次数，显然对于 (i+j)=x 其被计算次数为 (x-1)，那么我们不妨枚举 T 然后通过调和级数统计答案即可。

通过预处理 K^d，我们可以做到 \mathcal O(n\log n)

Code: 
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 4e5 + 5 ; 
const int P = 1e9 + 7 ; 
const int I = 1e9 + 8 ; 
int n, K, Ans, f[N], g[N], fac[N], mu[N] ;
bool isp[N] ; 
int fpow(int x, int k) {
    int ans = 1, base = x ; 
    while(k) {
        if(k & 1) ans = ans * base % P ; 
        base = base * base % P, k >>= 1 ; 
    } return ans ; 
}
void init() {
    rep( i, 1, 2 * n ) fac[i] = fpow( K, i ) % P ; 
    rep( i, 1, n ) 
        f[i] = ( f[i - 1] + (i - 1) ) % P ; 
    rep( x, 1, n ) {
        int lim = (n - 1) / x + 1 ; 
        rep( i, 1, lim ) g[x] = (g[x] + (i - 1) * fac[i * x] % P) % P ;
    }
    rep( i, 1, n ) mu[i] = 1 ; 
    rep( i, 2, n ) {
        if(isp[i]) continue ; mu[i] = -1 ; int v = i * i ; 
        for(re int j = i * 2; j <= n; j += i) isp[j] = 1, mu[j] = -mu[j] ;
        for(re int j = v; j <= n; j += v) mu[j] = 0 ;
    }
    rep( i, 1, n ) mu[i] = (P + mu[i]) % P ; 
}
int gcd(int a, int b) {
    return (!a) ? b : gcd(b % a, a) ;  
}
signed main()
{
    n = gi(), K = gi() ; 
    init() ; 
    rep( i, 1, 2 * n ) {
        if( i <= n ) Ans = ( Ans + fpow(K, i) * (i - 1) ) % P ; 
        else Ans = ( Ans + fpow(K, i) * (2 * n - i + 1) ) % P ; 
    } 
    Ans = Ans * fpow( fpow( K, n ), P - 2 ) % P ;
    int dAns = 0 ;
    rep(d, 1, n) {
        int fK = fpow( K, d ) ; 
        rep(k, 1, n / d) { 
            int x = k * d ; 
            int lim = (n - 1) / x + 1 ; 
            int rim = (n + d - 1) / x ; 
            if( lim == rim ) dAns = ( dAns + mu[k] * g[x]) % P ; 
            else dAns = ( dAns + mu[k] * (g[x] - (lim - 1) * fac[lim * x] % P + P ) % P ) % P ; 
            Ans = ( Ans + mu[k] * f[rim] % P * fac[d] % P ) % P ; 
        }
    }
    dAns = dAns * fpow( fpow( K, n ), P - 2 ) % P ;
    Ans = ( Ans - dAns + P ) % P ; 
    rep(i, 1, n) Ans = ( Ans - ( 1 + (i != n) ) * fac[max(i, gcd(i, n))] + P ) % P ; 
    Ans %= P, Ans = ( Ans + P ) % P ; 
    cout << Ans * fpow( fac[n], P - 2 ) % P << endl ;  
    return 0 ;
}