欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2019牛客暑期多校训练营(第二场)A

程序员文章站 2022-04-01 13:01:36
...

题目描述

题目大意是
    你有n个点(0~n-1),按顺序形成一个环,初始时你在0的位子,你随机顺时针走一步或者逆时针走一步,一旦你走到一个点,环上所有点都被经过至少一次后,你就必须停下来。
问你最后停留在m这个位子的概率是多少。

输入描述

输入的第一行包含一个整数T,后面的T行包含两个空格分隔的整数Ni和Mi
1T10211 \leq T \leq 1021
0M<N1090 \leq M < N \le 10^9

输出描述

输出T行每一行包含一个整数,表示前i个场景将按顺序发生的概率。您应该输出数字对109+710^9+7取模后的结果。假设概率是PQ{{P} \over {Q}},所需的输出将是P×Q1P \times Q^{-1} 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);
    }
}

总结

本题就是道概率题,考验数学推理能力。
此外涉及到的编程知识有:
快速幂
模的逆元
费马小定理