2019牛客暑期多校训练营（第二场）A（随机化）

怼烎@ 2021-11-01 09:10 238阅读 0赞

# 题意： #

现在有一个长度为未知环，每次你可以向前或者向后走一步。现在有\\(T\\)个回合，每个回合给你两个整数\\(n\\)和\\(m\\)。现在问你，在第\\(i\\)个回合中，在满足第\\(i-1\\)个回合的条件的前提下，在该回合中，将长度为\\(n\\)的环上的所有的点都访问过至少一次并最终落在点\\(m\\)的可能性。

# 分析： #

对于这类询问概率的问题，我们可以采用蒙特卡洛随机的方法进行随机分析（说白了也就是随机算法）。

我们可以模拟若干次题意的操作，并求解出大概的概率，根据归纳分析，我们发现，当\\(m\\)不等于\\(0\\)的情况下，答案与\\(m\\)的值无关，只与\\(n\\)的值有关且答案为\\(\\frac\{1\}\{n-1\}\\)。因此我们只需要用快速幂求解逆元即可，**注意上一次回合的答案会累积到本回合**。时间复杂度\\(\\mathcal\{O\}(nlogn)\\)。

**需要注意的是，在\\(\\text\{windows\}\\)系统下，随机函数\\(\\text\{rand()\}\\)在数据较大的情况可能会发生比较大的误差。**

# 代码： #

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n,m; int montekalo(int n){ int cur=0,vis[10005],cnt=1; memset(vis,0,sizeof(vis)); vis[0]=1; int tmp=0; while(cnt<n){ int x=rand()%2; if(x){ cur=(cur+1)%n; } else cur=(cur-1+n)%n; if(!vis[cur]){ vis[cur]=1; cnt++; } } return cur; } void gen(int n,int m){ int cnt=0,res=0; while(cnt<=100000){ if(montekalo(n)==m) res++; cnt++; } printf("%d %d %.5f\n",res,cnt,1.0*res/cnt); } const int mod=1e9+7; ll powmod(ll x,ll n){ ll res=1; while(n){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res%mod; } int main() { int t; /* while(~scanf("%d%d",&n,&m)){ gen(n,m); }*/ scanf("%d",&t); ll res=1; while(t--){ ll n,m; scanf("%lld%lld",&n,&m); if(n==1){ printf("%lld\n",res); continue; } else if(m==0) res=0; else{ res=res*powmod(n-1,mod-2)%mod; } printf("%lld\n",res); } return 0; }

转载于:https://www.cnblogs.com/Chen-Jr/p/11219658.html