[ABC 271] G. Access Counter ★

문제 링크

으... 어려워...

여태 풀었던 앳코더 문제들 중에 레이팅이 kenkooo 기준으로 제일 높다. (거의 꽉 찬 옐로우)

내가 보기에는 다이아도 줄 만한 것 같다. 발상이 너무 어렵다...

 

짜증나는 점이 하나 있는데, ABC 공식 풀이가 뭐가 많이 부족하다는 것이다. 잘못된 점도 많고 설명도 친절하지 않다.

1. 문제 요약

웹 페이지에 웹 카운터는 접속 횟수를 측정한다.

$i=0,1,2,\ldots,23$에 대해서, 매일 $i$시마다 다음의 접속 가능성이 존재한다.

• 만약 $c_i=$'T'라면 철수는 $X$%의 확률로 웹 페이지에 접속한다.
• 만약 $c_i=$'A'라면 영희는 $Y$%의 확률로 웹 페이지에 접속한다.

$N$번째 접속이 영희에 의한 것일 확률을 $\mathrm{mod }\ 998244353$으로 취하여 출력하라.

제한

• $1\le N\le 10^{18}$
• $1\le X, Y\le 99$
• $c_i\in \{$'T'$,$'A'$\}$
• $N, X, Y$는 모두 정수이다.

 

*편의상 'T', 'A'에 대한 조건부를 달면 귀찮으니 $p_i=\begin{cases} X &c_i=\text{'T'}\\ Y &c_i=\text{'A'} \end{cases}$라고 하자.

2. 아마도 이런 사고 과정을 거쳐야 하지 않았을까 싶은 것

• $N$이 너무 큰데, 상수 시간은 솔직히 말이 안되니까 로그 시간 정도에 풀리겠지
  • 분할 정복을 여기서 떠올렸을 수도 있긴 하겠다
• 하루 동안 접속 안 할 확률($=\prod_{i=0}^{23}(1-p_i)$)을 갖다가 $24$주기로 두고두고 써먹을 생각을 할 거다
• 근데 이제.. 이 하루 접속 안 할 확률을 무한 등비 급수의 합 형태로 사용해야 되니까 공식 $\sum_{k=0}^\infty \square^k=\frac 1 \square$을 사용해야 한다
• 더 이상은 이 풀이에 어떻게 해야 접근해야 할지 모르겠다...
  • 행렬곱 DP를 많이 풀다 보면 알게 되려나?
• 난 '$n$일간 $k$번 접속할 확률' 이런 기준으로 바라봤는데, 결국 아니었다
  
  • 한정된 기간 동안 얼마나 접속하냐 따위를 고려하면 안 되는 거였다
  • 왜냐하면 기간 자체가 무한이니까...
• 그럼 기간으로 잡기보다는 주기적으로 나오는 시간대를 기준으로 뭔가를 해줘야 한다는 방향을 잡아야 할 것 같다
• 그러면 고려해야 할 인자는 '접속 횟수', '접속 시간대' 정도가 다 일테니까 여기 안에서 놀면 되겠다...
  • 물론 난 못했지만...
• $q:=\prod_{i=0}^{23}(1-p_i)$ (즉, 하루 동안 접속 안 할 확률)
• $0$시에 $1$번째 접속을 할 확률..?
  • $\sum_{k=1}^\infty q^k\times p_0$
• $0$시에 $1$번째 접속을 하고 이후 어떤 시각이든 $2$번째 접속을 할 확률..?
  • $(\sum_{k=1}^\infty q^k\times p_0) \times (\sum_{k=0}^\infty q^k\times p_1+(1-p_1)\sum_{k=0}^\infty q^k\times p_2+(1-p_1)(1-p_2)\sum_{k=0}^\infty q^k\times p_3+\cdots+\frac {q}{1-p_0}\sum_{k=0}^\infty q^k\times p_0)$
• 여기서 주목해야 될 점은 이거다
  • $1-p_i$의 $24$개 미만의 곱을 이용해서 어떤 시각 $x$에서 다른 시각 $y$으로 가는 최소 단위에 맞는 확률을 찾고서 $q$를 점차 곱해가면 일반적인 $y+24k$들로 가는 확률을 구할 수 있다는 것이다
  • 다시 말하면 시각 두 개를 고정하면 그에 맞는 확률을 구해낼 수 있다
• 그런 관점에서 어거지로 점화식을 도출하다 보면 정답에 맞는 점화식이 나올 것 같다...
  • 아닐 수도 있다... 난 못 풀었으니깐

3. 문제 풀이

$\mathrm{dp}(i,j,k):=k+1$시에 시작해서 $j$시에 $i$번째 접속을 할 확률

$0$이랑 $i$가 아닌 $x$에 대해 $\displaystyle \mathrm{dp}(i,j,k)=\sum_{l=0}^{23} \mathrm{dp}(x,j,\ell)\times \mathrm{dp}(i-x,\ell,k)$이니까,

