Hỏi bài trên HackerRank: Bit Array

Cho 4 số nguyên N, S, P, Q. Tạo N số a_i với quy luật:

• a₀ = S
• a_i = ( P×a_i-1 + Q ) % 2³¹

Hỏi trong N số a_i đó có bao nhiêu số khác nhau đôi một (distinct integers)?

Ràng buộc:
1 ≤ N ≤ 10⁸
1 ≤ S, P, Q < 2³¹

Mình làm mà nó chỉ pass test case mẫu, còn các test case khác thì fail
Bạn có thể coi qua bài mình làm và chỉ ra chỗ sai của mình. Cám ơn !

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
typedef unsigned int UINT;

int main() {
	UINT N, S, P, Q;
	const UINT p231 = static_cast<UINT>(pow(2, 31));
	cin >> N >> S >> P >> Q;
	int *a = new int[p231/32];
	memset(a, 0, sizeof(int)*(p231/32));
	a[0] = S % p231;
	for (int i = 1; i < N; i++)
	{
		a[i] = (a[i - 1] * P + Q) % p231;
	}
	int result = 0;
	for (int i = 0; i < N - 1; i++)
	{
		for (int j = 1; j < N; j++)
		{
			if (a[i] != a[j])
				result++;
		}
	}
	cout << result << endl;
    return 0;
}

Bài mình làm bằng code java

public static void main(String[] args) {
    int N = 3;
    int S = 1;
    int P = 1;
    int Q = 1;
    int moduloShift = Integer.MAX_VALUE; // 2^31 - 1
    BitSet bitSet = new BitSet();
    long aiMinus1 = S; // use long to prevent number overflow
    long ai; // use long to prevent number overflow
    bitSet.set(S, true); //because S < 2^31 so S % 2^31 always is equal to S, no need to calculate 
    int count = 1;
    for (int i = 1; i < N; i++) {
        ai = (aiMinus1 * P + Q) & moduloShift;
        if (!bitSet.get((int) ai)){
            bitSet.set((int) ai, true); // mark that number has been exist
            count++;
        }
        aiMinus1 = ai;
    }
    System.out.println(count);
}

int *a = new int[p231/32];
…
a[0] = S % p231;

đâu có đúng. a trỏ tới mảng int, a[0] là int - 32 bit chứ đâu phải là 1 bit. Mình viết có lẽ chưa kỹ: tính được a_i thì set visited[a_i] = 1 chứ ko phải set visited[i] = 1. Mình viết “set a[i] = 1 khi tính được a_i” là viết tắt cho kiểu này.

C++ có kiểu vector<bool> là bit array đó, lấy nó mà xài.

vector<bool> visited(p231);
int a = S; //bắt đầu
while (N--)
{
    visited[a] = 1; //đánh dấu đã gặp a
    a = (static_cast<long long>(a) * P + Q) % p231; //tính a kế tiếp. Vì int*int có thể tràn số nên cast thành long long
}

rồi sau đó bạn có thể đếm số lượng bit 1 trong bit array visited:

int result = accumulate(begin(visited), end(visited), 0);

nhưng làm kiểu này rất là lâu, vì phải lướt 2³¹ phần tử. Trong khi n < 10⁸, nên đếm trong vòng for ở trên. Mình để bạn tự suy nghĩ vậy ha. Gợi ý là trong vòng lặp trên, chỉ cộng 1 cho result khi chưa gặp a. Nếu đã gặp a rồi (visited[a] == true) thì ko cộng 1.

thử với input
10000 573272257 859433109 1894136138
output là 10000. Xem nó chạy ná thở luôn vì length lên tới hơn 2 tỷ. N giới hạn là 100 triệu nên đếm ở trong vòng lặp N ấy.

Ok, thế để mình update, hehe

100000000 569099406 1607140150 823906344
output 31. Mình bị fail test case, nhưng cuối cùng cũng pass
Cám ơn bạn !

Bạn cho mình hỏi thêm: giả sử mình tính ai= 123 thì tương ứng với vị trí thứ 123 trong Bit Array và bật lên 1 đúng không?

đúng rồi. Nhưng trước khi bật xem vị trí thứ 123 có được bật chưa, tức là số 123 đã xuất hiện trước đó chưa, nếu đã có rồi thì đừng đếm nó, nếu chưa có thì mới đếm.