2019牛客暑期多校训练营(第二场)A
程序员文章站
2022-04-01 13:01:36
...
题目描述
题目大意是
你有n个点(0~n-1),按顺序形成一个环,初始时你在0的位子,你随机顺时针走一步或者逆时针走一步,一旦你走到一个点,环上所有点都被经过至少一次后,你就必须停下来。
问你最后停留在m这个位子的概率是多少。
输入描述
输入的第一行包含一个整数T,后面的T行包含两个空格分隔的整数Ni和Mi
输出描述
输出T行每一行包含一个整数,表示前i个场景将按顺序发生的概率。您应该输出数字对取模后的结果。假设概率是,所需的输出将是 mod 109+7
输入样例
3
1 0
2 1
3 0
输出样例
1
1
0
solution
- 如果n=1, 那么其落到0的概率是1(一开始就落到0了)。如果n>1,你会很容易发现终点落到1~n-1的概率是相同的,因为他们的地位相同,而落到0的概率是0,因为它是起点。
- 除了推论,这题还有一个做法就是打表,随机数模拟题意中的过程,也能得到结果。
打表代码
#include<bits/stdc++.h>
using namespace std;
int t,now,n,x;
int vis[105],book[105];
int main(){
cin>>n;
srand((unsigned int)(time(NULL)));
for(int i=1;i<=1e5;i++){
memset(vis,0,sizeof(vis));
vis[0] = 1;
now = 0;
t = 1;//表示已访问点的数量
while(t<n){
x=rand()%2?1:-1;
now+=x;
now=(now+n)% n;
if(!vis[now]){
vis[now]=1;
t++;
}
if(t==n)
book[now]++;
}
}
for(int i=0;i<n;i++)
cout<<book[i]<<' ';
cout<<endl;
}
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3fffffff
#define maxn 100005
#define mod 1000000007
ll poww(ll a,ll b){
ll res=1;
while(b){
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
int n,m,k,t;
int main(){
scanf("%d",&t);
ll ans=1;
while(t--){
scanf("%d%d",&n,&m);
ll res;
if(n==1)res=1;
else{
if(m==0)
res=0;
else res=poww(n-1,mod-2);
}
ans=(ans*res)%mod;//结果是一个前缀积
printf("%lld\n",ans);
}
}
总结
本题就是道概率题,考验数学推理能力。
此外涉及到的编程知识有:
快速幂
模的逆元
费马小定理
上一篇: php中foreach结合curl实现多线程的方法实例分析
下一篇: php生成验证码文件的方法
推荐阅读
-
2019牛客暑期多校训练营(第二场)H Second Large Rectangle
-
2020牛客暑期多校训练营(第四场)——Basic Gcd Problem
-
2020牛客暑期多校训练营(第五场)
-
2020牛客暑期多校训练营(第九场) The Flee Plan of Groundhog
-
2020牛客暑期多校训练营Groundhog and Apple Tree(树形dp,贪心)
-
2020暑期牛客多校训练营第九场(K)The Flee Plan of Groundhog(lca,树形dp)
-
2020牛客暑期多校训练营(第二场)Cover the Tree
-
2020牛客暑期多校训练营(第一场)H-Minimum-cost Flow
-
2020牛客暑期多校 第一场 F Infinite String Comparision(字符串)
-
Harmony Pairs 2020牛客暑期多校训练营(第六场)