随机生成一个不重复序列

给定连续的值域 $V$ 以及序列长度 $n$，如何随机生成一个均匀分布的单调递增序列？给定连续的值域 $V$ 以及序列长度 $n$，如何随机生成一个均匀分布的不重复序列？

主要是出题遇到了，思考了一下，很有意思。后来跟着 EarthMessenger 看了 python 源码，又学到了另一种做法。

这篇文章还有个英文版，更简洁：Generate a Non-repeating Sequence。

方法一

不妨来想一下最朴素的算法。我们直接把整个值域装数组，再 shuffle 一下。取前 $n$ 个，就可以做到 $O(|V|)$ 生成了。不过，shuffle 的常数较大，整个过程可以看做 $O(|V|w)$ 的，有没有更好的做法？

其实有一个更朴素的思想，不过有漏洞：直接随机 $n$ 次数字，构成一个序列。这个漏洞就是可能随机出重复的数字。那怎么解决呢？一个简单的做法是先把整个值域放进平衡树，选完直接删掉。那这样复杂度就是 $O(|V|+n \log n)$，不过阴间常数，肯定不好。解决办法也很简单：把整个值域放进 vector $x$，然后随一个下标 $y$，对应元素 $x[y]$ 放进目标 vector $z$，然后把 $x[y]$ 和 $x$ 末尾元素交换，再 pop 掉就可以了。总复杂度还是 $O(|V|+n)$，不过由于 rand 之类的有一定常数，整个过程可以看做 $O(|V|+nw)$ 的。由于 $n\leq|V|$，所以这个做法恒不劣于上面的做法，某些情况优于上面的做法。

分析正确性。假设当前选的是第 $i$ 个数，值域为 $n$，那么前面所有选择不选到 $z$ 的概率是：

当前选到 $z$ 的概率是 $\dfrac 1{n-i+1}$。所以 $z$ 被选中的概率是 $\dfrac 1n$。确实是均匀分布。

方法二

现在是人类智慧时刻。

还是上面那个朴素思想：不考虑重复直接随。遇到重复怎么办？别怕！还记得二次剩余怎么求吗？我们随机一个数字，重了就重了，大不了再选一个呗。就害怕，选了很多次都选到了重复的数字。

不过我们是随机选数字，自带随机化:) 所以算期望就行了。

我们先来解决这样一个问题：

做一件事，每次有 $p$ 的概率失败，$1-p$ 的概率成功。失败后继续尝试直到成功，成功后停止。求成功的期望次数。也就是：

这不就一个等比数列嘛！就是

哎呀！成功的期望次数就是成功的概率分之一！（虽然但是，据说这是经典结论，好像还很直觉 QwQ）

我们要求随机不重复一个数字的复杂度，所以算一个上限就好。上限显然在选第 $n$ 个数的时候达到。此时成功的概率是 $\dfrac {|V|-n+1}{|V|}$。设 $|V|=(n-1)k$，那么，期望复杂度是：

那么，我们要选 $n$ 个，总的复杂度就是 $O(n\cdot\dfrac k{k-1})$。不过，判断一个数是否出现过，由于值域较大，可能需要平衡树来处理，复杂度 $O(n\log n\cdot\dfrac k{k-1})$。省略掉了 $V$，巨大进步！！！

缝合怪

但是上面这个算法仍然不能满足所有情况，比方说 $n=V$ 的时候，每次选择都是巨大的代价，期望复杂度都来到了惊人的 $O(n^2)$。

那么，我们不妨类似整除分块的做法，什么算法更快，采用什么办法。显然，$k$ 较大的时候，采用下面 $O(n\log n\cdot\dfrac k{k-1})$ 的算法；否则，采用上面 $O(|V|+n)$ 的算法。那具体什么时候呢？稍微解一下下面这个方程就好了。

解得：$k\leq \dfrac {\log n+1}2$。所以不妨设一个阈值 $B=\dfrac {\log n+1}2$，当 $k\leq B$ 时，采用上面的做法，否则采用下面的做法。分析一下复杂度。当 $k\leq 2$ 时，$|V|=k(n-1)$，那么，复杂度是 $O(|V|+n)=O(n \log n)$ 的；当 $k>B$ 时，$\dfrac k{k-1}<2$，可以看做常数，所以也是 $O(n \log n)$ 的。总复杂度 $O(n \log n)$。

进一步优化

优化 1

显然我们还可以再优化。比方说，对于 $n\log n\geq |V|$ 的，可以直接采用上面的 $O(|V|+n)$ 的做法，或者用 std::sort 进行时空常数优化。这样，时空复杂度是 $O(\min \{|V|,n\log n\})$ 的。不过，由于刚才算了合理的阈值，这个优化并不重要。

优化 2

另外一个优化是关于时间复杂度的优化。我们判断一个数是否出现过，不仅可以用 set，还可以用哈希表。这样时间复杂度又会变优，但是时空常数阴间。此时第二个方法的复杂度又会变成 $O(n\cdot \dfrac k{k-1})$ 的。解一下：

解得：$0<k\leq 2$。所以设阈值 $B=2$，当 $k\leq B$ 时，采用上面的做法，否则采用下面的做法。再分析一下复杂度。当 $k\leq 2$ 时，$|V|=k(n-1)$，$k$ 可以看做常数，那么，复杂度是 $O(|V|+n)=O(n)$ 的；当 $k>2$ 时，$\dfrac k{k-1}<2$，可以看做常数，所以也是 $O(n)$ 的。总复杂度 $O(n)$。

优化 3

还是判断一个数是否出现的优化。当 $|V|$ 不大，且空间富余的时候，可以采用常用的 vis 数组判断。使用 std::bitset 可以大幅优化常数。当 $|V|\leq 10^8$ 的时候可以考虑使用这个方法进行常数优化。

优化 4

我们很多情况下不需要那么随机。所以我们可以把值域平均分成 $K$ 块，每块分别求解。这样时间复杂度不变，空间复杂度变为 $O(\dfrac nK)$ 或 $O(\dfrac {|V|}K)$。

方法三/优化 5

