[2019牛客多校第二场][A. Eddy Walker]

题目链接：https://ac.nowcoder.com/acm/contest/882/A

题目大意：圆上有\(n\)个点，标号从\(0\)到\(n-1\)，初始一个人在点\(0\)，每次会等概率向左或向右移动一步，如果某一时刻所有点均被访问过则停止移动，问最终停留在\(m\)点的概率

题解：若\(m \neq 0\)且\(n \neq 1\)，则\(ans=\frac{1}{n-1}\)，具体证明如下

　　　若设答案为\(f(n,m)\)，可以发现这个函数有如下性质：

　　　　1.函数是关于零点对称的，即\(f(n,m)=f(n,n-m)\)

　　　　2.若\(m\neq 0,1,n-1\)，则\(f(n,m)=\frac{f(n,m-1)+f(n,m+1)}{2}\)，画一下图就能知道为什么了

　　　接着考虑\(n\)的奇偶性，若\(n\)为奇数，则设\(a=\left \lfloor \frac{n}{2} \right \rfloor,b=\left \lceil \frac{n}{2} \right \rceil,c=b+1\)。可以发现由如上两条性质，有\(f(n,a)=f(n,b)\)，且\(f(n,b)=\frac{f(n,a)+f(n,c)}{2}\)，因此可以得出\(f(n,a)=f(n,b)=f(n,c)\)。以此类推则可以得出所有\(f(n,m)\)相等，所以函数取值为\(\frac{1}{n-1}\)

　　　若\(n\)为偶数，则设\(a=\frac{n}{2}-1,b=\frac{n}{2},c=\frac{n}{2}+1\)，可以得出\(f(n,a)=f(n,c)\)，且\(f(n,b)=\frac{f(n,a)+f(n,c)}{2}\)，同样可以推出\(f(n,a)=f(n,b)=f(n,c)\)，同理可证\(f(n,m)=\frac{1}{n-1}(m\neq 0)\)

　　　注意对\(n=1\)的特判即可

 #include<bits/stdc++.h>

 using namespace std;

 #define LL long long

 #define MOD 1000000007

 LL T,n,m,ans=1ll;

 LL qow(LL x,LL y){return y?(y&?x*qow(x,y-)%MOD:qow(x*x%MOD,y/)):;}

 int main()

 {

     scanf("%lld",&T);

     while(T--)

       {

       LL res;

       scanf("%lld%lld",&n,&m);

       if(m==)res=n>?:;

       else res=qow(n-,MOD-);

       ans*=res,ans%=MOD;

       printf("%lld\n",ans);

       }

     return ;

 }

巴特西

[2019牛客多校第二场][A. Eddy Walker]

最新文章

热门文章