문제 설명

\(m\) 개의 \([0,2^n)\) 범위 내에서 균일하게 무작위로 선택된 정수 변수가 있을 때, 최소 두 개의 변수 값이 동일할 확률을 구하는 문제입니다.

정확한 계산을 위해 결과를 \(a/b\) 형태로 표현하며, 여기서 \((a,b)=1\). 이때, \(a\)와 \(b\)는 \(10^6+3\)에 대해 모듈러 연산 후 출력해야 합니다.

데이터의 70%에 대해, \(m \le 10^6\) 모든 데이터에 대해, \(1 \le 10^{18}\), \(2 \le m \le 10^{18}\)

【예시 1 입력】

3 2

【예시 1 출력】

1 8

【예시 2 입력】

1 3

【예시 2 출력】

1 1

【예시 3 입력】

4 3

【예시 3 출력】

23 128

해결 전략

먼저, 모든 값이 다른 경우의 확률을 계산한 후 이를 이용하여 적어도 두 값이 같은 경우의 확률을 구합니다. 즉,

[1 - \frac{2^n \times (2^n -1)\times ... \times (2^n -m +1)}{2^{nm}} ]

이 식을 간단히 하기 위해, 먼저 \(m \ge mod\)일 때 분자에 \(mod\)로 나누었을 때 0이 되는 항이 반드시 존재함을 알 수 있습니다. 그러나 답을 바로 1로 출력할 수 없으므로, 분자와 분모의 약분 방법을 고려해야 합니다.

분자의 각 항은 모두 2의 거듭제곱에서 어떤 수를 뺀 값으로 구성되며, 이들 사이의 관계를 이용하여 2의 지수를 계산할 수 있습니다. 예를 들어, \(8 - 2 = (1000)_2 - (0010)_2 = (0110)_2\).

이 관찰을 바탕으로, \(2^n \times (2^n -1)\times ... \times (2^n -m +1)\)에서 2의 지수 개수를 구하는 것은 사실상 \((m-1)!\)에서 2의 지수 개수를 구하는 것과 같습니다.

이를 효율적으로 계산하기 위한 방법으로는 Legendre's Theorem을 사용할 수 있습니다:

[\text{CountOf2}(n!) = \left\lfloor \frac{n}{2} \right\rfloor + \left\lfloor \frac{n}{4} \right\rfloor + \left\lfloor \frac{n}{8} \right\rfloor + \cdots ]

이제 분자를 어떻게 계산할지 생각해봅시다. \(O(m)\) 시간 복잡도로 직접 계산하지 않고, \(m \le mod\)인 경우만 처리하면 됩니다.

분모를 약분하려면 지수에서 빼주면 되고, 분자는 Fermat's Little Theorem을 통해 나눗셈을 곱셈으로 변환할 수 있습니다:

[a^{-1} \equiv a^{p-2} \pmod{p} ]

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e6 + 3;

ll powerMod(ll base, ll exp, ll mod) {
    ll result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

ll countTwoFactors(ll x) {
    return x ? x / 2 + countTwoFactors(x / 2) : 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m;
    cin >> n >> m;
    
    ll twoFactors = countTwoFactors(m - 1) + n;
    ll invDenom = powerMod(powerMod(2, twoFactors, MOD), MOD - 2, MOD);
    ll denom = powerMod(powerMod(2, n, MOD), m, MOD) * invDenom % MOD;

    if (m >= MOD) {
        cout << denom << " " << denom;
        return 0;
    }

    ll current = (powerMod(2, n, MOD) - (m % MOD) + 1 + MOD) % MOD;
    for (ll i = 1; i < m; ++i) {
        current = (current * (powerMod(2, n, MOD) - i + 1)) % MOD;
    }

    current = (current * invDenom) % MOD;
    cout << (denom - current + MOD) % MOD << " " << denom;

    return 0;
}