2

#include <time.h>
#include <iostream>
#include <functional>
#include <random>
#include <ctime>
#include <map>
#include <ratio>
#include <chrono>
using namespace std;
using namespace std::chrono;
int main()
{
    map<long long int, int> map0;   //儲存各種排列出現的次數
    random_device rd;       //設定PRNG
    auto tt = chrono::high_resolution_clock::now();     //亂數種子為當下時間
    std::mt19937_64 gen = std::mt19937_64(tt.time_since_epoch().count());       //以梅森旋轉作為PRNG
    std::uniform_int_distribution<> dis(0, 1);  //數值範圍限定為0或1
    auto Rand = bind(dis, gen);
    int N = 1;
    while (N < 50000) {     //創造一個夠大但隨機的N，為了程式碼乾淨使用不再多寫一個PRNG
        if (Rand())
            N = N * 2 + 1;
        else
            N *= 2;
    }
    int T = N, n, location[1000];
    cout << "將會執行" << T << "次" << endl;
    cin >> n;       //輸入人數

    while (T--)
    {
        for (int i = 0; i < n; i++)
            location[i] = i + 1;
        for (int i = 0; i < n; i++)
            for (int j = i+1; j < n; j++)
                if (Rand())
                    swap(location[i], location[j]);

        long long int number = 0;       //把排列轉換成數字方便儲存
        for (int i = 0; i < n; i++)
            number = number * n + location[i];
        map0[number]++;
    }

    long long int max0 = 0, min0 = N, size0 = 1;    //極大極小
    long double S = 0;  //標準差
    for (int i = 1; i <= n; i++)
        size0 *= n;
    for (auto iter = map0.begin(); iter != map0.end(); iter++) {
        max0 = max(max0, (long long int)iter->second);
        min0 = min(min0, (long long int)iter->second);
        S += pow((iter->second - (double)N / size0), 2);
    }
    S /= size0;
    S = sqrt(S);
    cout << max0 << " " << min0 << endl;
    cout << S << endl;

    return 0;
}