睡觉的时候，又想到一个方法三。具体来说，我们先随机 $n$ 个数，然后排序去重。设现在剩下 $m$ 个数，那么，令 $n=m$，递归地求解。这个复杂度我不会证，干脆打个表：

            n/V             Exp
         0.0001               1
         0.0002               1
         0.0004               1
         0.0008               1
         0.0016               1
         0.0032               1
         0.0064               2
         0.0128               2
         0.0256               2
         0.0512               3
         0.1024               4
         0.2048               6
         0.4096              11
         0.8192            47.7

$Exp$ 表示的是，按照上面的方法，使当前得到至少 $n-100$ 个数的平均次数。

发现在 $\dfrac n{|V|}$ 比较小的时候，期望次数是非常少的。那么，在上面的方法中，如果 $k$ 很大（$\dfrac n{|V|}$ 很小），应用这个方法先生成前 $n-100$ 或前 $x\%$ 个数，再使用方法二生成剩下的个数，可以小幅优化时空常数。

（到后面这个方法有惊喜）

附打表程序：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<random>
#include<ctime>
using namespace std;

signed main() {
    vector<int> v;
    cout.precision(13);
    int V=1e7;
    uniform_int_distribution<> dist(1,V);
    cout<<setw(15)<<"n/V"<<' '<<setw(15)<<"Exp"<<endl;
    for(int n=1000;n<=10000000;n*=2) {
        double rr=0;
        for(int sd=1;sd<=10;sd++) {
            mt19937 gen(sd+time(0)+clock());
            v.clear();
            int cnt=0;
            while((int)v.size()<=n-100) {
                while((int)v.size()<n) v.push_back(dist(gen));
                sort(v.begin(),v.end());
                v.erase(unique(v.begin(),v.end()),v.end());
                cnt++;
            }
            rr+=cnt;
        }
        cout<<setw(15)<<double(n)/V<<' '<<setw(15)<<rr/10<<endl;
    }
    return 0;
}

方法四，逆天

此方法，是我写错了方法三的代码，得到的优化版方法三。也就是，不要只填剩下的个数，我们再填 $n$ 个数进去。设去重后有 $m$ 个数，只要 $m\geq n$，我们的目的就达到了。

打表代码大概是这样的：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<random>
#include<ctime>
using namespace std;

signed main() {
    vector<int> v;
    cout.precision(13);
    int V=1e7;
    uniform_int_distribution<> dist(1,V);
    cout<<setw(15)<<"n/V"<<' '<<setw(15)<<"Exp"<<endl;
    for(int n=1000;n<=1e7;n*=2) {
        double rr=0;
        for(int sd=1;sd<=10;sd++) {
            mt19937 gen(sd+time(0)+clock());
            v.clear();
            int cnt=0;
            while((int)v.size()<n) {
                for(int i=1;i<=n;i++) v.push_back(dist(gen)); // 不同点
                sort(v.begin(),v.end());
                v.erase(unique(v.begin(),v.end()),v.end());
                cnt++;
            }
            rr+=cnt;
        }
        cout<<setw(15)<<double(n)/V<<' '<<setw(15)<<rr/10<<endl;
    }
    return 0;
}

打表出来是这样的：

            n/V             Exp
         0.0001               1
         0.0002               1
         0.0004             1.3
         0.0008               2
         0.0016               2
         0.0032               2
         0.0064               2
         0.0128               2
         0.0256               2
         0.0512               2
         0.1024               2
         0.2048               2
         0.4096               2
         0.8192               3
      0.9888888               5

极其恐怖！！！

试了试 $V$ 比较小的情况（$|V|=10$）：

            n/V             Exp
            0.1               1
            0.2               1
            0.4             1.3
            0.8             2.5

仍然很理想！

只有在 $n\approx |V|$ 的时候比较慢，那这时候就跑 $O(|V|+n)$。这个做法常数还小！！！虽然我不知道怎么回事，但是这个做法绝对比方法二牛牛。我们把方法二替换成这个做法再跑缝合怪，得到了小常数 $O(n)$ 算法！

不过——

方法四的均匀分布不能保证，所以只能在不需要均匀分布的时候使用。不过大多数情况下都不需要均匀分布，所以尽管放心用了。

初步总结

• 均匀分布非常重要的时候，使用缝合怪+优化 1,2,3,5；
• 均匀分布基本不重要的时候，使用缝合怪+优化 1,2,3,4,5；
• 均匀分布完全不重要的时候，使用方法四。

实现

$O(n\log n)$ 实现

初步实现了 $O(n\log n)$ 算法（没有保证上升，只是保证了不重复），并且加入了优化 3,5。

/**
 * @author robinyqc ([email protected])
 * @brief random uniform nonrepeating sequence generation
 * @link https://www.luogu.com.cn/blog/robinyqc-blog/sui-ji-sheng-cheng-yi-ge-shang-sheng-xu-lie
 */
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<limits>
#include<cmath>
#include<bitset>

const int MAXLEN=1<<26;

template<typename IntType=int,class Checker=std::set<IntType>, 
    class UniformIntDistrbution=std::uniform_int_distribution<IntType> >
class UniformNonredundantIntGenration {
    typedef IntType T;
    static_assert(std::is_integral<T>::value, 
        "IntType must be a supported integer type");
    public:
        UniformNonredundantIntGenration(T mn=std::numeric_limits<T>::min(),T mx=std::numeric_limits<T>::max())
            :lwb_(mn),upb_(mx) {V=(double)upb_-(double)lwb_;}
        
        void set_bound(T mn,T mx) {lwb_=mn,upb_=mx,V=upb_-lwb_+1;}
        
        template<typename URNG>
        std::vector<T> operator()(int n,URNG &gen) {
            double B=(log2(n)+1)/2;
            if(V>=B*(n-1)) {
                if(V<=(1<<26)) {
                    std::vector<T> ret;
                    ret.reserve(n);
                    bitset_opt_sparse_gen(n,gen,ret);
                    return ret;
                }
                return sparse_gen(n,gen);
            }
            return dense_gen(n,gen);
        }
    private:
        T lwb_,upb_;
        T V;

