CSP题解

发表于 分类于 ， 阅读次数： 作者 Pomelorin ， CoolBreeze

CSP38 T3 月票发行

正则表达式 动态规划 矩阵快速幂

题意：长度为n（1e9）的空位有m（1e6）个被#占了不能填，其余的能填任意小写字母，问至少有一对ccf出现在cspark前的字符串数量。

点击查看题解

首先这是个计数，要不重不漏，考虑以第一个出现的ccf和ccf后第一个出现的cspark作为特征进行计数，这样就需要求出前i个没出现ccf的数量（紧接着放ccf），这个可以通过dp，很复杂，但是只能n2做，因为是左（在i第一次出现ccf）乘中间（26^空格数）乘右（在j最后一次出现cspark），固定左边，中间也不是等比数列（有#），所以没法On求，只能n2。

直接计数不行，考虑正则表达式匹配，.*ccf.*cspark.*,(.*简化为*)，就是*ccf*cspark*，dp[i][j]代表考虑到第i位，最多匹配j位正则表达式的数量。转移方法是类似kmp的失配转移，具体来说，*遇到任意字符转移到下一位c，也就是dp[i][2]=dp[i-1][1]*26，c遇到c转移到下一位c，剩下25转移到*，第二个c遇到f转移到下一位（f位置不会被匹配上，因为定义是最多能匹配到哪一位，.*代表人任意个任意符号，所以在f的必定会转移到），遇到c转移到原地，其他24转移到*……

然后就过了第一个 subtask ，\(O(11n)\)。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 1e5 + 10, inf = 1e17, mod = 998244353;

ll n, m, b[N], f[N][15];
// *ccf*cspark*
// 0123456789

void solve() {
    cin >> n >> m;
    for (ll i = 1, t; i <= m; i++) {
        cin >> t;
        b[t] = 1;
    }
    f[0][0] = 1;
    for (ll i = 1; i <= n; i++) {
        if (!b[i]) {
            f[i][0] =
                (f[i - 1][0] * 25 + f[i - 1][1] * 25 + f[i - 1][2] * 24) % mod;
            f[i][1] = f[i - 1][0];
            f[i][2] = (f[i - 1][1] + f[i - 1][2]) % mod;
            f[i][3] = 0;
            f[i][4] = (f[i - 1][2] + f[i - 1][4] * 25 + f[i - 1][5] * 24 +
                       f[i - 1][6] * 24 + f[i - 1][7] * 24 + f[i - 1][8] * 24 +
                       f[i - 1][9] * 24) %
                      mod;
            f[i][5] = (f[i - 1][4] + f[i - 1][5] + f[i - 1][6] + f[i - 1][7] +
                       f[i - 1][8] + f[i - 1][9]) %
                      mod;
            f[i][6] = f[i - 1][5];
            f[i][7] = f[i - 1][6];
            f[i][8] = f[i - 1][7];
            f[i][9] = f[i - 1][8];
            f[i][11] = (f[i - 1][9] + f[i - 1][11] * 26) % mod;
        } else {
            f[i][0] = (f[i - 1][0] + f[i - 1][1] + f[i - 1][2]) % mod;
            f[i][1] = f[i][2] = f[i][3] = 0;
            f[i][4] = (f[i - 1][4] + f[i - 1][5] + f[i - 1][6] + f[i - 1][7] +
                       f[i - 1][8] + f[i - 1][9]) %
                      mod;
            f[i][5] = f[i][6] = f[i][7] = f[i][8] = f[i][9] = f[i][10] = 0;
            f[i][11] = f[i - 1][11];
        }
        // cout << f[i][1] << endl;
    }
    cout << f[n][11] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

然后考虑这两个转移的dp式子很像矩阵运算，所以可以用矩阵快速幂加快运算，#之间的连续的k个空格就用矩阵快速幂加速dp

然后就过了第二个subtask，\(O(11^3m+11^3m\log n)\)

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 13, inf = 1e17, mod = 998244353;

ll n, m;
vector<ll> a;

struct Matrix // 方阵
{
    ll M[N][N], n;
    Matrix(ll type, ll s) // 若 type 不为 0，构造一个单位矩阵
    {
        memset(M, 0, sizeof(M));
        n = s;
        if (type)
            for (ll i = 1; i <= N - 1; i++)
                M[i][i] = 1;
    }
    Matrix operator*(const Matrix &N) // 矩阵乘法
    {
        Matrix ret(0, n);
        for (ll i = 1; i <= n; i++)
            for (ll k = 1; k <= n; k++)
                for (ll j = 1; j <= n; j++) // j,k 互换可能会更快
                    ret.M[i][j] =
                        (ret.M[i][j] + M[i][k] * N.M[k][j] % mod) % mod;
        return ret;
    }
    Matrix operator^(ll k) // 矩阵快速幂
    {
        Matrix ret(1, n), tmp = *this;
        while (k) {
            if (k % 2)
                ret = ret * tmp;
            tmp = tmp * tmp;
            k /= 2;
        }
        return ret;
    }
} f(0, 12), m1(0, 12), m2(0, 12);

ll mat1[12][12] = {
    {25, 25, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0},    // 0
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 1
    {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 2
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 3 (保持全0)
    {0, 0, 1, 0, 25, 24, 24, 24, 24, 24, 0, 0}, // 4
    {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0},       // 5
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},       // 6
    {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},       // 7
    {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},       // 8
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},       // 9
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 10 (保持全0)
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 26}       // 11
};

