@codeforces - 1205E@ Expected Value Again

朴灿烈づ我的快乐病毒、 2023-06-01 13:59 3阅读 0赞

*  @description@
 *  @solution@
    
     *  @part - 1@
     *  @part - 2@
     *  @part - 3@
 *  @solution@
 *  @details@

--------------------

## @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 所以跑得非常慢。。。  
但是也不确定，说不定可能是我时间复杂度一不小心写多了个什么奇怪的东西。。。。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11402012.html