CF1205E [* hard]
给定字符串 (s),定义 (f(s)) 为其 ( m border) 的数量,令其长度为 (n),字符集为 ([1,k]),求 (f(s)^2) 的期望。答案对 (10^9+7) 取模。
(nle 10^5,kle 10^9)
( m Sol:)
首先如果存在一个长度为 (x) 的 ( m border),那么我们有当前字符串会满足对于 (iin [1,x],s_i=s_{i+(n-x)})
考虑 (f(s)) 的平方,可以考虑经典套路,枚举 ((i,j)) 且 (i,j) 均为 (s) 的 ( m border),那么 ((i,j)) 的对数就是 (f(s)^2)
枚举 (i,j) 不利于计算答案,我们可以考虑枚举 (n-x) 为 ((i,j)),那么对于 (forall kin [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 o i+a) 连一条边,这样可以得到以 (n\% a) 为类的共计 (|a|) 个组。
我们接下来显然只需要保留每个组的开头,即 (iin [1,a]),然后使 (i o 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)) o max(a+b-n,gcd(a,b)))
于是我们统计的答案即:
不妨枚举 (gcd(i,j)=d),计算贡献我们考虑容斥,先假设所有点均取 (i+j-n),那么此时贡献为:
枚举 (i+j),计算其出现次数然后乘以贡献即可,复杂度 (mathcal O(nlog n))
另一边,我们需要修正我们的答案,不难注意到所求为:
由于边界的不同,您可以看到上述式子推导中边界的问题,我们可以将上界先设为 (n),然后减去 (i,j) 分别有一个 (n) 对于答案的贡献。
同时,后者的 (G(T,frac{n-1}{T}+1)) 是我们放缩的一个界,容易验证此界与标准界的误差至多为 (1),所以可以对这个 (1) 的误差进行特判。
接下来预处理 (f(x)),其中 (f(x)=sum_{i,j}^x [i+jle x]),于是我们可以递推 (f),(f(x) o f(x+1)) 相当于增加了 (i+j=x+1) 的数,显然为 (x)
那么我们的瓶颈在于计算 (G(T)),不难注意到内部的 ([(i+j)le ...]) 是一个更严的界,所以我们可以直接考虑每个元素对于答案的贡献次数,显然对于 ((i+j)=x) 其被计算次数为 ((x-1)),那么我们不妨枚举 (T) 然后通过调和级数统计答案即可。
通过预处理 (K^d),我们可以做到 (mathcal O(nlog 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 ;
}