[ABC271 G] Access Counter

난이도: 2323

 

태그

• Probability Theory (확률론)
• Dynamic Programming (동적 계획법)
  • DP Optimization - Matrix Exponentiation (행렬 거듭제곱으로 DP 최적화하기)
• Modular Multiplicative Inverse (모듈러 곱셈에 대한 역원)

 

풀이

1. \( N \)번째 클릭이 발생하는 시각은?

확률에 의존하기 때문에 당연히 "이 때다!"라고 답할 수는 없습니다.

하지만, 이 생각 자체는 도움이 많이 될 예정이니 따로 적었습니다.

 

문제의 답은, \( N \)번째 클릭이 발생하는 시간이 T의 방문 시각인지 / A의 방문 시각인지 로 계산할 수 있습니다.

 

2. \( 1 \)번째 클릭이 \( i \)시에 발생할 확률은?

가장 간단한 케이스인 \( N = 1 \)을 들고 왔습니다.

 

편의상, Takahashi와 Aoki가 클릭을 할 확률을 각각 \( P_{\text{T}}, P_{\text{A}} \)라고 합시다.

• \( 0 \)시간만에 첫 클릭이 발생할 확률은 \( P_{c_0} \)입니다.
• \( 1 \)시간만에 첫 클릭이 발생할 확률은 \( (1 - P_{c_0}) \cdot P_{c_1} \)입니다.
• \( 2 \)시간만에 첫 클릭이 발생할 확률은 \( (1 - P_{c_0})(1 - P_{c_1}) \cdot P_{c_2} \)입니다.
• ...
• \( i \)시간만에 첫 클릭이 발생할 확률은 \( P_{c_i} \cdot \prod\limits_{t=0}^{i-1} (1 - P_{c_t}) \)입니다.
• ...
• \( 24 \)시간동안 클릭이 없을 확률은 \( \prod\limits_{t=0}^{23} (1 - P_{c_t}) \)이며,
  이 뒤로는 위의 \( 0 \)시, \( 1 \)시, ...의 경우에 사이클로 적용됩니다.

 

이론적으로는 굉장히 오랜 시간동안 클릭이 없을 수도 있으므로, 좀 더 자세히 생각해봅시다.

 

\( i \)에 첫 클릭이 발생할 확률은, 아래의 합으로 볼 수 있습니다.

• \( i \)시간만에 첫 클릭 발생: \( P_{c_i} \cdot \prod\limits_{t=0}^{i-1} (1 - P_{c_t}) \)
• \( i + 24 \)시간만에 첫 클릭 발생: \( P_{c_i} \cdot \prod\limits_{t=0}^{i-1} (1 - P_{c_t}) \cdot \prod\limits_{t=0}^{23} (1 - P_{c_t}) \)
• \( i + 48 \)시간만에 첫 클릭 발생: \( P_{c_i} \cdot \prod\limits_{t=0}^{i-1} (1 - P_{c_t}) \cdot \left( \prod\limits_{t=0}^{23} (1 - P_{c_t}) \right)^2 \)
• ...

 

등비수열의 합이 등장한 걸 볼 수 있습니다.

그러므로, \( i \)시에 첫 클릭이 발생할 확률은 초항 \( a = P_{c_i} \cdot \prod\limits_{t=0}^{i-1} (1 - P_{c_t}) \)이고, 공비 \( r = \prod\limits_{t=0}^{23} (1 - P_{c_t}) \)인 등비수열의 합 \( \frac{a}{1-r} \)로 계산할 수 있습니다.

 

3. \( N-1 \)번째 클릭이 \( j \)시에 발생했다면, \( N \)번째 클릭이 \( i \)시에 발생할 확률은?

\( j+1 \)시부터 시작해서 (2번)과 비슷한 과정을 거쳐볼 수 있습니다.

 

실제 과정은 그냥 \( 0 \)시 대신 \( j+1 \)시를, \( 1 \)시 대신 \( j+2 \)시를 넣고 똑같이 해주면 되니 생략하겠습니다.

중요한 점은, 등비수열의 합으로 잘 계산할 수 있다는 점입니다.

 

여담으로, (2번)에서 구한 과정은 사실 \( 0 \)번째 클릭 (존재하진 않지만 편의상 정의)이 \( 23 \)시 (\( -1 \)시)에 발생했을 때로 볼 수 있습니다.

 

4. 이제 문제의 답을 구해보자.

