[SWEA] 1843 영준이의 숫자 고르기

출처: SWEA

Approach

bit 연산을 이용해서 자료를 재배치하는 문제이다.

- 배열 index N은 가장 큰수(마지막수)가 N인 경우의 수이다.

- 전체가 다 들어오고 나서 셈하는 것이 아닌 들어 올때마다 갱신된다.

 

▶ 비트마스크 (Bitmask) 

비트마스크 (Bitmask)

---

#include <stdio.h>
#define LL long long

const int MOD = 1000000007;
const int MAX_N = 1e5;
int N, S, TC, srr[MAX_N + 1];
LL card[MAX_N + 1], temp[MAX_N + 1];

void addBit(int idx, LL val)
{
    while (idx <= MAX_N)
    {
        card[idx] += val;
        card[idx] %= MOD;
        idx += (idx & -idx);
    }
}

void init()
{
    for (int i = 0; i < MAX_N + 1; i++)
    {
        card[i] = 0;
    }
    addBit(1, 1);
}

LL sumBit(int idx)
{
    LL sum = 0;
    while (idx > 0)
    {
        sum += card[idx];
        sum %= MOD;
        idx -= (idx & -idx);
    }
    return sum;
}

void input()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &S);
        for (int j = 0; j < S; j++)
        {
            scanf("%d", &srr[j]);
            temp[j] = sumBit(srr[j]) % MOD;
        }
        for (int j = 0; j < S; j++)
        {
            addBit(srr[j], temp[j]);
        }
    }
}

int main()
{
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for(int tc = 1; tc <= TC; ++tc)
    {
        init();
        input();
        printf("#%d %lld\n", tc, sumBit(MAX_N));
    }
}