        // template<typename URNG>
        // std::vector<T> sparse_gen(int n,URNG &gen) {
        //     UniformIntDistrbution dist(lwb_,upb_);
        //     Checker vis;
        //     std::vector<T> ans;
        //     for(int i=1;i<=n;i++) {
        //         T nw;
        //         do nw=dist(gen);
        //         while(vis.count(nw));
        //         ans.push_back(nw);
        //         vis.insert(nw);
        //     }
        //     return ans;
        // }

        template<typename URNG>
        std::vector<T> sparse_gen(int n,URNG &gen) {
            UniformIntDistrbution dist(lwb_,upb_);
            int B=std::min((unsigned long long)V/40,(unsigned long long)std::max(n-100,0));
            Checker vis;
            std::vector<T> ans;
            ans.reserve(n);
            while((int)ans.size()<B) {
                while((int)ans.size()<n) ans.push_back(dist(gen));
                std::sort(ans.begin(),ans.end());
                ans.erase(std::unique(ans.begin(),ans.end()),ans.end());
            }
            for(auto &i:ans) vis.insert(i);
            for(int i=ans.size()+1;i<=n;i++) {
                T nw;
                do nw=dist(gen);
                while(vis.count(nw));
                vis.insert(nw);
                ans.push_back(nw);
            }
            return ans;
        }

        template<typename URNG,int len=1>
        void bitset_opt_sparse_gen(int n,URNG &gen,std::vector<T> &ans) {
            if(V>len) {
                // std::cout<<len<<' '<<MAXLEN<<std::endl;
                bitset_opt_sparse_gen<URNG,std::min(MAXLEN,len<<1)>(n,gen,ans);
                return ;
            }
            UniformIntDistrbution dist(lwb_,upb_);
            std::bitset<len> *vis=new std::bitset<len>();
            vis->reset();
            for(int i=1;i<=n;i++) {
                T nw;
                do nw=dist(gen);
                while(vis->operator[](nw-lwb_));
                ans.push_back(nw);
                vis->operator[](nw-lwb_)=1;
            }
            delete vis;
        }

        template<typename URNG>
        std::vector<T> dense_gen(int n,URNG &gen) {
            std::vector<T> ans;
            ans.reserve(n);
            std::vector<T> rng((size_t)V);
            for(int i=lwb_;i<=upb_;i++) rng[i-lwb_]=i;
            for(int i=1;i<=n;i++) {
                UniformIntDistrbution dist(0,rng.size()-1);
                int nw=dist(gen);
                ans.push_back(rng[nw]);
                std::swap(rng[nw],rng.back());
                rng.pop_back();
            }
            return ans;
        }
};

signed main() {
    int Q;
    std::cin>>Q;
    std::mt19937 gen(1993);
    UniformNonredundantIntGenration<> UNIG;
    while(Q--) {
        int n,a,b;
        std::cin>>a>>b>>n;
        UNIG.set_bound(a,b);
        auto v=UNIG(n,gen);
        // for(auto i:v) std::cout<<i<<' ';
        // std::cout<<std::endl;
        std::cout<<"fine\n";
    }
    return 0;
}

非常好！这份代码的正确性我们用如下程序验证（test.in 是由上面程序生成的一个 $n=10^6,a=1,b=10^9$ 的序列）：

#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<random>
#include<cctype>
#include<iomanip>
using namespace std;

#define int long long

int x[10000005];
int cnt[10000001];

signed main() {
    freopen("test.in","r",stdin);
    int n,V=1e9;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>x[i];
    double avg=0;
    double var=0;
    cout.precision(10);
    for(int i=1;i<=n;i++) avg+=x[i];
    avg/=n;
    cout<<"Average number: "<<avg<<endl;
    for(int i=1;i<=n;i++) var+=(x[i]-avg)*(x[i]-avg);
    cout<<"Variance value: "<<var/(n-1)<<endl;
    cout<<"\nBlock test:"<<endl;
    cout<<setw(10)<<"Block size"<<setw(18)<<"Average distance"<<setw(15)<<"Variance"<<endl;
    for(int i=3,j=1000,ed=log10(V)+0.5;i<=ed;i++,j*=10) {
        cout<<setw(10)<<j;
        memset(cnt,0,sizeof(cnt));
        for(int k=1;k<=n;k++) cnt[(x[k]-1)/j]++;
        int lim=V/j,avgdis=abs(cnt[0]-cnt[lim-1]);
        avg=(double)n/lim,var=0;
        for(int k=0;k<lim-1;k++) avgdis+=abs(cnt[i+1]-cnt[i]);
        for(int k=0;k<lim;k++) var+=(cnt[k]-avg)*(cnt[k]-avg);
        cout<<setw(18)<<avgdis/(double)n<<setw(15)<<var/n<<endl;
    }
    return 0;
}

我的电脑的结果是：

Average number: 499849719.6
Variance value: 8.33604178e+16

Block test:
Block size  Average distance       Variance
      1000          0.999999       0.997594
     10000          0.299999       1.001514
    100000          0.080011       0.999544
   1000000          0.018983       0.919822
  10000000          0.009383       0.857388
 100000000          0.001625        1.18481
1000000000                 0              0

前两个分别是平均数和方差。根据数学知识我们可以知道期望均值是 $\dfrac {a+b}2$，符合预期；方差是 $\dfrac {(b-a+1)^2-1} {12}$，也符合预期。

后面是，将值域分成若干个等长的块，统计每个块内的出现的数的数量。Average distance 的含义可以见上面代码，总之越靠近 $0$ 越好。可以发现也是非常理想的。

最后是效率。不开 O2 在跑方法二时比 python 还慢，bitset 优化是 python 的两倍左右。开了 O2 最劣是 python 1.5 倍快。bitset 优化甚至达到了 10 倍效率。

$O(n)$ 实现

按照方法二加上优化 2 我们可以得到一个 $O(n)$ 做法。只需要把上面代码改一下就好了，这里就不赘述了。贴个代码还是：