(3번)을 토대로, \( P_{i, j} \) = \( i \)시에 마지막 클릭이 발생했을 때, 그 다음 클릭이 \( j \)시에 발생할 확률 을 계산해봅시다.

 

이제 \( D_{x, t} \) = \( x \)번째 클릭이 \( t \)시에 발생할 확률 을 보면, \( D_{x, t} = \sum_{k=0}^{23} D_{x-1, k} P_{k, t} \)로 식을 적어볼 수 있습니다.

 

무언가 의심되는 선형 점화식이 등장했습니다.

이 선형 점화식은 아래와 같은 행렬 곱셈으로 표현할 수 있습니다.

\[ \begin{bmatrix} D_{x, 0} \\ D_{x, 1} \\ \vdots \\ D_{x, 23} \end{bmatrix} = \begin{bmatrix} P_{0, 0} & P_{1, 0} & \cdots & P_{23, 0} \\ P_{0, 1} & P_{1, 1} & \cdots & P_{23, 1} \\ \vdots & \vdots & \ddots & \vdots \\ P_{0, 23} & P_{1, 23} & \cdots & P_{23, 23} \end{bmatrix} \begin{bmatrix} D_{x-1, 0} \\ D_{x-1, 1} \\ \vdots \\ D_{x-1, 23} \end{bmatrix} \]

 

그런데, \( D_{x-1} \) 역시 동일한 행렬 곱셈으로 표현할 수 있고, 이를 반복하면

\[ \begin{bmatrix} D_{N, 0} \\ D_{N, 1} \\ \vdots \\ D_{N, 23} \end{bmatrix} = \begin{bmatrix} P_{0, 0} & P_{1, 0} & \cdots & P_{23, 0} \\ P_{0, 1} & P_{1, 1} & \cdots & P_{23, 1} \\ \vdots & \vdots & \ddots & \vdots \\ P_{0, 23} & P_{1, 23} & \cdots & P_{23, 23} \end{bmatrix}^N \begin{bmatrix} D_{0, 0} \\ D_{0, 1} \\ \vdots \\ D_{0, 23} \end{bmatrix} \]

라는 결과를 얻게 됩니다.

 

(3번)의 마지막 줄에 따르면, \( D_{0, t} \)는 아래와 같이 볼 수 있습니다.

\[ D_{0, t} = \begin{cases} 0 & \text{if } t \neq 23 \\ 1 & \text{if } t = 23 \end{cases} \]

 

이제 \( D_{N, t} \)를 구할 준비는 끝났으니, 위 식을 써서 구해주면 됩니다.

 

코드

문제의 답은, \( c_t = \text{T} \)인 \( t \)에 대해 \( \sum D_{N, t} \)로 구할 수 있습니다.

const ll mod = 998244353;
ll fpow(ll mul, ll bit){ ll res = 1;
    while (bit){
        if (bit&1){ res = res*mul % mod; }
        mul = mul*mul % mod; bit >>= 1;
    }
    return res;
}
inline ll finv(ll x){ return fpow(x, mod-2); }
 
const int N = 24;
ll res[24][24], mul[24][24], tmp[24][24];
void matmul(ll (*a)[24], ll (*b)[24]){
    memset(tmp, 0, sizeof(tmp));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            for (int k = 0; k < N; k++){
                tmp[i][j] += a[i][k] * b[k][j] % mod;
                tmp[i][j] %= mod;
            }
        }
    }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){ a[i][j] = tmp[i][j]; }
    }
}
void matpow(ll bit){
    for (int i = 0; i < N; i++){ res[i][i] = 1; }
    while (bit){
        if (bit&1){ matmul(res, mul); }
        matmul(mul, mul); bit >>= 1;
    }
}
 
void Main(){
    ll n; int a, b; cin >> n >> a >> b;
    ll x = a*finv(100) % mod, y = b*finv(100) % mod;
    string s; cin >> s;
    for (int i = 0; i < N; i++){
        ll p = 1;
        for (int d = 1; d <= N; d++){
            int j = (i+d) % N;
            if (s[j] == 'T'){ mul[i][j] = p*x % mod; p = p*(1-x +mod) % mod; }
            if (s[j] == 'A'){ mul[i][j] = p*y % mod; p = p*(1-y +mod) % mod; }
        }
        for (int j = 0; j < N; j++){ mul[i][j] *= finv(1-p+mod); mul[i][j] %= mod; }
    }
    matpow(n);
    ll ans = 0;
    for (int j = 0; j < N; j++){
        if (s[j] == 'A'){ ans += res[23][j]; }
    }
    cout << ans % mod;
}