【2019.8.7 慈溪模拟赛 T2】环上随机点（ran）（自然算法）

简单声明

我是蒟蒻不会推式子。。。

所以我用的是乱搞做法。。。

大自然的选择

这里我用的乱搞做法被闪指导赐名为“自然算法”，对于这种输入信息很少的概率题一般都很适用。

比如此题，对于一组\(n,m\)，我们可以进行\(10^6\)次随机，每次随机\(n\)个\(0\sim1\)之间的实数表示这个点在圆上的位置，然后我们暴力判断，用一个变量\(t\)记录下合法次数。

然后我们输出\(\frac t{10^6}\)就能得出大致概率了。

找规律

显然，上面这个“自然算法”精度误差较大，且我们要输出的是取模意义下的结果而非实数。

但是，该算法输出的结果，已经够我们找规律了。

首先，我们输入\(n=2,m=2,3,4,5\)可得\(1,\frac23,\frac12,\frac25\)，即\(\frac2m\)。

然后，我们输入\(n=3,m=2,3,4,5\)可得\(\frac34,\frac13,\frac3{16},\frac3{25}\)，即\(\frac 3{m^2}\)。

这时候我们似乎就可以大力猜测，答案就是\(\frac n{m^{n-1}}\)。

再代几组数据用“自然算法”验证，发现都符合这个结论，于是我们就可以姑且认为它正确了。

这样就过了。其实就是乱搞。

代码

“自然算法”：

#include<bits/stdc++.h>

#define T 1000000

#define R() 1.0*rand()/RAND_MAX//随机实数

using namespace std;

int n,m;double a[(int)1e7+5];

int main()

{

	srand(time(NULL));int t=0;scanf("%d%d",&n,&m);for(int i=1;i<=T;++i)

	{

		for(int j=1;j<=n;++j) a[j]=R();sort(a+1,a+n+1);//随机n个点

		double Mx=a[1]-a[n]+1;for(int j=1;j^n;++j) a[j+1]-a[j]>Mx&&(Mx=a[j+1]-a[j]);

		1-Mx<1.0/m&&++t;//统计合法情况数

	}return printf("%.7lf",1.0*t/T),0;

}

最终代码：

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define X 998244353

#define Qinv(x) Qpow(x,X-2)

using namespace std;

int n,m;

I int Qpow(RI x,RI y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}

int main()

{

	freopen("ran.in","r",stdin),freopen("ran.out","w",stdout);

	return scanf("%d%d",&n,&m),printf("%d",1LL*n*Qpow(Qinv(m),n-1)%X),0;//直接输出

}