longdie 随机数生成器
longdie
2020-12-31 14:22:53
$update$: 有人提出了质疑，说我的原理和 C++11 的是一样的，但是经过我的上网查阅，暂时发现并不相同， 而且 C++11 的原理很复杂好不好，我都看不懂。
$update$: 经过航航公主的测试，发现我的随机数是最快的，超越 C++11 一倍多。
$update$: 经过本人的测试，发现 X 的数值是可以随便选的（0显然不行），但是对于 Y 来说，它只能是个奇数， 对于 mod 来说，它并不需要是质数，只要它不是偶数就可以。
$update$: 用它试了一下 Treap ,结果没有任何问题，并且快了不少。
在今天小编考虑到 许多算法 需要随机数的帮助， 但是小编对C++自带随机数的时间效率产生了深刻的怀疑，
果然，经过了测试，发现如果产生1千万个随机数，就已经 200多ms 了， 于是小编想自己写一个随机数生成器。
首先小编写了一个只有一个数一直模一个数的随机数生成器：
```cpp
const int mod = 19260817;
int X = 133;
inline int rand() {
X = X * mod;
return abs(X);
}
```
当我以为自己已经写出来的时候，发现它不是个正确的东西，因为它并不符合随机分布（可以看情圣818的[这篇博客](https://www.cnblogs.com/rui-4825/p/13713729.html)）
然后就在网上查了一下，发现网上的随机数生成器都是 这样的：
```cpp
inline int rand() {
X = (A*X*X%C + B*X%C) % C;
return X;
}
```
这样肯定是正确的，但是我们的都知到，取模运算的时间效率很不优秀，它不能满足一亿次的随机数的产生。
于是小编乱搞了一个下面的随机数程序：
```cpp
const int mod = 19260817;
int X = 133, Y = 19;
inline int rand() {
X = X*mod;
X -= Y;
return abs(X);
}
```
本来只是抱着乱搞的心态，结果经过随机测试，它居然满足随机分布，而且分布很平均。
但是张大仙提出了质疑，认为它有循环节，经过张大仙的测试，发现它的循环节至少在 10亿次 以上，也就是说在一道题里完全不用担心。
而且它的速度很快，一千万只需要 28ms ,一亿次 只需要 500ms。
最后我用这个程序尝试了一下模拟退火，在经过几次调参后，居然过掉了这道题[[JSOI2004]平衡点 / 吊打XXX](https://www.luogu.com.cn/problem/P1337)
```cpp
#include <bits/stdc++.h>
#define down 0.995
#define Max RAND_MAX
using namespace std;
int n;
const int mod = 19260817;
int X = 133, Y = 19;
inline int rand() {
X = X*mod;
X -= Y;
return abs(X);
}
struct node { int x, y, w; } object[2005];
double ansx, ansy, answ;
double suan(double x, double y) {
double ans = 0, dx, dy;
for(int i = 1; i <= n; ++i) {
dx = x - object[i].x, dy = y - object[i].y;
ans += sqrt(dx*dx + dy*dy) * object[i].w;
}
return ans;
}
void monituihuo() {
double t = 3000;
while(t > 1e-15) {
double ex = ansx + (rand()*2 - Max)*t;
double ey = ansy + (rand()*2 - Max)*t;
double ew = suan(ex, ey);
double cha = ew - answ;
if(cha < 0) {
ansx = ex, ansy = ey, answ = ew;
}
else if(exp(-cha / t) * Max > rand()) {
ansx = ex, ansy = ey;
}
t *= down;
}
}
void solve() {//六六大顺跑六遍
monituihuo();
monituihuo();
monituihuo();
monituihuo();
monituihuo();
monituihuo();
}
int main() {
cin >> n;
for(int i = 1; i <= n; ++i) {
cin >> object[i].x >> object[i].y >> object[i].w;
ansx += object[i].x, ansy += object[i].y;
}
ansx /= n, ansy /= n, answ = suan(ansx, ansy);//初始点
solve();
printf("%.3lf %.3lf", ansx, ansy);//最终答案
return 0;
}
```
而且时间快了 0.5s 以上，这就意味着可以多跑几次模拟退火，以增加正确性。
目前在网上还没有找到类似的方法，当然也不确保这是个正确的东西，目前把它命名为 longdie 的随机数产生器。
希望各位提出质疑。
当然缺点是一旦它的三个参数固定了，它所产生的数也就固定了，但是出题人又怎么会知道你用的参数是啥呢。
而且 C++ rand()函数 当你确定随机数种子的时候，它也就固定了。
好了， 本期介绍就到这里了。
欢迎关注。