C++ solution with hash map
Code\n\nclass Solution {\n    static inline std::random_device rand_dev{};\n    static inline std::default_random_engine ng{rand_dev()};\n\n    int rows, cols, 
# Code\n```\nclass Solution {\n    static inline std::random_device rand_dev{};\n    static inline std::default_random_engine ng{rand_dev()};\n\n    int rows, cols, tail;\n    std::unordered_map<int, int> map;\n\n    int rand() {\n        std::uniform_int_distribution<int> dist(0, tail);\n        return dist(ng);\n    }\n\npublic:\n    Solution(int m, int n) : rows(m), cols(n) {\n        reset();\n    }\n\n    std::vector<int> flip() {\n        auto r = rand();\n        auto ij = r;\n        if (auto find = map.find(r); find != map.end()) {\n            ij = find->second;\n        }\n        if (auto find = map.find(tail); find != map.end()) {\n            map[r] = find->second;\n        } else {\n            map[r] = tail;\n        }\n        tail--;\n        return { ij / cols, ij % cols };\n    }\n\n    inline void reset() {\n        tail = rows * cols - 1;\n        map.clear();\n    }\n};\n```\n\nor another variant without `map.clear()` in `reset`:\n\n```\nclass Solution {\n    static inline std::random_device rand_dev{};\n    static inline std::default_random_engine ng{rand_dev()};\n\n    int rows, cols, tail;\n    std::unordered_map<int, int> map;\n\n    int rand() {\n        std::uniform_int_distribution<int> dist(0, tail);\n        return dist(ng);\n    }\n\npublic:\n    Solution(int m, int n) : rows(m), cols(n) {\n        reset();\n    }\n\n    std::vector<int> flip() {\n        auto r = rand();\n        auto ij = r;\n        if (auto find = map.find(r); find != map.end()) {\n            ij = find->second;\n        }\n        if (auto find = map.find(tail); find != map.end()) {\n            map[r] = find->second;\n        } else {\n            map[r] = tail;\n        }\n        map[tail] = ij;\n        tail--;\n        return { ij / cols, ij % cols };\n    }\n\n    inline void reset() {\n        tail = rows * cols - 1;\n    }\n};\n```
['C++']