[C++] 31435번 기숙사 비밀번호 구하기

https://www.acmicpc.net/problem/31435

---

 

25/10/28

 

 

연립방정식을 풀기 위해 열심히 식 정리를 해보자....

---

 

문제 접근 방식:

 

 

핵심 아이디어는 두 인접한 쿼리의 결과의 차를 이용하여 하나의 항을 "빠르게" 구하는 것이다.

가장 쉽게 생각할 수 있는 방법은 모든 $x_{i}$의 합 $S$가 주어져 있고,

 

$$S = x_{1}+x_{2}+\cdots+x_{n}$$

 

여기서 하나의 항을 뺀 $S-x_{i}$가 주어져 있을 때, 두 식을 뺀다면 $x_{i}$를 구할 수 있을 것이다.

하지만 여기서 첫번째 문제는 쿼리를 날릴 때 모든 $a_{i}$가 달라야 하므로, $? \ 1 \ 1 \ \cdots \ 1$과 같은 형식으로 쿼리를 날려서 $S$를 직접 물어볼 수 없다는 것이다.

따라서, 어떻게든 하나의 항을 뺀 $S-x_{i}$들의 형태와 $S$만 잘 구한다면 쉽게 해결할 수 있을 것이다.


$n = 4$로 예시를 들어보겠다.

나의 경우는 $S$를 먼저 구성하려는 시도를 하지 않았고, $S-x_{i}$를 먼저 구성했고, 그로부터 $S$를를 만들자고 생각 했다.

즉, 아래와 같이 쿼리 구성을 진행했다.

 

$$\begin{bmatrix}1 & 2 & 3 & 4 \\5 & 7 & 8 & 9  \\10 & 11 & 13 & 14 \\15 & 16 & 17 & 19\end{bmatrix}$$

 

$i+1$번째 쿼리의 결과 $y_{i+1}$에서 $i$번째 쿼리의 결과 $y_{i}$를 빼면

 

$$\Delta_{i} = y_{i+1} - y_{i} = (n+1)S-x_{i}$$

 

와 같은 식을 얻을 수 있다.

즉, 이 경우 $5S - x_{1}, 5S-x_{2}, 5S-x_{3}$까지는 구할 수 있다. 당연히 식이 $3$개이기 때문에 하나가 더 필요하다.

이제 $S$만 찾으면 $x_{1}, x_{2}, x_{3}$를 빠르게 구할 수 있다. 당연히 남은 $x_{4}$또한 $x_{1}, x_{2}, x_{3}, S$를 구했기 때문에 $x_{4}$도 쉽게 구할 수 있다.

결국 활용할 수 있는건 $\Delta_{i}$였기 때문에, $S$를 찾기 위해 $\Delta_{i}$들을 먼저 모두 더해주었다.
$$\begin{align} P &= \sum_{i=1}^{n-1}\Delta_{i} \\&= \sum_{i=1}^{n-1}(n+1)S-\sum_{i=1}^{n-1} x_{i}\\&= (n-1)(n+1)S - \sum_{i=1}^{n-1} x_{i} \\ &= (n-1)(n+1)S-S+x_{n} \\ &=(n^{2}-2)S + x_{n} \end{align}$$

 

$S$와 $x_{n}$에 관한 식이 하나 나왔다.

첫번째 쿼리의 결과 또한 활용하고 싶었다. 첫번째 쿼리의 결과 $y_{1} = x_{1}+2x_{2}+3x_{3}+\dots+nx_{n}$이므로, $\Delta_{i} = (n+1)S-x_{i}$에 $i$를 곱해서 더하면 첫번째 쿼리와 비슷하게 가져갈 수 있다고 생각했다.

 

$$\begin{align}Q &= \sum_{i=1}^{n-1} i\Delta_{i}\\ &= \sum_{i=1}^{n-1}i(n+1)S- \sum_{i=1}^{n-1} ix_{i}\\&= \left( \frac{n(n-1)}{2} \right)(n+1)S-y_{1}+nx_{n} \\ &= \frac{n(n^{2}-1)}{2}S - y_{1} + nx_{n}\end{align}$$

$y_{1}$은 이미 알고 있으므로, $P, Q$를 연립하면 $x_{n}$과 $S$를 구할 수 있을 것 같다. 정리해보면 다음과 같다.

 

$$\begin{align} Q-nP + y_{1} &= \frac{n(n^{2}-1)}{2}S-y_{1}+nx_{n} - n(n^{2}-2)S -nx_{n} + y_{1} \\ &=\frac{n(n^{2}-1-2n^{2}+4)}{2}S \\ &= -\frac{n(n^{2}-3)}{2}S \\ \rightarrow nP - Q - y_{1} &= \frac{n(n^{2}-3)}{2}S \\ \rightarrow S &= \frac{2(nP-Q-y_{1})}{n(n^{2}-3)}\end{align}$$

$S$를 구했다면 $x_{i}$를 구하는건 껌이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 31435번 기숙사 비밀번호 구하기
// 차분 공격, 모듈로 역원
/*
접근 방법:
? 0     1     2     ... N-1
? N     N+2   N+3   ... 2*N
? 2*N+1 2*N+2 2*N+4 ... 3*N+1

*/
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MOD 998'244'353
typedef long long ll;

ll fastpow(ll a, ll exp){
    if (exp == 0) return 1;
    if (exp == 1) return a;
    ll k = fastpow(a, exp/2);
    if (exp % 2 == 0){
        return (k*k)%MOD;
    } else {
        return (((k*k)%MOD)*a)%MOD;
    }
}

ll inverse(ll N){
    return fastpow(N % MOD, MOD-2);
}

ll mod(ll N){
    while (N < 0){
        N += MOD;
    }
    return N % MOD;
}

int main(void){
    fastio

    int N; cin >> N;
    vector<ll> Y(N);
    ll a = 0;
    for (int i = 0; i < N; ++i){
        cout << '?';
        for (int j = 0; j < N; ++j){
            if (j == i) a++;
            cout << ' ' << a;
            a++;
        }
        cout << endl;
        cin >> Y[i];
    }
    vector<ll> D(N-1);
    for (int i = 0; i < N-1; ++i){
        D[i] = mod(Y[i+1]-Y[i]);
    }
    ll P = 0, Q = 0;
    for (int i = 0; i < N-1; ++i){
        P += D[i];
        P = mod(P);
        Q += ((i+1)*D[i])%MOD;
        Q = mod(Q);
    }
    ll S = mod(mod(mod(2*mod(mod(mod(N*P)-Q)-Y[0]))*inverse(N))*inverse(N*N-3));
    vector<ll> ans(N);
    ll sum = 0;
    for (int i = 0; i < N-1; ++i){
        ans[i] = mod((N+1)*S - D[i]);
        sum = mod(sum + ans[i]);
    }
    ans[N-1] = mod(S - sum);
    cout << '!';
    for (int i = 0; i < N; ++i){
        cout << ' ' << ans[i];
    }
    cout << endl;
    return 0;
}