ZCMU - 2157: K.ly的旅行计划

题目链接：点击打开链接

题目大意：初始点为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
#include#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x3f3f3f3fusing 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/ba2[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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！