Subset with sum divisible by m

[907pqv (Violet)]

[https://www.geeksforgeeks.org/subset-sum-divisible-m/]
[https://practice.geeksforgeeks.org/problems/subset-with-sum-divisible-by-m/0]

E viết 1 thuật O(n*m) nhưng bị LTE. Sau đó e xem hướng dẫn thì thấy bài giải cũng là O(n*m) nhưng không biết sao lại ghi là O(m^2)? a/c xem giúp e với ạ!
Đây là code e bị LTE

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1000;
const int MAX_VALUE = 1000;
inline bool subsetsum(vector<int> &nums, int &m)
{
    bitset<MAX_SIZE * MAX_VALUE / 2 + 1> bits(1);
    int sum = 0;
    for (int &x : nums)
    {
        sum += x;
        bits |= bits << x;
    }
    for (int i = m; i <= sum; i += m)
    {
        if (bits[i])
        {
            return true;
        }
    }
    return false;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t, n, m;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        vector<int> nums(n);
        for (int i = 0; i < n; ++i) cin >> nums[i];
        if(n>m) 
        {   cout << "1" << endl;
	        continue;
        }
        if (subsetsum(nums, m)) cout << "1" << endl;
        else cout << "0" << endl;
    }

    return 0;
}

[rogp10]

n > m thì nó là true hẳn rồi theo nguyên lí Dirichlet, nên chỉ cần xét n <= m, nên O(m^2).

[907pqv (Violet)]

Nếu vậy thì code của e cũng O(m^2) vì e có chặn trường hợp n>m rồi. Mà ko biết sao LTE, e nghĩ cùng đpt thì làm trên bit phải nhanh hơn chứ nhỉ. Vì có 1 bài tương tự trên leetcode dùng mảng hoặc vector chạy khoảng 500ms, còn viết bằng bitset thì 4ms (cùng đpt).

[rogp10]

Code bạn là O(sum*n) đó.
Tổng chia hết cho m tức là mod m = 0, vậy thì chỉ cần xét [0…m-1] thôi nên O(m^2).

[907pqv (Violet)]

à, tks a. làm riết bị lú luôn