About / 关于 Archive / 归档 Categories / 分类 Tags / 标签 Friends / 友链 RSS
- 目录 -
POI2008 选做
folder OI 题解   schedule 13 min 5 s.

P3473 UCI - The Great Escape

简要题意: 给一个 $n\times m$ 的地图，计算从 $(n,1)$ 到第 $x$ 列的第 $y$ 行的路径条数 $\bmod k$，走过的点不能再走，转弯只能向右转。

数据规模: $n,m \le 100$。

题解: 走过的点不能再走，并且只能向右转，容易发现在此之后能够到达的点一定在某个围成的矩形内。设 dp 状态 $dp[u][d][l][r][x]$，$u,d,l,r$ 分别表示当前矩形的上下左右边界，$x$ 表示下一步的方向。初始状态从 $(x,y)$ 开始，转移时枚举往 $x$ 方向走多少步再转弯，可以做到 $O(n^5)$，具体方程如下，其中 $\mathrm{check}(k)$ 表示判断路径是否没有障碍：

$$ \begin{aligned} dp[u][d][l][r][\text{Up}] &= \sum [\mathrm{check(k)}]dp[k][d][l+1][r][\text{Ri}] \\ dp[u][d][l][r][\text{Dn}] &= \sum [\mathrm{check(k)}]dp[u][k][l][r-1][\text{Le}] \\ dp[u][d][l][r][\text{Le}] &= \sum [\mathrm{check(k)}]dp[u][d-1][k][r][\text{Up}] \\ dp[u][d][l][r][\text{Ri}] &= \sum [\mathrm{check(k)}]dp[u+1][d][l][k][\text{Dn}] \\ \end{aligned} $$

上述 dp 容易通过前缀和优化，以向上为例，有如下转移方程：

$$ dp[u][d][l][r][\text{Up}] = dp[u+1][d][l][r][\text{Up}] + [\mathrm{check}(u)]dp[u][d][l+1][r][\text{Ri}] $$

于是时间复杂度就变成了 $O(n^4)$。但是空间还会炸，所以考虑滚动数组优化一下。注意到在上述转移方程中，令 $sum = d-u+1+r-l+1$，不难看出 $sum$ 总是由 $sum-1$ 转移得到，在这一维进行滚动数组即可。

代码:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

using ll = long long;
const int N = 105;
int n, m, tx, ty, mod, s1[N][N], s2[N][N], dp[2][N][N][N][4];
char mp[N][N];
enum direction { UP = 0, DN = 1, LE = 2, RI = 3 };
signed main() {
  read(n), read(m), read(mod), read(ty), read(tx);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", mp[i] + 1);
    for (int j = 1; j <= m; ++j) {
      s1[i][j] = s1[i][j - 1] + (mp[i][j] == '*');
      s2[i][j] = s2[i - 1][j] + (mp[i][j] == '*');
    }
  }
  int k = 0;
  for (int sum = 2; sum <= n + m; ++sum) {
    k ^= 1, memset(dp[k], 0, sizeof(dp[k]));
    for (int lx = 1, ly = sum - lx; lx <= n; ++lx, --ly) {
      if (ly < 1 || ly > m)
        continue;
      for (int u = 1, d = lx; d <= n; ++u, ++d) {
        if (u > tx || d < tx)
          continue;
        for (int l = 1, r = ly; r <= m; ++l, ++r) {
          if (l > ty || r < ty)
            continue;
          int *cur = dp[k][d][l][r];
          auto get = [&](int u, int d, int l, int r, int dir) -> int {
            return dp[k ^ 1][d][l][r][dir];
          };
          cur[UP] = get(u, d, l + 1, r, RI) + (u == tx && l == ty);
          cur[UP] = cur[UP] * (s2[d][l] == s2[u - 1][l]);
          cur[UP] = cur[UP] + get(u + 1, d, l, r, UP);
          cur[DN] = get(u, d, l, r - 1, LE) + (d == tx && r == ty);
          cur[DN] = cur[DN] * (s2[d][r] == s2[u - 1][r]);
          cur[DN] = cur[DN] + get(u, d - 1, l, r, DN);
          cur[LE] = get(u, d - 1, l, r, UP) + (d == tx && l == ty);
          cur[LE] = cur[LE] * (s1[d][r] == s1[d][l - 1]);
          cur[LE] = cur[LE] + get(u, d, l + 1, r, LE);
          cur[RI] = get(u + 1, d, l, r, DN) + (u == tx && r == ty);
          cur[RI] = cur[RI] * (s1[u][r] == s1[u][l - 1]);
          cur[RI] = cur[RI] + get(u, d, l, r - 1, RI);
          cur[UP] %= mod, cur[DN] %= mod, cur[LE] %= mod, cur[RI] %= mod;
        }
      }
    }
  }
  write(dp[k][n][1][m][0]), putchar('\n');
  return 0;
}

P3474 KUP - Plot Purchase

