GenCheck

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

const long long N = 4294967295;
const double a[] = {1.0000886, 0.4713941, 0.0001348028, -0.008553069, 0.00312558, -0.0008426812, 0.00009780499};
const double b[] = {-0.2237368, 0.02607083, 0.01128186, -0.01153761, 0.005169654, 0.00253001, -0.001450117};
const double c[] = {-0.01513904, -0.008986007, 0.02277679, -0.01323293, -0.006950356, 0.001060438, 0.001565326};

vector<int> vA;
vector<vector<int> > vB;
vector<vector<long long> > StirlingNumb;

double chiSquared(double alpha, double frdegr)
{
  double res(0);
  double d;
  if (alpha < 0.5) {
    d = -2.0637 * pow(log(1.0 / alpha) - 0.16, 0.4274) + 1.5774;
  }
  else {
    d = 2.0637 * pow(log(1.0 / (1.0 - alpha)) - 0.16, 0.4274) - 1.5774;
  }

  for (int j(0); j < 7; ++j) {
    res += pow(frdegr, (-j * 1.0) / 2.0) * pow(d, 1.0 * j) * (a[j] + b[j] / (1.0 * frdegr) + c[j] / (1.0 * frdegr * frdegr));
  }

  res = frdegr * pow(res, 3.0);
  return res;
}

int checkType(const vector<long long> &vals)
{
  map<long long, int> tp;
  for (int i(0); i < vals.size(); ++i) {
    tp[vals[i]]++;
  }

  vector<int> count(6);
  for (auto it = tp.begin(); it != tp.end(); it++) {
    count[it->second]++;
  }

  if (count[5] == 1) {
    return 0;
  }
  if (count[4] == 1) {
    return 1;
  }
  if ((count[3] == 1 && count[1] == 2) || count[2] == 2) {
    return 2;
  }
  if ((count[2] == 1 && count[1] == 3) || (count[3] == 1 && count[2] == 1)) {
    return 3;
  }
  if (count[1] == 5) {
    return 4;
  }
}

void countStirling(int d)
{
  StirlingNumb.resize(d + 1);
  for (int i(0); i <= d; ++i) {
    StirlingNumb[i].resize(d + 1);
    StirlingNumb[i][0] = 0;
    StirlingNumb[i][i] = 1;
  }

  for (int i(1); i < StirlingNumb.size(); ++i) {
    for (int j(1); j < StirlingNumb[i].size(); ++j) {
      StirlingNumb[i][j] = j * StirlingNumb[i - 1][j] + StirlingNumb[i - 1][j - 1];
    }
  }
}

int main()
{
  long long m(4294967296);
  long long a(69069);
  long long c(0);
  long long x0(1);
  long long maxX(m - 1);

  int d(5);
  vA.resize(d);

  long long n(100000);
  long long l(maxX / d);
  double p(1.0 / d);

  long long x(x0);
  for (int i(0); i < n; ++i) {
    vA[x / l]++;
    x = (a * x + c) % m;
  }

  double V(0);
  for (int i(0); i < d; ++i) {
    V += pow(vA[i] - n * p, 2.0) / (1.0 * n * p);
  }

  double chi(chiSquared(0.95, d - 1));

  if (V < chi) {
    cout << "Satisfy criterion A\n";
  }
  else {
    cout << "Don't satisfy criterion A\n";
  }
  //-----------------------------------------------------
  vB.resize(d);
  for (int i(0); i < d; ++i) {
    vB[i].resize(d);
  }

  x = x0;
  long long aa, bb;
  for (int i(0); i < n / 2; ++i) {
    aa = x / l;
    x = (a * x + c) % m;
    bb = x / l;
    vB[aa][bb]++;
  }

  p = 1.0 / (d * d);
  V = 0;
  for (int i(0); i < d; ++i) {
    for (int j(0); j < d; ++j) {
      V += pow(vB[i][j] - n / 2 * p, 2.0) / (1.0 * n / 2 * p);
    }
  }

  chi = chiSquared(0.95, d * d - 1);

  if (V < chi) {
    cout << "Satisfy criterion B\n";
  }
  else {
    cout << "Don't satisfy criterion B\n";
  }
  //------------------------------------------------------------
  x = x0;
  vector<long long> vals(5);
  vector<long long> vD(5);
  int type;
  for (int i(0); i < n / 5; i += 5) {
    for (int j(0); j < 5; ++j) {
      vals[j] = x;
      x = (a * x + c) % m;
    }
    type = checkType(vals);
    vD[type]++;
  }

  countStirling(d);
  vector<double> pr(5);
  for (int i(0); i < 5; ++i) {
    pr[i] = 1;
    int r(i + 1);
    for (int j(1); j <= r; ++j) {
      pr[i] *= (d + 1 - j);
    }
    pr[i] /= pow(d, 5);
    pr[i] *= StirlingNumb[5][r];
  }

  V = 0;
  for (int i(0); i < 5; ++i) {
    V += pow(vD[i] - 5 * pr[i], 2.0) / (5.0 * pr[i]);
  }

  chi = chiSquared(0.95, 4);

  if (V < chi) {
    cout << "Satisfy criterion D\n";
  }
  else {
    cout << "Don't satisfy criterion D\n";
  }

  return 0;
}