题解：CF2174C1 Beautiful Patterns (Easy Version)

· · 题解

题目大意

给你三个整数 n,m,p，问你长度为 n，值域为 [1,m]，求这个字符串的回文子串个数的平方在模 p 意义下的期望。

分析

首先，设 f(l,r) 表示 [l,r] 这个字串是否为回文串。那么答案即为：

E((\sum f(l,r))^2)=E((\sum f(l,r))\times (\sum f(l,r)))=E(\sum f^2(l,r))+2E(\sum_{(l,r)\not=(l',r')}f(l,r)\times f(l',r'))

此时发现这个式子可以分为两个步骤来计算。

计算 E(\sum f^2(l,r))

首先，这个平方让人很难受，但是因为 f(l,r) 的取值只有 0 和 1，所以完全可以把平方去掉，于是变成了计算每一个字串是回文串的概率了。

首先设我们枚举到的区间长度为 len，那么此时可以选出 n-len+1 个位置不同的方案。然后，对于每一个方案，发现如果这个串是一个回文串，我们只需要确定前 \lceil \frac{len}{2}\rceil 个元素，那么后面那一半就确定了。所以回文串的方案数即为 m^{\lceil \frac{len}{2}\rceil} 个，因为总方案数为 m^{len}，则总期望为 \sum_{len=1}^{n}(n-len+1)\times\frac{m^{\lceil \frac{len}{2}\rceil}}{m^{len}}，这便是前面这个式子的值。

计算 2E(\sum_{(l,r)\not=(l',r')}f(l,r)\times f(l',r'))

这其实就是求两个子串同时为回文串时的期望，我们设这两个子串的长度分别为 len_1 和 len_2，这时候我们分个类：

  1. 两个子串有共同的中点。此时很明显期望取决于长的那个子串，即 \frac{m^{\lceil \frac{\max(len_1,len_2)}{2}\rceil}}{m^{\max(len_1,len_2)}}。
  2. 两个子串没有共同的中点，且不相交。这个时候明显两个字符串互不影响，答案为 \frac{m^{\lceil \frac{len_1}{2}\rceil}}{m^{len_1}}\times\frac{m^{\lceil \frac{len_2}{2}\rceil}}{m^{len_2}}=\frac{m^{\lceil \frac{len_1}{2}\rceil+\lceil \frac{len_2}{2}\rceil}}{m^{len_1+len_2}}。
  3. 两个子串没有共同的中点，且相交。此时设相交长度为 L，此时还要分类：

然后我们惊奇的发现，第 2、3 个情况的答案是一样的。所以这题就做完了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e3 + 10;
int T, n, m, p, now[N];

int qpow(int x, int y, const int MOD) {
  int ans = 1;
  while(y) {
    if(y & 1) {
      ans = ans * x % MOD;
    }
    x = x * x % MOD;
    y >>= 1;
  }
  return ans;
}

void solve() {
  cin >> n >> m >> p;
  int ans = 0;
  for(int i = 1; i <= n; i++) {
    now[i] = qpow(m, (i + 1) / 2, p) * qpow(qpow(m, i, p), p - 2, p) % p;
    ans = (ans + now[i] * (n - i + 1) % p) % p;
  }
  for(int l1 = 1; l1 <= n; l1++) {
    ans = (ans + now[l1] * (n - l1 + 1) % p * ((l1 - 1) / 2) % p * 2 % p) % p;
    for(int l2 = 1; l2 < l1; l2++) {
      ans = (ans + now[l1] * now[l2] % p * (n - l1 + 1) % p * (n - l2 + ((l2 & 1) ^ (l1 & 1))) % p * 2 % p) % p;
    }
    ans = (ans + (n - l1 + 1) * (n - l1) % p * now[l1] % p * now[l1] % p) % p;
  }
  cout << ans << "\n";
}

signed main() {

  cin >> T;
  while(T--) {
    solve();
  }

  return 0;
}

完结撒花★,°:.☆(￣▽￣)/$:.°★ 。