ll mat2[12][12] = {
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 1
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 2
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 3
    {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0}, // 4
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 5
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 6
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 7
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 8
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 9
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 10
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}  // 11
};

void solve() {
    cin >> n >> m;
    ll lsta = 0, cura;
    for (ll i = 1; i <= m; i++) {
        cin >> cura;
        a.push_back(cura - lsta - 1);
        lsta = cura;
    }
    cura = n + 1;
    a.push_back(cura - lsta - 1);
    for (ll i = 1; i <= 12; i++) {
        for (ll j = 1; j <= 12; j++) {
            m1.M[i][j] = mat1[j - 1][i - 1];
            m2.M[i][j] = mat2[j - 1][i - 1];
        }
    }
    f.M[1][1] = 1;
    ll len = a.size();
    for (ll i = 0; i <= len - 1; i++) {
        f = f * (m1 ^ a[i]);
        if (i != len - 1) {
            f = f * m2;
        }
        // cout << a[i] << endl;
    }
    cout << f.M[1][12] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

然后我们发现矩阵快速幂里和普通快速幂不一样，矩阵乘法有\(11^3\)复杂度，所以可以预处理矩阵的幂，把矩阵快速幂时间复杂度降下来，变成\(O(11^3m+m\log n)\)

或者我们可以发现，不同的区间长度不会多于根号n，因为长度1+2+3…..是等差数列，所以我记住快速幂得出的答案也可以把这里的时间复杂度降下来。

然后我们发现现在的时间复杂度卡在了1e6的m上，每次#都要算两次113的矩阵操作用来dp，太慢了，所以我们可以从开始维护向量，而不是把矩阵都乘起来再乘向量。所以开始创建一个向量，然后每次遇到#只需要112的向量成矩阵，所以变成了\(O(11^2m+m\log n)\)，就可以过了。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll, ll>
const ll N = 13, inf = 1e17, mod = 998244353;

ll n, m;
vector<ll> a;

struct Matrix // 方阵
{
    ll M[N][N], n;
    Matrix(ll type = 0, ll s = 12) // 若 type 不为 0，构造一个单位矩阵
    {
        memset(M, 0, sizeof(M));
        n = s;
        if (type)
            for (ll i = 1; i <= N - 1; i++)
                M[i][i] = 1;
    }
    Matrix operator*(const Matrix &N) // 矩阵乘法
    {
        Matrix ret(0, n);
        for (ll i = 1; i <= n; i++)
            for (ll k = 1; k <= n; k++)
                for (ll j = 1; j <= n; j++) // j,k 互换可能会更快
                    ret.M[i][j] =
                        (ret.M[i][j] + M[i][k] * N.M[k][j] % mod) % mod;
        return ret;
    }
    Matrix operator^(ll k) // 矩阵快速幂
    {
        Matrix ret(1, n), tmp = *this;
        while (k) {
            if (k % 2)
                ret = ret * tmp;
            tmp = tmp * tmp;
            k /= 2;
        }
        return ret;
    }
} f(0, 12), m1(0, 12), m2(0, 12);

ll mat1[12][12] = {
    {25, 25, 24, 0, 0, 0, 0, 0, 0, 0, 0, 0},    // 0
    {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 1
    {0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 2
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 3 (保持全0)
    {0, 0, 1, 0, 25, 24, 24, 24, 24, 24, 0, 0}, // 4
    {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0},       // 5
    {0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0},       // 6
    {0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},       // 7
    {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0},       // 8
    {0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0},       // 9
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},       // 10 (保持全0)
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 26}       // 11
};

ll mat2[12][12] = {
    {1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 0
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 1
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 2
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 3
    {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0}, // 4
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 5
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 6
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 7
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 8
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 9
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 10
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1}  // 11
};

unordered_map<ll, Matrix> ans;

void solve() {
    cin >> n >> m;
    ll lsta = 0, cura;
    for (ll i = 1; i <= m; i++) {
        cin >> cura;
        a.push_back(cura - lsta - 1);
        lsta = cura;
    }
    cura = n + 1;
    a.push_back(cura - lsta - 1);
    for (ll i = 1; i <= 12; i++) {
        for (ll j = 1; j <= 12; j++) {
            m1.M[i][j] = mat1[j - 1][i - 1];
            m2.M[i][j] = mat2[j - 1][i - 1];
        }
    }
    f.M[1][1] = 1;
    ll len = a.size();
    for (ll i = 0; i <= len - 1; i++) {
        if (!ans.count(a[i])) {
            ans[a[i]] = (m1 ^ a[i]);
        }
        Matrix tmp(0, 12), tans = ans[a[i]];
        for (ll j = 1; j <= 12; j++) {
            for (ll k = 1; k <= 12; k++) {
                tmp.M[1][j] =
                    (tmp.M[1][j] + f.M[1][k] * tans.M[k][j] % mod) % mod;
            }
        }
        f = tmp;
        if (i != len - 1) {
            ll t0, t4, t11;
            t0 = f.M[1][1] + f.M[1][2] + f.M[1][3];
            t4 = f.M[1][5] + f.M[1][6] + f.M[1][7] + f.M[1][8] + f.M[1][9] +
                 f.M[1][10];
            t11 = f.M[1][12];
            for (ll i = 1; i <= 12; i++) {
                f.M[1][i] = 0;
            }
            f.M[1][1] = t0 % mod;
            f.M[1][5] = t4 % mod;
            f.M[1][12] = t11 % mod;
        }
        // cout << a[i] << endl;
    }
    cout << f.M[1][12] << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll T;
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
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
map<PII, PII> p;

void add(PII a, PII b, ll c) {
    if (!p.count(a)) {
        p[a].first = n + 1;
        p[a].second = n + 2;
        n += 2;
    }
    if (!p.count(b)) {
        p[b].first = n + 1;
        p[b].second = n + 2;
        n += 2;
    }
    e[p[a].second].push_back((edge){p[b].first, c, e[p[b].first].size()});
    e[p[b].first].push_back((edge){p[a].second, 0, e[p[a].second].size() - 1});
}

void add(ll a, ll b, ll c) {
    e[a].push_back((edge){b, c, e[b].size()});
    e[b].push_back((edge){a, 0, e[a].size() - 1});
}

void solve() {
    ll ans = 0, r, c, d;
    n = 0;
    s = ++n;
    t = ++n;
    cin >> r >> c >> d;
    string g1[30], g2[30];
    for (ll i = 0; i < r; i++) {
        cin >> g1[i];
    }
    for (ll i = 0; i < r; i++) {
        cin >> g2[i];
    }
    for (ll i1 = 0; i1 < r; i1++) {
        for (ll j1 = 0; j1 < c; j1++) {
            for (ll i2 = -1; i2 <= r; i2++) {
                for (ll j2 = -1; j2 <= c; j2++) {
                    if ((i1 - i2) * (i1 - i2) + (j1 - j2) * (j1 - j2) <=
                        d * d) {
                        add({i1, j1}, {i2, j2}, inf);
                    }
                }
            }
            add(p[{i1, j1}].first, p[{i1, j1}].second, g1[i1][j1] - '0');
            if (g2[i1][j1] == 'L') {
                add(s, p[{i1, j1}].first, 1);
                ans++;
            }
        }
    }
    for (ll i2 = -1; i2 <= r; i2++) {
        for (ll j2 = -1; j2 <= c; j2++) {
            if (i2 == -1 || j2 == -1 || i2 == r || j2 == c) {
                add(p[{i2, j2}].first, t, inf);
            }
        }
    }

    while (bfs()) {
        ans -= dfs(s, inf);
    }
    cout << ans << endl;
}