/**
 * @author robinyqc ([email protected])
 * @brief random uniform nonrepeating sequence generation
 * @link https://www.luogu.com.cn/blog/robinyqc-blog/sui-ji-sheng-cheng-yi-ge-shang-sheng-xu-lie
 */
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<limits>
#include<cmath>
#include<bitset>

const int MAXLEN=1<<26;

namespace RadixSort {

namespace __RadixSort {
int cnt[32][256],n,cc=0;
template<typename Iter1,typename Iter2> 
void __radix_sort(Iter1 a,Iter2 b,int len) {
    int tim=n>>3,dt=len<<3;
    auto nw=a+n-1;
    while(tim--){
        b[--cnt[len][nw[0]>>dt&255]]=nw[0];
        b[--cnt[len][nw[-1]>>dt&255]]=nw[-1];
        b[--cnt[len][nw[-2]>>dt&255]]=nw[-2];
        b[--cnt[len][nw[-3]>>dt&255]]=nw[-3];
        b[--cnt[len][nw[-4]>>dt&255]]=nw[-4];
        b[--cnt[len][nw[-5]>>dt&255]]=nw[-5];
        b[--cnt[len][nw[-6]>>dt&255]]=nw[-6];
        b[--cnt[len][nw[-7]>>dt&255]]=nw[-7];
        nw-=8;
        
    }
    switch(n&7){
        case 7:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 6:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 5:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 4:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 3:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 2:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 1:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
    }

}
}

template<typename IntType,typename Iter,bool chkmx=false> 
void radix_sort(Iter st,Iter ed) {
    typedef IntType T;
    static_assert(std::is_unsigned<T>::value&&std::is_integral<T>::value,
        "Need unsigned integer. Pleas use to_unsigned to access.");
    T rmx=std::numeric_limits<IntType>::max()>>8;
    T mx=0,*b=new T[ed-st](),v=1;
    Iter a=st;
    int tot=1;
    for(T i=1;i<rmx;i<<=8) tot++;
    if(chkmx) {for(auto nw=st;nw!=ed;nw++) if(*nw>mx) mx=*nw;}
    else mx=std::numeric_limits<IntType>::max();
    __RadixSort::n=ed-st,v=0;
    for(int len=0;len<tot;len++,v=(len<<3)) {
        memset(__RadixSort::cnt[len],0,sizeof(__RadixSort::cnt[len]));
        for(auto nw=st;nw!=ed;++nw) ++__RadixSort::cnt[len][*nw>>v&255];
    }
        
    for(int len=0;len<tot;len++) for(int i=1;i<256;++i) {
        __RadixSort::cnt[len][i]+=__RadixSort::cnt[len][i-1];
    }
    bool p=1;
    v=1;
    for(int len=0;len<tot;len++,p^=1,v<<=3) {
        if(p) __RadixSort::__radix_sort(a,b,len);
        else __RadixSort::__radix_sort(b,a,len);
        if(v>=mx) break;
    }
    if(!p) for(int i=0;i<__RadixSort::n;i++) a[i]=b[i];
    delete []b;
}

}

template<typename IntType=int,
         class UniformIntDistrbution=std::uniform_int_distribution
            <typename std::make_unsigned<IntType>::type>,
         class Checker=std::set<typename std::make_unsigned<IntType>::type>,
         bool linear=false >
class UniformNonredundantIntGenration {
    typedef IntType T;
    typedef typename std::make_unsigned<T>::type UT;
    static_assert(std::is_integral<T>::value, 
        "IntType must be a supported integer type");
    public:
        UniformNonredundantIntGenration(T mn=std::numeric_limits<T>::min(),T mx=std::numeric_limits<T>::max())
            :lwb_(to_unsigned(mn)),upb_(to_unsigned(mx)) {V=upb_-lwb_;}

        void set_bound(T mn,T mx) {lwb_=to_unsigned(mn),upb_=to_unsigned(mx),V=upb_-lwb_;}

        template<typename URNG>
        std::vector<T> operator ()(int n,URNG &gen) {
            // std::cout<<lwb_<<' '<<upb_<<'\n';
            auto x=get(n,gen);
            std::vector<T> ans(n);
            for(int i=0;i<n;i++) ans[i]=to_ori(x[i]);
            return ans;
        }
        
    private:
        UT lwb_,upb_;
        UT V;

        // template<typename URNG>
        // std::vector<T> sparse_gen(int n,URNG &gen) {
        //     UniformIntDistrbution dist(lwb_,upb_);
        //     Checker vis;
        //     std::vector<T> ans;
        //     for(int i=1;i<=n;i++) {
        //         T nw;
        //         do nw=dist(gen);
        //         while(vis.count(nw));
        //         ans.push_back(nw);
        //         vis.insert(nw);
        //     }
        //     return ans;
        // }

        template<typename URNG>
        std::vector<UT> get(int n,URNG &gen) {
            double B=(!linear)?((log2(n)+1)/2):2.0;
            // std::cerr<<B<<'\n';
            if((double)V+1>=B*(n-1)) {
                if(V<=MAXLEN) {
                    std::vector<UT> ret;
                    ret.reserve(n);
                    bitset_opt_sparse_gen(n,gen,ret);
                    return ret;
                }
                return sparse_gen(n,gen);
            }
            return dense_gen(n,gen);
        }

        template<typename URNG>
        std::vector<UT> sparse_gen(int n,URNG &gen) {
            UniformIntDistrbution dist(lwb_,upb_);
            int B=std::min((UT)V/40,(UT)std::max(n-100,0));
            Checker vis;
            std::vector<UT> ans;
            ans.reserve(n);
            auto ansb=ans.end();
            while((int)ans.size()<B) {
                while((int)ans.size()<n) ans.push_back(dist(gen));
                robin_sort(ansb,ans.end());
                std::inplace_merge(ans.begin(),ansb,ans.end());
                ans.erase(std::unique(ans.begin(),ans.end()),ans.end());
                ansb=ans.end();
            }
            for(auto &i:ans) vis.insert(i);
            for(int i=ans.size()+1;i<=n;i++) {
                UT nw;
                do nw=dist(gen);
                while(vis.count(nw));
                vis.insert(nw);
                ans.push_back(nw);
            }
            return ans;
        }

