A번: 빨간 점 제거 후 남은 영역 계산

격자판에서 특정 위치 (r, c)의 빨간 점을 제거했을 때, 나머지 칸들을 세 가지 구역으로 나누어 계산한다. 오른쪽에 있는 열들은 각 행마다 m - c칸만큼 이동하며 영향을 받고, 아래쪽 행 전체는 m * (n - r)만큼 더해진다. 마지막으로 대각선 아래 왼쪽 부분은 (m - 1) * (n - r)로 계산할 수 있다. 최종 답은 이 세 값을 합한 것이다.

#include <iostream>
using namespace std;
typedef long long ll;

void solve() {
    ll n, m, r, c;
    cin >> n >> m >> r >> c;
    cout << (m - c) + m * (n - r) + (m - 1) * (n - r) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

B번: 주기적인 숫자 패턴 생성

입력된 길이 n에 따라 특정 규칙에 맞는 숫자 문자열을 출력해야 한다. 소수 조건이나 짝수/홀수 여부에 따라 다르게 동작한다:

• n = 1 또는 3: 불가능하므로 -1 출력
• n = 2: "66" 출력
• n이 홀수이고 5 이상: 앞에 "33"을 반복 추가하고 끝에 "36366" 붙임
• n이 짝수이고 4 이상: 앞에 "33"을 반복 추가하고 끝에 "3366" 붙임

#include <iostream>
#include <string>
using namespace std;

void solve() {
    int n; cin >> n;
    if (n == 1 || n == 3) {
        cout << -1 << '\n';
        return;
    }
    if (n == 2) {
        cout << "66\n";
        return;
    }

    string res = "";
    int repeat = (n % 2 == 1) ? (n - 5) / 2 : (n - 4) / 2;
    for (int i = 0; i < repeat; ++i) res += "33";

    res += (n % 2 == 1) ? "36366" : "3366";
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

C번: 비트 연산 기반 배열 구성

비트 OR과 AND를 번갈아 수행하는 과정에서 최대 결과를 만들기 위한 순열을 구성해야 한다. 마지막 연산이 무엇인지에 따라 전략이 달라진다.

• 홀수 길이: 마지막 연산은 AND이므로 결과는 반드시 n 이하여야 하며, 마지막 원소는 n이어야 한다. n의 비트를 분해하여 lowbit(n)과 n - lowbit(n)을 이용해 OR로 n을 만들고, AND 시 값이 유지되도록 보조 값을 배치한다. 예: [lowbit(n), lowbit(n)+1 or 2, n-lowbit(n), n]
• 짝수 길이: 마지막 연산은 OR이므로 최대값은 2^t - 1 (t는 n의 비트 수). 특별히 n이 2의 거듭제곱일 경우, n-1을 구성하기 위해 [1, 3, n-2, n-1, n] 순으로 배치. 그 외에는 2^(t-1), n, 2^(t-1)-1 조합으로 마지막 세 칸을 채운다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

void solve() {
    int n; cin >> n;
    vector<int> result(n + 1, 0);
    vector<bool> used(n + 1, false);

    if (n & 1) {
        int lb = n & (-n);
        int a = lb;
        int b = (lb == 1) ? 3 : lb + 1;
        int c = n - lb;
        int d = n;
        result[n] = d; result[n-1] = c; result[n-2] = b; result[n-3] = a;
        used[a] = used[b] = used[c] = used[d] = true;
        cout << n << '\n';
    } else {
        int t = 1;
        while (t <= n) t <<= 1;
        cout << t - 1 << '\n';

        if (n != t / 2) {
            int x = t / 2, y = n, z = t / 2 - 1;
            result[n] = z; result[n-1] = y; result[n-2] = x;
            used[x] = used[y] = used[z] = true;
        } else {
            int w = 1, x = 3, y = n - 2, z = n - 1, u = n;
            result[n] = u; result[n-1] = z; result[n-2] = y; result[n-3] = x; result[n-4] = w;
            used[w] = used[x] = used[y] = used[z] = used[u] = true;
        }
    }

    int fill = 1;
    for (int i = 1; i <= n; ++i) {
        if (!result[i]) {
            while (used[fill]) ++fill;
            result[i] = fill;
            used[fill] = true;
        }
    }

    for (int i = 1; i <= n; ++i) cout << result[i] << ' ';
    cout << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

D번: 누적 비트시프트 최적화

배열의 각 원소는 2의 배수를 포함하며, 이를 다른 원소에게 넘겨 곱셈 효과를 줄 수 있다. 단, 인덱스 순서를 어길 수 없으므로 스택을 이용해 뒤에서부터 더 큰 값이 나올 경우 앞의 2 승수를 모두 가져오는 방식으로 처리한다. 모듈러 연산 중 과도한 시프트는 오버플로우를 유발할 수 있으므로 직접 곱셈 대신 지수 관리와 모듈러 거듭제곱을 활용한다.

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

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

int countTwos(long long &x) {
    int cnt = 0;
    while (x % 2 == 0) {
        x /= 2;
        cnt++;
    }
    return cnt;
}

void solve() {
    int n; cin >> n;
    vector<long long> a(n + 1), power(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        power[i] = countTwos(a[i]);
    }

    vector<int> stk;
    long long total = 0;
    auto addMod = [&](long long x) { return (total + x % MOD + MOD) % MOD; };

    for (int i = 1; i <= n; ++i) {
        long long currentVal = a[i] * modpow(2, power[i], MOD) % MOD;
        total = addMod(currentVal);

        while (!stk.empty() && a[stk.back()] < a[i]) {
            int j = stk.back(); stk.pop_back();
            long long prevContrib = (a[j] * modpow(2, power[j], MOD)) % MOD;
            total = addMod(-prevContrib);
            total = addMod(a[j]); // remove shift
            power[i] += power[j];
            long long newContrib = (a[i] * modpow(2, power[i], MOD)) % MOD;
            total = addMod(newContrib - currentVal);
            currentVal = newContrib;
        }
        stk.push_back(i);
        cout << total << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}