[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 _{t=0}^{i-1}(1-P_{c_t})$입니다.
• ...
• $24$시간동안 클릭이 없을 확률은 $\prod _{t=0}^{23}(1-P_{c_t})$이며,
  이 뒤로는 위의 $0$시, $1$시, ...의 경우에 사이클로 적용됩니다.

 

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

 

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

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

 

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

그러므로, $i$시에 첫 클릭이 발생할 확률은 초항 $a=P_{c_i}\cdot \prod _{t=0}^{i-1}(1-P_{c_t})$이고, 공비 $r=\prod _{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}$로 식을 적어볼 수 있습니다.

 

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

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

$$\left[\begin{array}{c}{D}_{x,0}\\ D_{x,1}\\ ⋮\\ D_{x,23}\end{array}\right]=\left[\begin{array}{cccc}{P}_{0,0}& P_{1,0}& \cdots & P_{23,0}\\ P_{0,1}& P_{1,1}& \cdots & P_{23,1}\\ ⋮& ⋮& \ddots & ⋮\\ P_{0,23}& P_{1,23}& \cdots & P_{23,23}\end{array}\right]\left[\begin{array}{c}{D}_{x-1,0}\\ D_{x-1,1}\\ ⋮\\ D_{x-1,23}\end{array}\right]$$

 

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

$$\left[\begin{array}{c}{D}_{N,0}\\ D_{N,1}\\ ⋮\\ D_{N,23}\end{array}\right]={\left[\begin{array}{cccc}{P}_{0,0}& P_{1,0}& \cdots & P_{23,0}\\ P_{0,1}& P_{1,1}& \cdots & P_{23,1}\\ ⋮& ⋮& \ddots & ⋮\\ P_{0,23}& P_{1,23}& \cdots & P_{23,23}\end{array}\right]}^N\left[\begin{array}{c}{D}_{0,0}\\ D_{0,1}\\ ⋮\\ D_{0,23}\end{array}\right]$$

라는 결과를 얻게 됩니다.

 

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

$$D_{0,t}=\{\begin{array}{ll}0& \text{if }t\ne 23\\ 1& \text{if }t=23\end{array}$$

 

이제 $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;
}