        template<typename URNG,int len=1>
        void bitset_opt_sparse_gen(int n,URNG &gen,std::vector<UT> &ans) {
            if(V>len) {
                // std::cout<<len<<' '<<MAXLEN<<std::endl;
                bitset_opt_sparse_gen<URNG,std::min(MAXLEN,len<<1)>(n,gen,ans);
                return ;
            }
            UniformIntDistrbution dist(lwb_,upb_);
            std::bitset<len> *vis=new std::bitset<len>();
            vis->reset();
            for(int i=1;i<=n;i++) {
                UT nw;
                do nw=dist(gen);
                while(vis->operator[](nw-lwb_));
                ans.push_back(nw);
                vis->operator[](nw-lwb_)=1;
            }
            delete vis;
        }

        template<typename URNG>
        std::vector<UT> dense_gen(int n,URNG &gen) {
            std::vector<UT> ans;
            ans.reserve(n);
            std::vector<UT> rng((unsigned long long)V+1);
            for(UT i=lwb_;i<=upb_;i++) rng[i-lwb_]=i;
            for(int i=1;i<=n;i++) {
                UniformIntDistrbution dist(0,rng.size()-1);
                int nw=dist(gen);
                ans.push_back(rng[nw]);
                std::swap(rng[nw],rng.back());
                rng.pop_back();
            }
            return ans;
        }

        template<typename Iter>
        void robin_sort(Iter st,Iter  ed) {
            if(ed-st<=100000) std::sort(st,ed);
            else RadixSort::radix_sort<UT>(st,ed);
        }

        UT to_unsigned(T x) {
            if(std::is_same<T,UT>::value) return x;
            UT y;
            if(x<0) y=x+std::numeric_limits<T>::max()+1;
            else y=x,y+=(UT)std::numeric_limits<T>::max()+1;
            return y;
        }

        T to_ori(UT x) {
            if(std::is_same<T,UT>::value) return x;
            T y;
            if(x>(UT)std::numeric_limits<T>::max()) 
                y=x-(UT)std::numeric_limits<T>::max()-1;
            else y=x,y-=std::numeric_limits<T>::max(),y--;
            return y;
        }
};

signed main() {
    // freopen("test.in","w",stdout);
    int Q=1;
    // std::cin>>Q;
    std::mt19937 gen(19937);
    UniformNonredundantIntGenration<int,std::uniform_int_distribution<unsigned>,std::unordered_set<unsigned>,true> UNIG;
    while(Q--) {
        int n=4e6,a=-1e9,b=1e9;
        // std::cin>>a>>b>>n;
        UNIG.set_bound(a,b);
        auto v=UNIG(n,gen);
        // std::cout<<n<<'\n';
        // for(auto i:v) std::cout<<i<<' ';
        // std::cout<<'\n';
        // std::cout<<"fine\n";
    }
    return 0;
}

不过！

经过几番测试，我发现哈希的常数太阴间。真的不适合，甚至比 $O(n\log n)$ 还要慢 $100$ms（$n=2\times10^6$）。

怎么办呢？

在无意中我想到，要不直接只用方法三，不结合方法二呢？

似乎，方法三在比率不合适的时候常数太大。可是，在方法二的常数相比下，这个常数，真的大吗？首先，比率应该小于 $0.5$，那么常数顶天 $20$ 了。好像，真的更优？

还真是。

这是只使用方法三的表(unsigned int)：

            n/V             Exp
         0.0001             1.2
         0.0002             1.2
         0.0004             1.9
         0.0008             1.9
         0.0016               2
         0.0032             2.2
         0.0064             2.7
         0.0128             3.1
         0.0256             3.9
         0.0512               5
         0.1024             6.4
         0.2048             9.4
         0.4096            16.9
         0.8192            71.8

上表是方法三跑满 $n$ 的表现。我们用不上 n/V=0.8 那组，所以看起来不错。

跑 $6e6$ 数据是哈希做法的 $3$ 到 $6$ 倍快。

似乎可能慢于上面代码的情况，只有值域很小了。但是我们有严格优于哈希的小值域 bitset 做法。结合这个。这样就是最优了！

对于方法三，我们还可以优化！我们发现已经生成过的数是有序的，只有新生成的数无序。所以我们对新生成的数排序并且归并一下就好了。常数，get!

还是上代码：

/**
 * @author robinyqc ([email protected])
 * @brief random uniform nonrepeating sequence generation
 * @link https://www.luogu.com.cn/blog/robinyqc-blog/sui-ji-sheng-cheng-yi-ge-shang-sheng-xu-lie
 */
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<limits>
#include<cmath>
#include<bitset>

const int MAXLEN=1<<26;

