22蔚来9 mancher 字符串哈希 概率计算 前缀和优化

chenxuming · 2022-08-15 20:06:00 · 个人记录

first E magic spell

• 字符串哈希，双哈希，manacher

• 题目大意： 给定k<=5字符串。计算多个字符串之间本质相同的回文公共子子串的数目。

• 经验总结：

  • 字符串哈希，wa时的考虑点：
  • 是否卡哈希，尝试双哈希的策略。

自己的ac代码：

#include <bits\stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef pair<ULL, ULL> llp;
const ULL X = 131;
string str[6];
vector<ULL> p, h, pp, hh;
string s;
set<llp> mmset[6];
ULL ans;
ULL mod = 1e9 + 7, mmod = 1e9 + 3;
void BKDR_hash() //初始化,这里没有使用双哈希。
{
    hh[0] = s[0];
    h[0] = s[0];
    p[0] = 1;
    pp[0] = 1;
    for (int i = 1, size = s.size(); i < size; i++)
    {
        h[i] = (h[i - 1] * X + s[i]) % mod;
        p[i] = (p[i - 1] * X) % mod;
        hh[i] = (hh[i - 1] * X + s[i]) % mmod;
        pp[i] = (pp[i - 1] * X) % mmod;
    }
}
llp get_hash(int l, int r)
{
    ULL a, b;
    a = l ? (h[r] - h[l - 1] * p[r - l + 1]%mod+mod) % mod : h[r];
    b = l ? (hh[r] - hh[l - 1] * pp[r - l + 1]%mmod+mmod) % mmod : hh[r];
    return llp(a, b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int kk;
    cin >> kk;
    for (int i = 1; i <= kk; i++)
        cin >> str[i];
    for (int j = 1; j <= kk; j++)
    {

        //完成初始化。
        s.clear();
        h.clear();
        hh.clear();
        pp.clear();
        p.clear();
        s = str[j];
        //先
        int n = s.length();
        p.resize(n);
        pp.resize(n);
        hh.resize(n);
        h.resize(n);
        vector<int> d1(n);
        BKDR_hash();
        for (int i = 0, l = 0, r = -1, k; i < n; i++)
        {
            k = (i > r) ? 1 : min(d1[l + r - i], r - i + 1);
            mmset[j].insert({ s[i], s[i] });
            while (i - k >= 0 && i + k < n && s[i - k] == s[i + k])
            {
                mmset[j].insert(get_hash(i - k, i + k));
                k++;
            }
            d1[i] = k--;
            if (i + k > r)
                l = i - k, r = i + k;
        }
        vector<int> d2(n);
        for (int i = 0, l = 0, r = -1, k; i < n; i++)
        {
            k = (i > r) ? 0 : min(d2[l + r - i + 1], r - i + 1);
            while (i - k - 1 >= 0 && i + k < n && s[i - k - 1] == s[i + k])
            {
                mmset[j].insert(get_hash(i - k - 1, i + k));
                k++;
            }
            d2[i] = k--;
            if (i + k > r)
            {
                l = i - k - 1;
                r = i + k;
            }
        }
    }
    //所有的哈希值已经记录完毕
    for (auto i : mmset[kk])
    {
        bool found = true;
        for (int j = 1; j < kk; j++)

        {
            if (mmset[j].count(i) == 0)
            {
                found = false;
                break;
            }
        }
        if (found)
            ans++;
    }
    cout << ans << '\n';
}

不够简洁。优化方向如下

• manacher 用填充式数组，并且利用 for(\quad auto\quad) 语法构造s。
• 双哈希，步骤处理优化。想一下还可以怎样做。

记得补！！！

Second Two Frogs

• two fogs
• 概率dp , 逆元 ，前缀和， 差分。
• 题意：
  • 河道里有n荷叶排成一排，从第i个荷叶出发可以跳到第(i,i+a_i]个荷叶上，有两只青蛙从第1个荷叶出发，每一步都独立地等概率随机地跳向后边的荷叶，求两只青蛙以相同步数到达第n个荷叶的概率。 n≤8000，保证1≤a_i≤n-i。

• 思路

  • 定义f_{i,j}为青蛙跳跃i步来到第j片荷叶的概率。
  • 研究其和其他状态的关系有该状态对f_{i,j+k},k<=a[j]有f_{i,j}/a_j的贡献。
  • 由于计算状态对其他状态的贡献时，是区间加的形式，可以采取差分，前缀和优化 方案。将复杂度=降低为O(n^2).
  • 最终结果为\sum ^{n-1}_{i=1}f \left[ i\right] \left[ n\right]

新知识补充，由于提高check的精度，对结果采取求模运算作为答案。分数求模运算中引入逆元。

• $$(a/b+c/d)\%P=a/b\%P+c/d\%P$$

• 在处理贡献的过程中就可以紧接着将分数，按照运算转化成整数的结果，避开了分数同分运算的模拟。

逆元myself

• 借鉴oiwiki。

  myself

  #include <bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  const int maxn = 8010;
  ll a[maxn];
  ll inv[maxn];     //逆元。使每个数的逆元
  ll f[maxn][maxn]; //
  ll p = 998244353;
  void get_inv(int n) // inverse 逆元。按照题目规则来求你元的方法
  {              //线性求逆元。线性方法求逆元。
  inv[1] = 1;
  for (int i = 2; i <= n; ++i)
      inv[i] = (ll)(p - p / i) * inv[p % i] % p;
  } //这样每一个逆元出来了，对贡献的每一个分数，通过定义转化为逆元。不用进行分数相机模拟。
  int main()
  {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++)
      cin >> a[i];
  f[0][1] = 1;
  get_inv(n);
  for (int i = 0; i <= n; i++) // n-1步必定来到最后一个点。
  {
      if (i)
          for (int j = 1; j <= n; j++)
              f[i][j] = (f[i][j - 1] + f[i][j]) % p;
      for (int j = 1; j <= n; j++) //在什么点开始进行跳跃。//区间加考虑差分。
      {
          f[i + 1][j + a[j] + 1] -= f[i][j] * inv[a[j]] % p;
          f[i + 1][j + 1] += f[i][j] * inv[a[j]] % p;
      }
  }
  ll ans = 0;
  for (int i = 1; i <= n; i++)
      ans += f[i][n] * f[i][n], ans %= p;
  cout << ans << '\n';
  }