原题呈现

P15862 回去！#

题目描述#

有一个 $n$ 个点 $n$ 条边的有向图 $G$ ，满足每个点的出度为 $1$ ．每个点有一个小写字母作为权值．

现在 DZ1000 准备在 $G$ 上游走，他打算用一个字符串 $s$ 和一个栈 $t$ 来记录他的行程．初始时栈 $t$ 为空．

每一步他都有两种可能的行动选择：

「前进？」：DZ1000 有 $p$ 的概率沿着当前点的出边移动，并将他到达的节点放进栈 $t$ 中．
「回去！」：DZ1000 有 $(1-p)$ 的概率弹出栈 $t$ 顶部的节点，然后回到当前位于栈 $t$ 顶部的节点．（若行动前栈 $t$ 为空则他不会这么做且一定会前进，若行动前栈 $t$ 大小为 $1$ 则回到起点．）

每走完一步，DZ1000 都会将当前他所在节点的权值接在字符串 $s$ 的后面．

现在 DZ1000 将从 $G$ 上等概率随机选择一个起始节点，开始走 $2k$ 步，他想让你求出走完 $2k$ 步后字符串 $s$ 的前 $k$ 位和后 $k$ 位相等的概率．答案乘上 $n$ 后对 $99\textcolor{#fec52b}8,\textcolor{purple}{24}4,353$ 取模．

注意起始节点的权值不等同于字符串 $s$ 的第一位．

输入格式#

输入共 $3$ 行．

第一行，三个正整数 $n,k,p$ ，分别表示 $G$ 的点数、行动的步数和往前进的概率（ $p$ 原本是一个介于 $0$ 和 $1$ 之间的有理数，现给出其对 $99\textcolor{#fec52b}8,\textcolor{purple}{24}4,353$ 取模后的结果）．

第二行，由小写字母组成的长度为 $n$ 的字符串，第 $i$ 个字母 $c_i$ 表示 $i$ 号点的权值．

第三行， $n$ 个正整数 $v$ ，第 $i$ 个正整数 $v_i$ 表示 $i$ 号点出边指向的点．

输出格式#

输出共 $1$ 行，一个正整数表示走完 $2k$ 步后字符串 $s$ 的前 $k$ 位和后 $k$ 位相等的概率乘 $n$ 的结果，对 $99\textcolor{#fec52b}8,\textcolor{purple}{24}4,353$ 取模．

输入输出样例 #1#

输入 #1#

1
3 1 499122177
2
aba
3
2 3 1

输出 #1#

1
1

输入输出样例 #2#

输入 #2#

1
10 10 882315098
2
nqqmlmnnon
3
6 3 4 1 4 4 9 4 10 7

输出 #2#

1
106458929

说明/提示#

样例 $1$ 解释#

$\frac12$ 在模 $998244353$ 下是 $499122177$ ，故原始的 $p=\frac12$ ．

有如下路径：

$1\to 2\to 3$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 ba，不符合条件．
$1\to 2\to 1$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 ba，不符合条件．
$2\to 3\to 1$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 aa，符合条件．
$2\to 3\to 2$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 ab，不符合条件．
$3\to 1\to 2$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 ab，不符合条件．
$3\to 1\to 3$ ，概率为 $\frac1n\times p=\frac16$ ，字符串为 aa，符合条件．

故有 $\frac16+\frac16=\frac13$ 的概率符合条件，乘 $n$ 的结果为 $1$ ，故输出 $1$ ．

数据规模#

对于 $100\%$ 的数据，满足 $1 \le n \le 30,1 \le k \le 30$ ．

子任务编号	$n$	$k$	特殊性质	分值
$1$	$\le 9$	$\le 9$	无	$5$
$2$	无特殊限制	^	^	$10$
$3$	^	$\le 17$	^	$30$
$4$	^	无特殊限制	A	$5$
$5$	^	^	B	$5$
$6$	^	^	C	$10$
$7$	^	^	无	$35$

特殊性质 A：所有 $c_i$ 相同．

特殊性质 B：对于任意 $1\le i\le n$ ，有 $v_i=i$ ．

特殊性质 C：对于任意 $1\le i<n$ ，有 $v_i=i+1$ ，且 $v_n=1$ ．

思路#

由于每一个节点出度相同，考虑枚举起点．如果枚举了起点，一直往前走的整条路径就固定了，可以将其预处理出来．将图上的问题转化为链上的问题．

接下来，问题转化为：有一个人在一条链上跳，可以向前跳，也可以向后跳，但是不能跳出界．问如何跳才能满足得到的字符串前 $k$ 个和后 $k$ 个相等．

由于想要前后两半相等，可以想象有两个人，一个人跳前半段，一个人跳后半段，枚举权值与第一个点 $fi$ 相等的点 $se$ ，两人从 $fi$ 和 $se$ 开始跳，每跳一步都保证落点权值相等，且最终第一个人的最终落点和第二个人的起点相邻的可能．

为了计算可能性，我们定义 dp[i][x][y] 表示两个人都走了 i 步，第一个人走到 x，第二个人走到 y 这种情况的可能性．

存在如下初始状态：

1
dp[1][fi][se] = 1;

存在如下转移方程：

1
int q = (1 - p + MOD) % MOD; // 后退的概率
2
if (x - 1 >= 0) {
3
  int p1 = (x - 1 == 0) ? 1 : p; // 玩家 1 前进的概率
4
  if (y - 1 >= 0) {
5
    int p2 = (y - 1 == 0) ? 1 : p; // 玩家 2 前进的概率
6
    // 都前进
7
    dp[i][x][y] =
8
      (dp[i][x][y] + 1ll * dp[i - 1][x - 1][y - 1] *
9
                 (1ll * p1 * p2 % MOD)) %
10
      MOD;
11
  }
12
  if (y + 1 <= 2 * k)
13
    // 玩家 1 前进，玩家 2 后退
14
    dp[i][x][y] =
15
      (dp[i][x][y] + 1ll * dp[i - 1][x - 1][y + 1] *
16
                 (1ll * p1 * q % MOD)) %
17
      MOD;
18
}
19
if (x + 1 <= 2 * k) {
20
  if (y - 1 >= 0) {
21
    // 玩家 1 后退，玩家 2 前进
22
    int p2 = (y - 1 == 0) ? 1 : p; // 玩家 2 前进的概率
23
    dp[i][x][y] =
24
      (dp[i][x][y] + 1ll * dp[i - 1][x + 1][y - 1] *
25
                 (1ll * q * p2 % MOD)) %
26
      MOD;
27
  }
28
  if (y + 1 <= 2 * k)
29
    // 都后退
30
    dp[i][x][y] =
31
      (dp[i][x][y] + 1ll * dp[i - 1][x + 1][y + 1] *
32
                 (1ll * q * q % MOD)) %
33
      MOD;
34
}

统计结果时，只统计第一人终点和第二人起点相邻的情况：

1
for (int x = 0; x <= 2 * k; x++) { // 枚举第一人终点
2
  if (x != se - 1 && x != se + 1)
3
    continue; // 距离恰好等于 1
4
  int bp = (se == x + 1) ? ((x == 0) ? 1 : p) : q; // 连接步（k->k+1）走对的概率
5
  long long s = 0;
6
  for (int y = 0; y <= 2 * k; y++) // 枚举第二人终点
7
    s += dp[k][x][y];
8
  ans = (ans + (s % MOD) * bp) % MOD;
9
}

显然，通过观察，我们不难发现，dp[i][..][..] 的值只与 dp[i-1][..][..] 有关，因此可以使用滚动数组优化．

标程

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int MOD = 998244353;
4
const int N = 70;
5
int n, k, p;
6
char c[N];
7
int nxt[N];
8
int dp[2][N][N]; // 使用滚动数组
9
vector<int> pane;
10
int ans;
11

12
void start(int fi, int se) {
13
    memset(dp, 0, sizeof(dp));
14
    dp[1][fi][se] = 1;
15
    int q = (1 - p + MOD) % MOD;
16
    for (int i = 2; i <= k; i++) {
17
        int cur = i & 1, pre = (i - 1) & 1;
18
        // cur => i; pre => i - 1
19
        for (int x = 0; x <= 2 * k; x++) {
20
            for (int y = 0; y <= 2 * k; y++) {
21
                dp[cur][x][y] = 0;
22
                if (c[pane[x]] != c[pane[y]])
23
                    continue;
24
                if (x - 1 >= 0) {
25
                    int p1 = (x - 1 == 0) ? 1 : p;
26
                    if (y - 1 >= 0) {
27
                        int p2 = (y - 1 == 0) ? 1 : p;
28
                        dp[cur][x][y] =
29
                            (dp[cur][x][y] + 1ll * dp[pre][x - 1][y - 1] *
30
                                                 (1ll * p1 * p2 % MOD)) %
31
                            MOD;
32
                    }
33
                    if (y + 1 <= 2 * k)
34
                        dp[cur][x][y] =
35
                            (dp[cur][x][y] + 1ll * dp[pre][x - 1][y + 1] *
36
                                                 (1ll * p1 * q % MOD)) %
37
                            MOD;
38
                }
39
                if (x + 1 <= 2 * k) {
40
                    if (y - 1 >= 0) {
41
                        int p2 = (y - 1 == 0) ? 1 : p;
42
                        dp[cur][x][y] =
43
                            (dp[cur][x][y] + 1ll * dp[pre][x + 1][y - 1] *
44
                                                 (1ll * q * p2 % MOD)) %
45
                            MOD;
46
                    }
47
                    if (y + 1 <= 2 * k)
48
                        dp[cur][x][y] =
49
                            (dp[cur][x][y] + 1ll * dp[pre][x + 1][y + 1] *
50
                                                 (1ll * q * q % MOD)) %
51
                            MOD;
52
                }
53
            }
54
        }
55
    }
56
    int bk = k & 1;
57
    for (int x = 0; x <= 2 * k; x++) {
58
        if (x != se - 1 && x != se + 1)
59
            continue; // 距离恰好等于 1
60
        int bp = (se == x + 1) ? ((x == 0) ? 1 : p) : q;
61
        long long s = 0;
62
        for (int y = 0; y <= 2 * k; y++)
63
            s += dp[bk][x][y];
64
        ans = (ans + (s % MOD) * bp) % MOD;
65
    }
66
}
67
void solve(int st) {
68
    pane.clear();
69
    for (int i = 1; i <= 2 * k + 1; i++) {
70
        pane.push_back(st);
71
        st = nxt[st];
72
    }
73
    for (int i = 0; i <= 2 * k; i++) {
74
        if (c[pane[i]] == c[pane[1]]) {
75
            start(1, i);
76
        }
77
    }
78
}
79
signed main() {
80
    cin >> n >> k >> p;
81
    for (int i = 1; i <= n; i++)
82
        cin >> c[i];
83
    for (int i = 1; i <= n; i++)
84
        cin >> nxt[i];
85
    for (int i = 1; i <= n; i++)
86
        solve(i);
87
    cout << (ans + MOD) % MOD;
88
}

实际上，对于一个对象进行两组重复的动作时，这也可以等同于两个对象分别做一组相同的动作．

音乐

音乐

P15862 回去！#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

样例 $1$ 解释#

数据规模#

思路#

文章分享

音乐

安吉D1-L

P15862 回去！#

题目描述#

输入格式#

输出格式#

输入输出样例 #1#

输入 #1#

输出 #1#

输入输出样例 #2#

输入 #2#

输出 #2#

说明/提示#

样例 111 解释#

数据规模#

思路#

文章分享

样例 $1$ 解释#