namespace RadixSort {

namespace __RadixSort {
int cnt[32][256],n,cc=0;
template<typename Iter1,typename Iter2> 
void __radix_sort(Iter1 a,Iter2 b,int len) {
    int tim=n>>3,dt=len<<3;
    auto nw=a+n-1;
    while(tim--){
        b[--cnt[len][nw[0]>>dt&255]]=nw[0];
        b[--cnt[len][nw[-1]>>dt&255]]=nw[-1];
        b[--cnt[len][nw[-2]>>dt&255]]=nw[-2];
        b[--cnt[len][nw[-3]>>dt&255]]=nw[-3];
        b[--cnt[len][nw[-4]>>dt&255]]=nw[-4];
        b[--cnt[len][nw[-5]>>dt&255]]=nw[-5];
        b[--cnt[len][nw[-6]>>dt&255]]=nw[-6];
        b[--cnt[len][nw[-7]>>dt&255]]=nw[-7];
        nw-=8;
        
    }
    switch(n&7){
        case 7:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 6:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 5:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 4:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 3:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 2:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 1:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
    }

}
}

template<typename IntType,typename Iter,bool chkmx=false> 
void radix_sort(Iter st,Iter ed) {
    typedef IntType T;
    static_assert(std::is_unsigned<T>::value&&std::is_integral<T>::value,
        "Need unsigned integer. Pleas use to_unsigned to access.");
    T rmx=std::numeric_limits<IntType>::max()>>8;
    T mx=0,*b=new T[ed-st](),v=1;
    Iter a=st;
    int tot=1;
    for(T i=1;i<rmx;i<<=8) tot++;
    if(chkmx) {for(auto nw=st;nw!=ed;nw++) if(*nw>mx) mx=*nw;}
    else mx=std::numeric_limits<IntType>::max();
    __RadixSort::n=ed-st,v=0;
    for(int len=0;len<tot;len++,v=(len<<3)) {
        memset(__RadixSort::cnt[len],0,sizeof(__RadixSort::cnt[len]));
        for(auto nw=st;nw!=ed;++nw) ++__RadixSort::cnt[len][*nw>>v&255];
    }
        
    for(int len=0;len<tot;len++) for(int i=1;i<256;++i) {
        __RadixSort::cnt[len][i]+=__RadixSort::cnt[len][i-1];
    }
    bool p=1;
    v=1;
    for(int len=0;len<tot;len++,p^=1,v<<=3) {
        if(p) __RadixSort::__radix_sort(a,b,len);
        else __RadixSort::__radix_sort(b,a,len);
        if(v>=mx) break;
    }
    if(!p) for(int i=0;i<__RadixSort::n;i++) a[i]=b[i];
    delete []b;
}

}

template<typename IntType=int,
         class UniformIntDistrbution=std::uniform_int_distribution 
            <typename std::make_unsigned<IntType>::type> >
        //  class Checker=std::set<typename std::make_unsigned<IntType>::type>,
        //  bool linear=false >
class UniformNonredundantIntGenration {
    typedef IntType T;
    typedef typename std::make_unsigned<T>::type UT;
    static_assert(std::is_integral<T>::value, 
        "IntType must be a supported integer type");
    public:
        UniformNonredundantIntGenration(T mn=std::numeric_limits<T>::min(),T mx=std::numeric_limits<T>::max())
            :lwb_(to_unsigned(mn)),upb_(to_unsigned(mx)) {V=upb_-lwb_;}

        void set_bound(T mn,T mx) {lwb_=to_unsigned(mn),upb_=to_unsigned(mx),V=upb_-lwb_;}

        template<typename URNG>
        std::vector<T> operator ()(int n,URNG &gen) {
            // std::cout<<lwb_<<' '<<upb_<<'\n';
            auto x=get(n,gen);
            std::vector<T> ans(n);
            for(int i=0;i<n;i++) ans[i]=to_ori(x[i]);
            return ans;
        }
        
    private:
        UT lwb_,upb_;
        UT V;

        // template<typename URNG>
        // std::vector<T> sparse_gen(int n,URNG &gen) {
        //     UniformIntDistrbution dist(lwb_,upb_);
        //     Checker vis;
        //     std::vector<T> ans;
        //     for(int i=1;i<=n;i++) {
        //         T nw;
        //         do nw=dist(gen);
        //         while(vis.count(nw));
        //         ans.push_back(nw);
        //         vis.insert(nw);
        //     }
        //     return ans;
        // }

        template<typename URNG>
        std::vector<UT> get(int n,URNG &gen) {
            double B=2.0;
            // std::cerr<<B<<'\n';
            if((double)V+1>=B*(n-1)) {
                if(V<=MAXLEN) {
                    std::vector<UT> ret;
                    ret.reserve(n);
                    bitset_opt_sparse_gen(n,gen,ret);
                    return ret;
                }
                return sparse_gen(n,gen);
            }
            return dense_gen(n,gen);
        }

        template<typename URNG>
        std::vector<UT> sparse_gen(int n,URNG &gen) {
            UniformIntDistrbution dist(lwb_,upb_);
            // Checker vis;
            std::vector<UT> ans;
            ans.reserve(n);
            auto ansb=ans.end();
            // long long cnt=0;
            while((int)ans.size()<n) {
                while((int)ans.size()<n) ans.push_back(dist(gen));
                robin_sort(ansb,ans.end());
                std::inplace_merge(ans.begin(),ansb,ans.end());
                ans.erase(std::unique(ans.begin(),ans.end()),ans.end());
                ansb=ans.end();
                // cnt++;
                // if(cnt*n>=4e8) break;
            }
            // if((int)ans.size()!=n) {
            //     std::set<UT> vis;
            //     for(auto &i:ans) vis.insert(i);
            //     for(int i=ans.size()+1;i<=n;i++) {
            //         UT nw;
            //         do nw=dist(gen);
            //         while(vis.count(nw));
            //         vis.insert(nw);
            //         ans.push_back(nw);
            //     }
            // }
            return ans;
        }

        template<typename URNG,int len=1>
        void bitset_opt_sparse_gen(int n,URNG &gen,std::vector<UT> &ans) {
            if(V>len) {
                // std::cout<<len<<' '<<MAXLEN<<std::endl;
                bitset_opt_sparse_gen<URNG,std::min(MAXLEN,len<<1)>(n,gen,ans);
                return ;
            }
            UniformIntDistrbution dist(lwb_,upb_);
            std::bitset<len> *vis=new std::bitset<len>();
            vis->reset();
            for(int i=1;i<=n;i++) {
                UT nw;
                do nw=dist(gen);
                while(vis->operator[](nw-lwb_));
                ans.push_back(nw);
                vis->operator[](nw-lwb_)=1;
            }
            delete vis;
        }

        template<typename URNG>
        std::vector<UT> dense_gen(int n,URNG &gen) {
            std::vector<UT> ans;
            ans.reserve(n);
            std::vector<UT> rng((unsigned long long)V+1);
            for(UT i=lwb_;i<=upb_;i++) rng[i-lwb_]=i;
            for(int i=1;i<=n;i++) {
                UniformIntDistrbution dist(0,rng.size()-1);
                int nw=dist(gen);
                ans.push_back(rng[nw]);
                std::swap(rng[nw],rng.back());
                rng.pop_back();
            }
            return ans;
        }

