@codeforces - 1205E@ Expected Value Again

2019/08/23 19:30
阅读数 7

[toc]


@description@

给定两个数 n, k,令 s 是一个字符集大小为 k 的随机字符串。

定义 f(s) 表示满足 s 长度为 i 的前缀 = s 长度为 i 的后缀的 i 的数量,要求 1 ≤ i < |s|。

求 f(s)^2 的期望。

Input 只有一行,包含两个整数 n, k(1≤n≤10^5, 1≤k≤10^9),含义如上。

Output 输出期望 mod 10^9 + 7。

Examples Input 2 3 Output 333333336

Input 1 5 Output 0

Input 100 1 Output 9801

Input 10 10 Output 412377396

@solution@

@part - 1@

其实题目所说的前后缀相等,就是 border 的数量。 因为长度为 k 的 border 等价于长度为 n - k 的周期,为了方便下面的讨论,我们不妨去计算周期的数量。

考虑令随机变量 $g_i(s)$,当 s 含有长度为 i 的周期时为 1,否则为 0。 则可以得到 $f(s) = \sum_{i=1}^{n-1}g_i(s)$,即考虑每种长度的周期的贡献。 于是可以得到 $E(f(s)^2) = \sum_{i=1}^{n-1}\sum_{j=1}^{n-1}E(g_i(s)*g_j(s))$,这个可以用期望的线性性质算。

考虑 $E(g_i(s)*g_j(s))$ 实际上等于 s 同时含有长度为 i 的周期与长度为 j 的周期的概率。 这里有一个结论:$E(g_i(s)*g_j(s)) = (\frac{1}{k})^{n - \max(i+j-n, gcd(i, j))}$。证明我会在 part - 3 给出。 接下来考虑在有这个结论的前提下求解答案。

@part - 2@

根据上面的思路,我们想要去求 $\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}(\frac{1}{k})^{n - \max(i+j-n, gcd(i, j))}$。

注意到这个式子只与 $s = i + j, d = gcd(i, j)$ 有关,而又因为 $d|s$,所以二元组 (d, s) 的数量不会超过 O(nlog n)(根据调和级数)。 我们尝试对于每一对 (d, s) 计算有多少对 (i, j) 满足 $i + j = s, gcd(i, j) = d$。

因为 $gcd(i, s) = gcd(i, s - i) = gcd(i, j) = d$(根据 gcd 的性质),所以 j 其实是不重要的,只会约束 i 的取值范围。 我们只需要算有多少 i 满足 1 <= i <= n-1 且 1 <= s - i <= n-1 且 $gcd(s, i) = d$。

不等式直接解,反正解出来一定是个区间。只需要考虑 $gcd(s, i) = d$ 的情况。 这个理论上来讲要用莫比乌斯反演,但其实只需要按 i 从大到小算,每次枚举出一个 p 满足 i | p | s,然后用 i 的答案容斥掉 p 的答案。因为从大到小计算,所以处理到 i 时一定会把 p 对应的正确答案处理出来。

时间复杂度是 i | p | s 这样的三元组数量,粗略分析应该是 $O(n\log^2n)$ 级别的。

@part - 3@

我们正式来考虑如何证明 $E(g_i(s)*g_j(s)) = (\frac{1}{k})^{n - \max(i+j-n, gcd(i, j))}$。

先建一张 n 个点的图,如果存在一个长度为 x 的周期,则用边连接所有的 (y, y + x)。 这样连接下来,同一个连通块的取值一定相同。如果令连通块数量为 c,则一共会有 k^c 种不同的字符串。 又因为总字符串个数为 k^n,于是概率就为 $\frac{k^c}{k^n} = (\frac{1}{k})^{n-c}$

首先当 i + j <= n 时,根据弱周期引理(这个搜金策的 WC 字符串课件就可以搜到),一定存在 gcd(i, j) 的周期,因此连通块数量 c = gcd(i, j)。 又因为 i + j <= n 时 gcd(i, j) > 0 >= i + j - n,所以我们的答案式子正确。

接下来考虑 i + j > n 时,不失一般性,令 i > j。又因为 i + j > n,所以 i > n - j。 我们考虑先将原来 n 个图通过长度为 i 的周期连边,连所有的 (y, y + i)。这样连出来的连通块个数一定为 i,且分别代表了长度为 i 的循环中的 0...i-1 的所有位置(注意这里是从 0 开始编号)。 不妨按这个连通块表示的在长度为 i 的循环中的位置给连通块依次编号为 0...i-1。

接下来,对于每一个 0 <= z < n - j,我们连 (z, (z + j) mod i)。注意 z < n - j < i。 每加入一条边,在不形成环的情况下会使得连通块的数量减少 1。但假如形成了环,结论就不成立了。 但是考虑上面的连边其实形成了一个置换第一部分,而这个类型的置换在做 polya 的模板题时就用过它的性质: (1)假如最终形成了多个环,那么所有环的大小一定为 i / gcd(i, j)。 (2)假如加入 (z, (z + j) mod i) 形成了环,那么之后加入的所有边都会形成环。 由此,我们可以得出:假如形成了环,那么连通块个数 c 一定为 gcd(i, j);且第一个形成的环的 z = i - gcd(i, j)。

因此,假如 z = i - gcd(i, j) < n - j,即 i + j - n < gcd(i, j),那么 c = gcd(i, j);否则 c = i - (n - j) = i + j - n。 至此,我们的结论就证明完毕了。

@solution@

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100000;
const int MOD = int(1E9) + 7;
int gcd(int a, int b) {
	return (b == 0) ? a : gcd(b, a % b);
}
int pow_mod(int b, int p) {
	int ret = 1;
	while( p ) {
		if( p & 1 ) ret = 1LL*ret*b%MOD;
		b = 1LL*b*b%MOD;
		p >>= 1;
	}
	return ret;
}
int n, m, k, ans;
void update(int d, int s, int p) {
	ans = (ans + 1LL*p*pow_mod(k, MOD - 1 + max(s - n, d) - n)%MOD)%MOD;
}
vector<int>dv[2*MAXN + 5];
void init() {
	for(int i=1;i<=m;i++)
		for(int j=i;j<=m;j+=i)
			dv[j].push_back(i);
}
int f[2*MAXN + 5];
int main() {
	scanf("%d%d", &n, &k), m = 2*(n - 1);
	init();
	for(int s=1;s<=m;s++) {
		int l = max(1, s - (n - 1)), r = min(n - 1, s - 1);
		for(int j=dv[s].size()-1;j>=0;j--) {
			int d = dv[s][j], p = s / d;
			f[d] = r / d - (l - 1) / d;
			for(int k=1;k<dv[p].size();k++)
				f[d] = (f[d] + MOD - f[d*dv[p][k]])%MOD;
			update(d, s, f[d]);
		}
	}
/*
	for(int i=1;i<=n-1;i++)
		for(int j=1;j<=n-1;j++)
			update(gcd(i, j), i + j, 1);
*/
	printf("%d\n", ans);
}

@details@

原来div1的E这么水。

好像因为我用了 vector 所以跑得非常慢。。。 但是也不确定,说不定可能是我时间复杂度一不小心写多了个什么奇怪的东西。。。。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部