P9522 [JOISC2022] 错误拼写

· · 题解

P9522 [JOISC2022] 错误拼写

考虑 T_{i}\leq T_{j} 的等价条件。模拟字典序比较的过程：

考虑从后往前 DP，设 f_{i, j} 表示 s_i = j 的方案数。计算 f_{i, j} 时，枚举 i' 表示 s_{i\sim i' - 1} 相等且 s_{i' - 1}\neq s_{i'}，枚举 j'\neq j。考虑什么情况下 f_{i, j} 可以从 f_{i', j'} 转移过来：如果存在 i\leq u < i' \leq v 要求 T_u\leq T_v，那么 j 不能小于 j'；若要求 T_u\geq T_v，那么 j 不能大于 j'。

设 u < v，则：

这说明，固定了 i' 之后，随着 i 不断向前移动，存在一个时刻使得 i' 不再能产生 j > j' 的贡献，也存在一个时刻使得 i' 不再能产生 j < j' 的贡献。

设 h_j 表示 f_{i + 1}\sim f_n 对之前的位置的每个 j 产生的贡献。枚举到 i 时，考虑所有和 i 有关的限制 (u, v)（u = i < v）

更新 h 之后有 f_{i, j} = h_j + 1，其中 1 表示 s_{i\sim n} 均相等的情况。统计 f_i 对 h 的贡献：h_{j} 加上 \sum_{j'\neq j} f_{i, j'}。

用链表或栈维护两种情况仍产生贡献的 i'，时间复杂度 \mathcal{O}(n|\Sigma|)。

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

using ll = long long;
using LL = __int128_t;
using ui = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(20060130);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 1e9 + 7;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}

char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + \
  fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
inline int read() {
  int x = 0;
  char s = getc();
  while(!isdigit(s)) s = getc();
  while(isdigit(s)) x = x * 10 + s - '0', s = getc();
  return x;
}

#define putc(x) putchar(x)
inline void print(ui x) {
  if(x >= 10) print(x / 10);
  putc(x % 10 + '0');
}

// ---------- templates above ----------

constexpr int N = 5e5 + 5;

int n, m, f[N][27], h[27];
int a[N], b[N], x[N], y[N];
vector<int> e[N], g[N];

void mian() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) a[i] = b[i] = i + 1;
  for(int i = 1; i <= m; i++) {
    int x, y;
    cin >> x >> y;
    if(x < y) e[x].push_back(y);
    else g[y].push_back(x);
  }
  for(int i = n; i; i--) {
    for(int it : e[i]) {
      for(int p = a[i]; p <= it; p = a[p]) {
        vector<int> s(27);
        for(int j = 1; j <= 26; j++) s[j] = add(s[j - 1], f[p][j]);
        for(int j = 1; j <= 26; j++) addt(h[j], mod - add(s[26], mod - s[j]));
        a[i] = a[p];
      }
    }
    for(int it : g[i]) {
      for(int p = b[i]; p <= it; p = b[p]) {
        vector<int> s(27);
        for(int j = 1; j <= 26; j++) s[j] = add(s[j - 1], f[p][j]);
        for(int j = 1; j <= 26; j++) addt(h[j], mod - s[j - 1]);
        b[i] = b[p];
      }
    }
    int sum = 0;
    for(int j = 1; j <= 26; j++) {
      f[i][j] = h[j] + 1;
      addt(h[j], mod - f[i][j]);
      addt(sum, f[i][j]);
    }
    if(i == 1) cout << sum << "\n";
    for(int j = 1; j <= 26; j++) addt(h[j], sum);
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T = 1;
  while(T--) mian();
  fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
  return 0;
}

/*
g++ a.cpp -o a -std=c++14 -O2 -DALEX_WEI
*/