        template<typename Iter>
        void robin_sort(Iter st,Iter  ed) {
            if(ed-st<=100000) std::sort(st,ed);
            else RadixSort::radix_sort<UT>(st,ed);
        }

        UT to_unsigned(T x) {
            if(std::is_same<T,UT>::value) return x;
            UT y;
            if(x<0) y=x+std::numeric_limits<T>::max()+1;
            else y=x,y+=(UT)std::numeric_limits<T>::max()+1;
            return y;
        }

        T to_ori(UT x) {
            if(std::is_same<T,UT>::value) return x;
            T y;
            if(x>(UT)std::numeric_limits<T>::max()) 
                y=x-(UT)std::numeric_limits<T>::max()-1;
            else y=x,y-=std::numeric_limits<T>::max(),y--;
            return y;
        }
};

signed main() {
    freopen("test.in","w",stdout);
    int Q=1;
    // std::cin>>Q;
    std::mt19937 gen(1993);
    UniformNonredundantIntGenration<int> UNIG;
    while(Q--) {
        int n=1e6,a=1,b=1e9;
        // std::cin>>a>>b>>n;
        UNIG.set_bound(a,b);
        auto v=UNIG(n,gen);
        std::cout<<n<<'\n';
        for(auto i:v) std::cout<<i<<' ';
        std::cout<<'\n';
        // std::cout<<"fine\n";
    }
    return 0;
}

// 4e6 0.3s
// 1e8 26s

这东西的用法，仔细读读应该就能知道了。我懒，就不说了。

用相同的数据范围在刚才的评定程序跑一下：

Average number: 499849719.6
Variance value: 8.33604178e+16

Block test:
Block size  Average distance       Variance
      1000          0.999999       0.997594
     10000          0.299999       1.001514
    100000          0.080011       0.999544
   1000000          0.018983       0.919822
  10000000          0.009383       0.857388
 100000000          0.001625        1.18481
1000000000                 0              0

非常好了！（这数据和刚才一样。不过我反复确认了是这次的数据。）

总之，这下真能吊打 py 了。

upd on 2023/8/27

更新了预处理 bitset 的做法。花费大约 0.1s 预处理 bitset 可以在生成时获得更好的常数。不过，如果你只生成一个序列，预处理反而是累赘。使用 UNIG::pret_bitset() 即可。

/**
 * @author robinyqc ([email protected])
 * @brief random uniform nonrepeating sequence generation
 * @link https://www.luogu.com.cn/blog/robinyqc-blog/sui-ji-sheng-cheng-yi-ge-shang-sheng-xu-lie
 */
#include<iostream>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<limits>
#include<cmath>
#include<bitset>

const int MAXLEN=1<<26;

namespace RadixSort {

namespace __RadixSort {
int cnt[32][256],n,cc=0;
template<typename Iter1,typename Iter2> 
void __radix_sort(Iter1 a,Iter2 b,int len) {
    int tim=n>>3,dt=len<<3;
    auto nw=a+n-1;
    while(tim--){
        b[--cnt[len][nw[0]>>dt&255]]=nw[0];
        b[--cnt[len][nw[-1]>>dt&255]]=nw[-1];
        b[--cnt[len][nw[-2]>>dt&255]]=nw[-2];
        b[--cnt[len][nw[-3]>>dt&255]]=nw[-3];
        b[--cnt[len][nw[-4]>>dt&255]]=nw[-4];
        b[--cnt[len][nw[-5]>>dt&255]]=nw[-5];
        b[--cnt[len][nw[-6]>>dt&255]]=nw[-6];
        b[--cnt[len][nw[-7]>>dt&255]]=nw[-7];
        nw-=8;
        
    }
    switch(n&7){
        case 7:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 6:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 5:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 4:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 3:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 2:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
        case 1:{b[--cnt[len][*nw>>dt&255]]=*nw;--nw;}
    }

}
}

template<typename IntType,typename Iter,bool chkmx=false> 
void radix_sort(Iter st,Iter ed) {
    typedef IntType T;
    static_assert(std::is_unsigned<T>::value&&std::is_integral<T>::value,
        "Need unsigned integer. Pleas use to_unsigned to access.");
    T rmx=std::numeric_limits<IntType>::max()>>8;
    T mx=0,*b=new T[ed-st](),v=1;
    Iter a=st;
    int tot=1;
    for(T i=1;i<rmx;i<<=8) tot++;
    if(chkmx) {for(auto nw=st;nw!=ed;nw++) if(*nw>mx) mx=*nw;}
    else mx=std::numeric_limits<IntType>::max();
    __RadixSort::n=ed-st,v=0;
    for(int len=0;len<tot;len++,v=(len<<3)) {
        memset(__RadixSort::cnt[len],0,sizeof(__RadixSort::cnt[len]));
        for(auto nw=st;nw!=ed;++nw) ++__RadixSort::cnt[len][*nw>>v&255];
    }
        
    for(int len=0;len<tot;len++) for(int i=1;i<256;++i) {
        __RadixSort::cnt[len][i]+=__RadixSort::cnt[len][i-1];
    }
    bool p=1;
    v=1;
    for(int len=0;len<tot;len++,p^=1,v<<=3) {
        if(p) __RadixSort::__radix_sort(a,b,len);
        else __RadixSort::__radix_sort(b,a,len);
        if(v>=mx) break;
    }
    if(!p) for(int i=0;i<__RadixSort::n;i++) a[i]=b[i];
    delete []b;
}

}

namespace __UNIG {

void* bs[27];

bool is_pret=false;

template<int len=1>
void get_bitset(int idx=0) {
    bs[idx]=new std::bitset<len>();
    if(MAXLEN>len) {
        get_bitset<std::min(len<<1,MAXLEN)>(idx+1);
        return;
    }
}

}

namespace UNIG {
    void pret_bitset() {__UNIG::get_bitset<1>(0); __UNIG::is_pret=true;}
}