简要题意: 给定 $k,n$，和 $n \times n$ 的矩阵，求一个子矩阵满足权值和在 $[k,2k]$ 之间。

数据规模: $n \le 2000,\ 1\le k \le 10^9,\ 0\le a_{i,j} \le 2\times 10^9$。

题解: 神仙题。首先考虑矩阵中的每一个数 $a_{i,j}$，如果 $k \le a_{i,j} \le 2k$，直接输出即可；如果 $a_{i,j} \gt 2k$，则这个点一定不能被最终的矩形所包含。

现在矩阵中只剩下 $< k$ 的数，考虑其中一个子矩阵，其权值和为 $sum$，仍然分为 $3$ 种情况讨论。

  1. $sum < k$，这个子矩阵一定无法满足权值和在 $[k,2k]$ 之间。
  2. $k \le sum \le 2k$，直接输出这个子矩阵即可。
  3. $sum > 2k$，可以发现若存在这样的子矩阵，且矩阵中的所有数权值均 $< k$，则一定能切出该子矩阵的子矩阵，使得其权值和在 $[k,2k]$ 之间。下面将给出一种构造方法。

考虑子矩阵的每一行，设此行的权值和为 $s$。若 $k \le s \le 2k$，直接取出这一行；若 $s > 2k$，则一定存在该行的一个子区间，其权值和在 $[k,2k]$ 之间，取出这个子区间作为答案。因此，若存在 $s \ge k$ 的行，直接取出这一行的某个区间输出即可。

若不存在 $s \ge k$ 的行，则所有行都满足 $s < k$。此时由于 $sum > 2k$，一定能够取出若干连续的行，使得这些行的权值和在 $[k,2k]$ 之间。$\square$

综上所述，只需要找到原矩阵的任意不包含 $>2k$ 的数的子矩阵，使得其权值和 $\ge k$，就能构造出权值和在 $[k,2k]$ 中的子矩阵。因此，只需要使用悬线法或单调栈找到原矩阵剔除 $> 2k$ 的元素后的最大子矩阵，即可按照上述方法进行构造。总体时空复杂度为 $O(n^2)$。

代码:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

using ll = long long;
const int N = 2e3 + 10;
int n, k, sta[N], pre[N], nxt[N], a[N][N], up[N][N];
ll num[N], prf[N], sum[N][N];
inline ll asksum(int sx, int sy, int tx, int ty) {
  return sum[tx][ty] - sum[sx - 1][ty] - sum[tx][sy - 1] + sum[sx - 1][sy - 1];
}
inline void output(int sx, int sy, int tx, int ty) {
  printf("%d %d %d %d\n", sy, sx, ty, tx), exit(0);
}
signed main() {
  read(k), read(n);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
      read(a[i][j]);
      if (k <= a[i][j] && a[i][j] <= 2 * k)
        output(i, j, i, j);
      up[i][j] = (a[i][j] >= k) ? 0 : up[i - 1][j] + 1;
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
    }
  ll ans = 0;
  int sx = 0, sy = 0, tx = 0, ty = 0;
  for (int i = 1; i <= n; ++i) {
    sta[0] = 0;
    for (int j = 1, tp = 0; j <= n; ++j) {
      while (tp && up[i][sta[tp]] >= up[i][j])
        --tp;
      pre[j] = sta[tp] + 1, sta[++tp] = j;
    }
    sta[0] = n + 1;
    for (int j = n, tp = 0; j >= 1; --j) {
      while (tp && up[i][sta[tp]] >= up[i][j])
        --tp;
      nxt[j] = sta[tp] - 1, sta[++tp] = j;
    }
    for (int j = 1; j <= n; ++j) {
      int ax = i - up[i][j] + 1, bx = i, ay = pre[j], by = nxt[j];
      ll cur = asksum(ax, ay, bx, by);
      if (cur > ans)
        tie(ans, sx, sy, tx, ty) = make_tuple(cur, ax, ay, bx, by);
    }
  }
  if (ans < k) {
    return puts("NIE"), 0;
  } else if (k <= ans && ans <= 2 * k) {
    output(sx, sy, tx, ty);
  }
  for (int i = sx; i <= tx; ++i) {
    for (int j = sy; j <= ty; ++j)
      num[i] += a[i][j];
    if (k <= num[i] && num[i] <= 2 * k) {
      output(i, sy, i, ty);
    } else if (num[i] > 2 * k) {
      for (int j = sy; j <= ty; ++j)
        prf[j] = prf[j - 1] + a[i][j];
      for (int j = sy, p = sy - 1; j <= ty; ++j) {
        while (prf[j] - prf[p] > 2 * k)
          ++p;
        if (prf[j] - prf[p] >= k)
          output(i, p + 1, i, j);
      }
      assert(0);
    }
  }
  fill(prf + 1, prf + n + 1, 0);
  for (int i = sx; i <= tx; ++i)
    prf[i] = prf[i - 1] + num[i];
  for (int i = sx, p = sx - 1; i <= tx; ++i) {
    while (prf[i] - prf[p] > 2 * k)
      ++p;
    if (prf[i] - prf[p] >= k)
      output(p + 1, i, sy, ty);
  }
  return assert(0), 0;
}