이는 $M^i[j,k]=\mathrm{dp}(i,j,k)$ 식으로 하면 행렬 곱이 잘 만족되므로 행렬 형태로 나타낼 수 있다.

그렇게 하면, $\displaystyle M^i[j,k]=\sum_{l=0}^{23}M^{\lfloor i/2\rfloor}[j,\ell]\times M^{\lfloor i/2\rfloor + i \mathrm{\ mod\ 2}}[\ell,k]$가 만족하므로 분할 정복을 이용한 빠른 거듭제곱으로 $24^3\times \log_2N$만에 해결할 수 있다.

4. 코드

으으으으으으...

우선 modnum 템플릿 투척!

      

      

      

    
    

      <cpp />
    
#pragma region modnum template from ecnerwala/cp-book
// https://github.com/ecnerwala/cp-book/blob/master/src/modnum.hpp
template <typename T> T mod_inv_in_range(T a, T m) {
    // assert(0 <= a && a < m);
    T x = a, y = m;
    T vx = 1, vy = 0;
    while (x) {
        T k = y / x;
        y %= x;
        vy -= k * vx;
        std::swap(x, y);
        std::swap(vx, vy);
    }
    assert(y == 1);
    return vy < 0 ? m + vy : vy;
}
template <typename T> T mod_inv(T a, T m) {
    a %= m;
    a = a < 0 ? a + m : a;
    return mod_inv_in_range(a, m);
}
template <int MOD_> struct modnum {
    static constexpr int MOD = MOD_;
    static_assert(MOD_ > 0, "MOD must be positive");

private:
    int v;

public:

    modnum() : v(0) {}
    modnum(int64_t v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
    friend std::istream& operator >> (std::istream& in, modnum& n) { int64_t v_; in >> v_; n = modnum(v_); return in; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum inv() const {
        modnum res;
        res.v = mod_inv_in_range(v, MOD);
        return res;
    }
    friend modnum inv(const modnum& m) { return m.inv(); }
    modnum neg() const {
        modnum res;
        res.v = v ? MOD-v : 0;
        return res;
    }
    friend modnum neg(const modnum& m) { return m.neg(); }

    modnum operator- () const {
        return neg();
    }
    modnum operator+ () const {
        return modnum(*this);
    }

    modnum& operator ++ () {
        v ++;
        if (v == MOD) v = 0;
        return *this;
    }
    modnum& operator -- () {
        if (v == 0) v = MOD;
        v --;
        return *this;
    }
    modnum& operator += (const modnum& o) {
        v -= MOD-o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator -= (const modnum& o) {
        v -= o.v;
        v = (v < 0) ? v + MOD : v;
        return *this;
    }
    modnum& operator *= (const modnum& o) {
        v = int(int64_t(v) * int64_t(o.v) % MOD);
        return *this;
    }
    modnum& operator /= (const modnum& o) {
        return *this *= o.inv();
    }

    friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
    friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
#pragma endregion modnum template

이 템플릿을 활용해서 작성했습니다:

제일 헷갈리는 부분은 기저 조건 부분인데, 잘 생각해보면 $M^n[i,23]$이 기저 사례라는 것을 알 수 있습니다.

~$23$시까지 접속 안 하고 $0$시부터 접속 or not 하는 거니깐요.

      

      

      

    
    

      <cpp />
    
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define dbg(x) cerr << #x << ": " << x << '\n'
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

#pragma region modnum template from ecnerwala/cp-book
...

using mint = modnum<998244353>;
using matrix = array<array<mint,25>,25>;
matrix operator* (const matrix &a, const matrix &b) {
    matrix c;
    rep(i,0,24) rep(j,0,24) rep(k,0,24)
        c[i][j] += a[i][k]*b[k][j];
    return c;
}

matrix id() {
    matrix e;
    rep(i,0,24) e[i][i] = 1;
    return e;
}

template <class T>
T pw(T x, ll e) {
    T r = id();
    while (e > 0) {
        if (e%2) r = r*x;
        e /= 2, x = x*x;
    }
    return r;
}

ll n;
string c;
mint x, y, p[25], q[25], ans;
matrix M;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> x >> y >> c;
    rep(i,0,23) {
        if (c[i] == 'T') p[i] = x/100;
        else p[i] = y/100;
        if (i) q[i] = q[i-1]*(1-p[i]);
        else q[0] = 1-p[0];
    }
    rep(j,0,23) rep(i,0,23) { // M[i,j] := j clock -> i clock
        M[i][j] = 1/(1-q[23]);
        if (i < j)      M[i][j] *= p[i]/(1-p[i]) * q[i] * q[23] / q[j];
        else if (i > j) M[i][j] *= p[i]/(1-p[i]) * q[i] / q[j];
        else            M[i][j] *= p[i]/(1-p[i]) * q[23];
    }
    auto dp_n = pw(M,n);
    rep(i,0,23) if (c[i] == 'A') ans += dp_n[i][23];
    cout << ans;
}