Cool Pomelo

Per aspera ad astra. 循此苦旅，以达天际。

发表于 更新于 作者 Pomelorin ， Cool-breeze

欢迎来到 Pomelorin 和 Cool-breeze 的博客！希望我们能相互交流，共同进步～

图标是清爽葡萄柚汽水（确信）。

阅读全文 »

发表于 分类于 ， 作者 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;
}
阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

U672488 寻找丢失柚子

题目背景

Pomelorin 喜欢吃 Pomelo（即柚子），所以他储存了许多柚子，并且给每个柚子编了号。某一天，他发现有两个柚子跑走了，非常着急。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

U227762 试卷排序

题目背景

期末考试临近了，yz 和 zzw 收到了来自老师的试卷关爱，但是试卷太多了，足足有 \(10^{6}\) 张，他们已经无法排好试卷了。

所以在 zzy 的建议下，他们把这个问题交给了你。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

P2472 蜥蜴 - 洛谷

最大流 考虑将问题转化为最多有几只蜥蜴能逃离。

把柱子的点拆成入点出点两部分，它们间的连边的容量就是柱子的高度（能跳出的次数）。

柱子的出点与所有距离 d 以内的柱子的入点和场外点连容量正无穷的边。

源点和有蜥蜴的柱子的入点连容量为 1 的边，场外点和汇点连容量正无穷的边。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

树上启发式合并、Kruskal 重构树、神秘康托展开、欧拉路（更新）、Dinic（更新）、cout 输出流控制。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

简介

线段树，是用来存放给定区间内对应信息的一种数据结构，是一种二叉搜索树。可用来处理数组相应的单点、区间修改操作，也可以进行区间最值、区间和等的查询。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin ， OIWiki

二叉堆

介绍

二叉堆主要支持的操作有：插入一个数 \(O(\log n)\)、查询最小值 \(O(1)\)、删除最小值 \(O(\log n)\)。

二叉堆是一棵完全二叉树，其每个节点都有一个值，且每个节点的值都大于等于/小于等于其父亲的值。每个节点的值都大于等于其父亲值的堆叫做小根堆（即根最小），否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

阅读全文 »

发表于 更新于 分类于 ， 作者 Pomelorin

模板——图论

Floyd 算法，SPFA 算法（慎用），Dijkstra 算法，强连通分量，Prim 算法，Kruskal 算法，Dinic 最大流（有更新），欧拉路（有更新）。

阅读全文 »
0%