P3477 PER - Permutation

简要题意: 给你一个序列 $s$，序列中的元素有重复，求出将这个序列的所有不同排列按字典序排列后，$s$ 的排名 $\bmod m$。

数据规模: 序列长度 $n \le 3\times 10^5,\ 1 \le s_i \le 3\times 10^5,\ 2 \le m \le 10^9$。

题解: 根据康托展开的基本式子，不难列出答案的式子如下：

$$ Ans = 1+\sum_{i=1}^{n} \frac{(n-i)!}{\prod cnt_j!} \times \sum_{k=i+1}^{n}[a_k < a_i] $$

其中 $cnt_j$ 表示 $i$ 到 $n$ 之间 $s_k=j$ 的出现次数。

如果不是任意模数，这道题就做完了，直接用树状数组维护一下 $\sum_{k=i+1}^{n}[a_k < a_i]$ 即可。但是现在有任意模数，这意味着与 $m$ 不互质的数不存在逆元。

按照以往的套路，我们先将 $m$ 分解质因数，然后在从后往前计算 $\frac{(n-i)!}{\prod cnt_j!}$ 时，对每个质因数 $p_i$ 分别维护其次数 $k_i$，查询答案时将 $p_i^{k_i}$ 相乘。质因数的个数为 $O(\log m)$ 级别，如果用快速幂暴力求次方是 $\log^2$ 级别的复杂度，实测并不能通过。因此考虑预处理每个质因子的次方，预处理的 $k_i$ 上界是 $O(n)$ 级别的，证明只需考虑阶乘中 $p_i$ 的出现次数，即可发现上界为 $\sum_{j=1}^{+\infty}\frac{n}{p_i^j} = O(n)$。所以在筛质因子时预处理一下即可做到 $O(n \log m)$ 的优秀复杂度。

代码:

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

using ll = long long;
const int N = 3e5 + 10, K = 11;
int n, m, mod, cur, ans, a[N], cnt[N], pri[K], num[K], pws[K][N];
int qpow(int x, int y) {
  int ret = 1;
  for (; y; y >>= 1, x = 1ll * x * x % mod)
    if (y & 1)
      ret = 1ll * ret * x % mod;
  return ret;
}
void exgcd(int a, int b, int &x, int &y) {
  if (!b)
    return x = 1, y = 0, void();
  return exgcd(b, a % b, y, x), y -= a / b * x, void();
}
void getfactors(int n) {
  for (int i = 2; i * i <= n; ++i) {
    if (n % i != 0)
      continue;
    pri[++m] = i, num[m] = 0;
    while (n % i == 0)
      n /= i;
  }
  if (n != 1)
    pri[++m] = n, num[m] = 0;
  for (int i = 1; i <= m; ++i) {
    pws[i][0] = 1;
    for (int j = 1; j < N; ++j)
      pws[i][j] = 1ll * pws[i][j - 1] * pri[i] % mod;
  }
}
inline int getinv(int x) {
  int u, v;
  return exgcd(x, mod, u, v), (u + mod) % mod;
}
inline void mulx(int x) {
  for (int i = 1; i <= m; ++i)
    while (x % pri[i] == 0)
      x /= pri[i], ++num[i];
  cur = 1ll * cur * x % mod;
}
inline void divx(int x) {
  for (int i = 1; i <= m; ++i)
    while (x % pri[i] == 0)
      x /= pri[i], --num[i];
  cur = 1ll * cur * getinv(x) % mod;
}
struct binary_indexed_tree {
  int bit[N];
  void add(int x, int v) {
    for (int i = x; i < N; i += i & -i)
      bit[i] += v;
  }
  int sum(int x) const {
    int ret = 0;
    for (int i = x; i; i -= i & -i)
      ret += bit[i];
    return ret;
  }
} bit;
inline int askx() {
  int ret = cur;
  for (int i = 1; i <= m; ++i)
    ret = 1ll * ret * pws[i][num[i]] % mod;
  return ret;
}
signed main() {
  read(n), read(mod);
  for (int i = 1; i <= n; ++i)
    read(a[i]);
  cur = ans = 1, getfactors(mod);
  for (int i = n; i >= 1; --i) {
    if (i != n)
      mulx(n - i);
    divx(++cnt[a[i]]);
    ans = (ans + 1ll * bit.sum(a[i] - 1) * askx()) % mod;
    bit.add(a[i], 1);
  }
  write(ans), putchar('\n');
  return 0;
}

最后修改于 2025-07-05

Git 版本: de2abab

yaoxi-std 的博客
About / 关于 Archive / 归档 Categories / 分类 Tags / 标签 Friends / 友链 RSS
Hugo Theme Diary by Rise
移植自 Makito's Journal.

© yaoxi-std, CC BY-NC-SA 4.0 Licensed
- 目录 -