CSP题解

发表于 更新于 分类于 ， 阅读次数： 作者 Pomelorin ， Cool-breeze

CSP38 T4 月票发行

CSP38 T4 月票发行

题意：长度为 \(n\)（\(10^9\)）的字符串有 \(m\)（\(10^6\)）个固定为 #，其余能填任意小写字母。问至少有一个 ccf 和一个 cspark 子串，且至少有一个 ccf 出现在 cspark 前的字符串数量。

点击查看题解

正则表达式 动态规划 矩阵快速幂 首先这是个计数，要不重不漏，可以想到的思路是考虑以第一个出现的 ccf 和 ccf 后第一个出现的 cspark 作为特征进行计数，这样就需要求出长度为 \(i\) 没出现 ccf 的数量，长度为 \(i\) 没出现 ccf 与 cspark 的数量。但是想不到好的办法使用 \(O(n)\) 算法可以做到不重不漏。

例如考虑前半段至少出现一次 ccf，后半段至少出现一次 cspark，显然会重复。前面不出现 ccf 然后紧接着放 ccf，之后至少出现一次 cspark（如果规定不出现 ccf 会遗漏，如果规定可出现 ccf 又显然重复）。没有好的计数方法。

直接计数不行，可以考虑正则表达式匹配。.* 简化为 *，题目要求就是可匹配 *ccf*cspark* 的字符串数量。设 dp[i][j] 代表考虑到第 \(i\) 位，最大可以匹配到第 \(j\) 位正则表达式的字符串数量（最大即唯一性，保证字符串计数不重不漏）。转移方法是类似 KMP 的失配转移，具体来说：

  • * = *+26-c，*c+26-c，*cc+26-c-f；
  • *c = *+c；
  • *cc = *c+c，*cc+c；
  • *ccf = 0（他也可以匹配 *ccf*，取最大）；
  • *ccf* = *cc+f，*ccf*+26-c，*ccf*c+26-c-s，*ccf*cs+26-c-p，*ccf*csp+26-c-a，*ccf*cspa+26-c-r，*ccf*cspar+26-c-k；
  • *ccf*c = *ccf*+c，*ccf*c+c，*ccf*cs+c，*ccf*csp+c，*ccf*cspa+c，*ccf*cspar+c；
  • *ccf*cs 至 *ccf*cspar：由 *ccf*c 至 *ccf*cspa 转移；
  • *ccf*cspark = 0（他也可以匹配 *ccf*cspark*，取最大）；
  • *ccf*cspark* = *ccf*cspar+k，*ccf*cspark*+26。

如果当前字符是 #，只有末尾为 *，即 *，*ccf*，*ccf*cspark* 可转移，且由“上一阶段”转移。

然后就过了第一个 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 式子只由固定的上一个状态转移而来，可以用矩阵快速幂加快运算。具体而言，# 之间的连续的空格就用第一个矩阵跑矩阵快速幂加速 DP，遇到 # 使用第二个矩阵转移。

然后就过了第二个 subtask，\(O(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;
}

获得满分需要两个观察。

我们可以发现，不同的区间长度不会多于 \(\sqrt n\)，因为长度 \(1+2+3...\) 是等差数列，所以预处理矩阵快速幂的答案可以把这里的时间复杂度降为 \(O(11^3m+11^3\sqrt n\log n)\)。

然后我们发现现在的时间复杂度卡在了 \(m=10^6\) 上，每次遇到 # 都要算两次 \(11^3\) 的矩阵操作。实际上矩阵快速幂题目一般是求向量乘矩阵的某次幂，所以我们直接维护向量，而不是把矩阵都乘起来再乘向量。每次遇到 # 只需要 \(11^2\) 的向量乘矩阵操作，所以变成了\(O(11^2m+11^3\sqrt n\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;
}

CSP37 T4 集体锻炼

CSP37 T4 集体锻炼

题意：给定长度为 \(n=10^6\) 的数列 \(a_i\le10^6\)，定义 \(f(l,r)=l\times r\times \gcd(a_l,a_{l+1},...,a_r)\)。求 \(\sum_{l=1}^n\sum_{r=l}^n f(l,r)\)。

点击查看题解

最大公约数 ST 表 考虑前缀 gcd 的变化，从 1 至 n，它的变化次数不会超过 \(\log n\)。可以使用 ST 表预处理区间 gcd。之后枚举左端点，在左端点固定时，通过二分找到前缀 gcd 变化的位置。例如固定的左端点为 \(L\)，前缀 gcd 为 \(g\) 的区间为 \([u,v]\)，则对答案的贡献为 \(gL(u+v)(v-u+1)/2\)。

注意到如果对于某个左端点 \(L\)，前缀 gcd 变化的位置集合为 \(S(L)\)，则 \(S(L)\subseteq S(L+1)\cup\{L\}\)。因为随着左端点左移，旧的变化位置有可能会减少，但除了左端点本身不可能增加新的变化位置。所以只需要倒着枚举左端点，维护变化的位置集合，不需要每次都二分查询变化位置。这样可以通过此题。

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

ll n, a[N], b[N], st[30][N];
map<ll, ll> dif;

ll ksm(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b % 2) {
            ret = ret * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return ret;
}

ll inv(ll x) { return ksm(x, mod - 2); }
ll inv2 = inv(2);

ll calc(ll l, ll r) { return (r + l) * (r - l + 1) / 2 * l % mod; }

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll query(ll l, ll r) {
    ll len = r - l + 1;
    ll x = st[b[len]][l];
    ll y = st[b[len]][r + 1 - (1 << b[len])];
    return gcd(x, y);
}

void solve() {
    ll ans = 0;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        st[0][i] = a[i] * 2;//给每个数都乘2，这样避免判断变化端点时的特判，答案最终除以2即可
    }
    st[0][n + 1] = 1;
    for (ll i = 1; i <= 20; i++) {
        for (ll j = 1; j <= n + 1; j++) {
            st[i][j] = gcd(st[i - 1][j], st[i - 1][j + (1ll << (i - 1))]);
        }
    }
    for (ll i = 1; i <= 20; i++) {
        b[1ll << i] = 1;
    }
    for (ll i = 1; i <= n + 1; i++) {
        b[i] += b[i - 1];
    }
    for (ll i = n; i >= 1; i--) {
        dif[i] = 1;
        vector<ll> de;
        for (auto [k, v] : dif) {
            if (query(i, k) == query(i, k + 1)) {
                de.push_back(k);
            }
        }
        for (auto j : de) {
            dif.erase(j);
        }
        ll lstk = i - 1;
        for (auto [k, v] : dif) {
            ans =
                (ans + query(i, k) * (calc(i, k) - calc(i, lstk)) % mod) % mod;
            lstk = k;
        }
    }
    cout << ans * inv2 % mod << endl;
}

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