template<typename IntType=int,
         class UniformIntDistrbution=std::uniform_int_distribution 
            <typename std::make_unsigned<IntType>::type> >
        //  class Checker=std::set<typename std::make_unsigned<IntType>::type>,
        //  bool linear=false >
class UniformNonredundantIntGenration {
    typedef IntType T;
    typedef typename std::make_unsigned<T>::type UT;
    static_assert(std::is_integral<T>::value, 
        "IntType must be a supported integer type");
    public:
        UniformNonredundantIntGenration(T mn=std::numeric_limits<T>::min(),T mx=std::numeric_limits<T>::max())
            :lwb_(to_unsigned(mn)),upb_(to_unsigned(mx)) {V=upb_-lwb_;}

        void set_bound(T mn,T mx) {lwb_=to_unsigned(mn),upb_=to_unsigned(mx),V=upb_-lwb_;}

        template<typename URNG>
        std::vector<T> operator ()(int n,URNG &gen) {
            // std::cout<<lwb_<<' '<<upb_<<'\n';
            auto x=get(n,gen);
            std::vector<T> ans(n);
            for(int i=0;i<n;i++) ans[i]=to_ori(x[i]);
            return ans;
        }
        
    private:
        UT lwb_,upb_;
        UT V;

        // template<typename URNG>
        // std::vector<T> sparse_gen(int n,URNG &gen) {
        //     UniformIntDistrbution dist(lwb_,upb_);
        //     Checker vis;
        //     std::vector<T> ans;
        //     for(int i=1;i<=n;i++) {
        //         T nw;
        //         do nw=dist(gen);
        //         while(vis.count(nw));
        //         ans.push_back(nw);
        //         vis.insert(nw);
        //     }
        //     return ans;
        // }

        template<typename URNG>
        std::vector<UT> get(int n,URNG &gen) {
            double B=2.0;
            // std::cerr<<B<<'\n';
            if((double)V+1>=B*(n-1)) {
                if(V<=MAXLEN) {
                    std::vector<UT> ret;
                    ret.reserve(n);
                    bitset_opt_sparse_gen(n,gen,ret);
                    return ret;
                }
                return sparse_gen(n,gen);
            }
            return dense_gen(n,gen);
        }

        template<typename URNG>
        std::vector<UT> sparse_gen(int n,URNG &gen) {
            UniformIntDistrbution dist(lwb_,upb_);
            // Checker vis;
            std::vector<UT> ans;
            ans.reserve(n);
            auto ansb=ans.end();
            // long long cnt=0;
            while((int)ans.size()<n) {
                while((int)ans.size()<n) ans.push_back(dist(gen));
                robin_sort(ansb,ans.end());
                std::inplace_merge(ans.begin(),ansb,ans.end());
                ans.erase(std::unique(ans.begin(),ans.end()),ans.end());
                ansb=ans.end();
                // cnt++;
                // if(cnt*n>=4e8) break;
            }
            // if((int)ans.size()!=n) {
            //     std::set<UT> vis;
            //     for(auto &i:ans) vis.insert(i);
            //     for(int i=ans.size()+1;i<=n;i++) {
            //         UT nw;
            //         do nw=dist(gen);
            //         while(vis.count(nw));
            //         vis.insert(nw);
            //         ans.push_back(nw);
            //     }
            // }
            return ans;
        }

        template<typename URNG,int len=1>
        void bitset_opt_sparse_gen(int n,URNG &gen,std::vector<UT> &ans,int idx=0) {
            if(V>len) {
                // std::cout<<len<<' '<<MAXLEN<<std::endl;
                bitset_opt_sparse_gen<URNG,std::min(MAXLEN,len<<1)>(n,gen,ans,idx+1);
                return ;
            }
            UniformIntDistrbution dist(lwb_,upb_);
            std::bitset<len> *vis=nullptr;
            if(!__UNIG::is_pret) vis=new std::bitset<len>();
            else vis=(std::bitset<len>*)__UNIG::bs[idx],vis->reset();
            for(int i=1;i<=n;i++) {
                UT nw;
                do nw=dist(gen);
                while(vis->operator[](nw-lwb_));
                ans.push_back(nw);
                vis->operator[](nw-lwb_)=1;
            }
            delete vis;
        }

        template<typename URNG>
        std::vector<UT> dense_gen(int n,URNG &gen) {
            std::vector<UT> ans;
            ans.reserve(n);
            std::vector<UT> rng((unsigned long long)V+1);
            for(UT i=lwb_;i<=upb_;i++) rng[i-lwb_]=i;
            for(int i=1;i<=n;i++) {
                UniformIntDistrbution dist(0,rng.size()-1);
                int nw=dist(gen);
                ans.push_back(rng[nw]);
                std::swap(rng[nw],rng.back());
                rng.pop_back();
            }
            return ans;
        }

        template<typename Iter>
        void robin_sort(Iter st,Iter  ed) {
            if(ed-st<=100000) std::sort(st,ed);
            else RadixSort::radix_sort<UT>(st,ed);
        }

        UT to_unsigned(T x) {
            if(std::is_same<T,UT>::value) return x;
            UT y;
            if(x<0) y=x+std::numeric_limits<T>::max()+1;
            else y=x,y+=(UT)std::numeric_limits<T>::max()+1;
            return y;
        }

        T to_ori(UT x) {
            if(std::is_same<T,UT>::value) return x;
            T y;
            if(x>(UT)std::numeric_limits<T>::max()) 
                y=x-(UT)std::numeric_limits<T>::max()-1;
            else y=x,y-=std::numeric_limits<T>::max(),y--;
            return y;
        }
};

signed main() {
    freopen("test.in","w",stdout);
    int Q=1;
    // std::cin>>Q;
    std::mt19937 gen(1993);
    UniformNonredundantIntGenration<int> UNIG;
    while(Q--) {
        int n=1e6,a=1,b=1e9;
        // std::cin>>a>>b>>n;
        UNIG.set_bound(a,b);
        auto v=UNIG(n,gen);
        std::cout<<n<<'\n';
        for(auto i:v) std::cout<<i<<' ';
        std::cout<<'\n';
        // std::cout<<"fine\n";
    }
    return 0;
}