题目链接：点击打开链接
题目大意：初始点为0，目标点为m（可能是负数），对于一步有：1/4的概率-1，1/4的概率+1，1/2的概率不变，求走n步，从0到m的概率是多少，假设答案为a/b，以a*b的乘法逆元形式输出。
解题思路：
设x，y，z分别为+1的步数，-1的步数，0的步数；则：
x*1+y*(-1)+z*0 = x-y = m
x+y+z = n
==>
x=m+y
z=n-m-y-y
假设到达目标点包含以下操作(m+i)步+1(向右)，(i)步-1(向左)，(n-m-i-i)步0(不变)。（i-->从 0 到 m+i+i<=n)
于是可得：
（1）分母部分为：pow(2,n-m-i-i)*pow(4,m+i+i)。
（2）分子部分为（分子部分是一个组合数）：C(n,m+i)*C(n-m-i,i)，因为总共包含三种操作固定两种自然确定最后一种，这个表达式是确定了+1的组合情况和-1的组合情况。
最后，不断求解累加即是答案。因为题目涉及一些乘分母，阶乘，组合数等东西，所以需要一些预处理，以及乘法逆元化。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define INF 0x3f3f3f3f using namespace std; typedef long long ll; const ll mod=1e9+7; const int maxn=100000+10; // 快速模幂（配合：费马小定理） ll qpow(ll a,ll b) { ll ans=1; a=a%mod; while(b) { if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } // 扩展欧几里德 void extgcd(ll a,ll b,ll& d,ll& x,ll& y){ if(!b){ d=a; x=1; y=0;} else{ extgcd(b,a%b,d,y,x); y-=x*(a/b); } } ll inverse(ll a,ll n){ ll d,x,y; extgcd(a,n,d,x,y); return d==1?(x+n)%n:-1; } ll a1[maxn],b1[maxn],c1[maxn]; // 1/4 1/2 i! ll a2[maxn],b2[maxn],c2[maxn]; // 同上对应的逆元数组 int main() { a1[0]=a2[0]=b1[0]=b2[0]=c1[0]=c2[0]=1; for(int i=1;i<=100000;i++) { a1[i]=(a1[i-1]*4)%mod; b1[i]=(b1[i-1]*2)%mod; c1[i]=(c1[i-1]*i)%mod; // 费马小定理+快速幂（O(log2N)）（mod 为素数 + mod较大时推荐）：用 b^(M-2) 代替 1/b a2[i]=qpow(a1[i],mod-2); b2[i]=qpow(b1[i],mod-2); c2[i]=qpow(c1[i],mod-2); // 扩展欧几里德（O(lnN)）（GCD是否为1，1存在逆元，非1不存在逆元） // a2[i]=inverse(a1[i],mod); // b2[i]=inverse(b1[i],mod); // c2[i]=inverse(c1[i],mod); } int T; scanf("%d",&T); ll n,m; while(T-- && ~scanf("%lld%lld",&n,&m)) { if(m<0) m=-m; // m，-m 结果等价 ll rs=0,ans=0; // C(n-m-i,i) * C(n,m+i) ==> (n-m-i)!/(i!*(n-m-i-i)!) * n!/((m+i)!*(n-m-i)!) ==> n!/(i!*(n-m-i-i)!*(m+i)!) for(int i=0;m+i+i<=n;i++) rs=(rs+c1[n]*c2[m+i]%mod*c2[i]%mod*c2[n-m-i-i]%mod*a2[m+i+i]%mod*b2[n-m-i-i]%mod)%mod; printf("%lld\n",rs); } return 0; }
