[ABC271G] Access Counter Solution

更好的阅读体验戳此进入

题面

每天存在 $24$$24$ 个时间点，两人要访问一个网站，给定一个 A 和 T 组成的长度为 $24$$24$ 的字符串，若为 T 则 Taka 有 $X\mathrm{\%}$$X\%$ 的概率成功访问，若为 A 则 Aoki 有 $Y\mathrm{\%}$$Y\%$ 的概率成功访问，求该网站第 $n$$n$ 次被访问时是被 Aoki 访问的概率，对 $998244353$$998244353$ 取模。

Solution

首先看一眼这个题面与 $n$$n$ 的范围，就不难联想到矩阵快速幂，但是这题的难点我认为主要还是在状态的设计与转移上。

一个显而易见但较为重要的性质，即两次访问之间间隔的天数是易于统计的，重要的在于两次访问的时间点 $i,j$$i, j$ 之间的位置关系。

令对应时间点的访问成功概率为 $p_i$$p_i$，令一天中未发生任何访问的概率为 $P=\prod _{i=1}^{24}(1-p_i)$$P = \prod_{i = 1}^{24}(1 - p_i)$，考虑预处理 $dp(i,j)$$dp(i, j)$ 表示上次在 $i$$i$ 访问本次在 $j$$j$ 访问的概率，如果两者之间的距离不超过一天，显然可以预处理，令 $R$$R$ 为从 $i+1$$i + 1$ 到 $j-1$$j - 1$ 的所有 $1-p$$1 - p$ 之积，则转移显然，即：

显然和式为等比数列求和，且由题意可知公比 $P<0$$P \lt 0$，则继续推式子可以得到：

显然 $n\to +\mathrm{\infty }$$n \to +\infty$ 时 $P^n\to 0$$P^n \to 0$，则转化为：

于是我们完成了 $dp(i,j)$$dp(i, j)$ 的预处理。

令 $f(i,j)$$f(i, j)$ 表示第 $i$$i$ 次访问发生在 $j$$j$ 时刻的概率，有：

按照我们之前的想法挂到矩阵上：

显然 $f(0,i)=[i=24]$$f(0, i) = [i = 24]$，初始时我们默认其最终选择的只能是 $24$$24$，等价于从 $0$$0$ 开始，这样不会对我们的结果造成影响，那么最终形式：

答案统计一下所有 $i$$i$ 处是 Aoki 的 $f(n,i)$$f(n, i)$ 之和即可，可以矩阵快速幂优化，令 $d=24$$d = 24$，则复杂度 $O(d^3\log n)$$O(d^3 \log n)$，可以通过。

Code

xxxxxxxxxx
144
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (998244353ll)
24

25
template < typename T = int >
26
inline T read(void);
27

28
ll N;
29
ll Taka, Aoki;
30
ll p[30];
31
ll P(1);
32
ll ansv(0);
33
ll inv100;
34
ll dp[30][30];
35
bitset < 30 > belong;
36

37
ll qpow(ll a, ll b){
38
    ll ret(1), mul(a);
39
    while(b){
40
        if(b & 1)ret = ret * mul % MOD;
41
        b >>= 1;
42
        mul = mul * mul % MOD;
43
    }return ret;
44
}
45

46
class Matrix{
47
private:
48
    int siz;
49
    ll v[30][30];
50
public:
51
    Matrix(int len = 24, int pat = 0){
52
        siz = len;
53
        for(int i = 0; i < siz; ++i)
54
            for(int j = 0; j < siz; ++j)
55
                v[i][j] = 0;
56
        switch(pat){
57
            case 1:{
58
                for(int i = 0; i < siz; ++i)v[i][i] = 1;
59
                break;
60
            }
61
            case 2:{
62
                v[0][siz - 1] = 1;
63
                break;
64
            }
65
            case 3:{
66
                for(int i = 1; i <= siz; ++i)
67
                    for(int j = 1; j <= siz; ++j)
68
                        v[i - 1][j - 1] = dp[i][j];
69
                break;
70
            }
71
            default: break;
72
        }
73
    }
74
    friend Matrix operator * (const Matrix &a, const Matrix &b){
75
        Matrix ret(24);
76
        for(int i = 0; i < 24; ++i)
77
            for(int j = 0; j < 24; ++j)
78
                for(int k = 0; k < 24; ++k)
79
                    (ret.v[i][j] += a.v[i][k] * b.v[k][j] % MOD) %= MOD;
80
        return ret;
81
    }
82
    void SetAns(void){
83
        for(int i = 0; i < 24; ++i)
84
            if(belong[i + 1])(ansv += v[0][i]) %= MOD;
85
    }
86
    void Print(void){
87
        printf("##########\n");
88
        for(int i = 0; i < siz; ++i)
89
            for(int j = 0; j < siz; ++j)
90
                printf("%lld%c", v[i][j], j == siz - 1 ? '\n' : ' ');
91
        printf("##########\n");
92
    }
93
}ans(24, 2);
94

95
Matrix qpow(Matrix a, ll b){
96
    Matrix ret(24, 1), mul(a);
97
    while(b){
98
        if(b & 1)ret = ret * mul;
99
        b >>= 1;
100
        mul = mul * mul;
101
    }return ret;
102
}
103

104
int main(){
105
    inv100 = qpow(100, MOD - 2);
106
    N = read < ll >(), Taka = read(), Aoki = read();
107
    for(int i = 1; i <= 24; ++i){
108
        char c = getchar(); while(!isalpha(c))c = getchar();
109
        p[i] = c == 'T' ? Taka : Aoki, belong[i] = c == 'T' ? false : true;
110
        (P *= (100 - p[i]) * inv100 % MOD) %= MOD;
111
    }
112
    for(int i = 1; i <= 24; ++i){
113
        for(int j = 1; j <= 24; ++j){
114
            ll R(1);
115
            if(i < j)for(int k = i + 1; k <= j - 1; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
116
            else{
117
                for(int k = i + 1; k <= 24; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
118
                for(int k = 1; k <= j - 1; ++k)(R *= (100 - p[k]) * inv100 % MOD) %= MOD;
119
            }
120
            dp[i][j] = R * (p[j] * inv100 % MOD) % MOD * qpow((1 - P + MOD) % MOD, MOD - 2) % MOD;
121
        }
122
    }
123
    Matrix base(24, 3);
124
    (ans * qpow(base, N)).SetAns();
125
    printf("%lld\n", ansv);
126
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
127
    return 0;
128
}
129

130
template < typename T >
131
inline T read(void){
132
    T ret(0);
133
    int flag(1);
134
    char c = getchar();
135
    while(c != '-' && !isdigit(c))c = getchar();
136
    if(c == '-')flag = -1, c = getchar();
137
    while(isdigit(c)){
138
        ret *= 10;
139
        ret += int(c - '0');
140
        c = getchar();
141
    }
142
    ret *= flag;
143
    return ret;
144
}

UPD

update-2023_02_09 初稿