题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4006
题意：小明在原点（0，0），一共可以走n步，他朋友在（m,0）这个点。小明是随机走步，1/2几率不动，1/4几率往左走一步，1/4几率往右走一步。
问：小明走n次以后在（m,0）这个点的概率的逆元为多少？ 结果对1e9+7取余，n、m∈[0,1e5]；
PS：P/Q%mod=P*（Q的逆元）%mod。
题解：
什么叫逆元，见下图：需要P为质数，题中1e9+7就是质数符合题意。
我们令i为小明原地不动的步数，但是前提是保证n-i>=m，因为m是有效步数。
首先，总步数是n，i是不动的步数，m是有效的动步数，那么我们设无效的动步数（即来回循环但位移是0的步数）为X。
则 i+m+X=n；
解得X=n-m-i；
这里是组合公式的运用。
在i确定的情况下，
我们先把i步不动的确定下来，就是C(n，i)。
不动的概率是0.5，所以总的是1/2）^i
在动的步数中，分为有效和无效步，如下图所示，我们只需要确定无效步的一种即可，
比如确定无效步的左边，就是c(n-i，n-m-i>>1)
总的动步为n-i，所以总的概率为(1/4)^(n-i)；
在i确定的情况下，答案就是C(n，i)*（1/2）^i *c(n-i，n-m-i>>1)*(1/4)^(n-i)；
所以最后i从0或1 遍历到n-m即可，步长为2.
1. #include<iostream> 2. using namespace std; 3. 4. #define ll long long 5. const ll mod = 1e9 + 7; 6. ll jc[100005]; 7. void init() 8. { 9. jc[0] = 1; 10. ll ret = 1; 11. for (ll i = 1; i <= 100000; i++) 12. { 13. ret = (ret*i) % mod; 14. jc[i] = ret; 15. } 16. } 17. ll qpow(ll a, ll b) 18. { 19. ll ret = a; 20. ll ans = 1; 21. while (b) 22. { 23. if (b & 1) 24. ans = (ans*ret) % mod; 25. ret = (ret*ret) % mod; 26. b >>= 1; 27. } 28. return ans; 29. } 30. ll c(ll a, ll b) 31. { 32. return jc[a] * qpow(jc[b] * jc[a - b] % mod, mod - 2) % mod; 33. } 34. int main() 35. { 36. int t; 37. scanf("%d", &t); 38. init(); 39. while (t--) 40. { 41. ll n, m, i; 42. scanf("%lld%lld", &n, &m); 43. if (m<0) m = -m; 44. int maxn=n-m; 45. ll ans = 0; 46. if (maxn % 2 == 1) i = 1; 47. else i = 0; 48. for (; i <= maxn; i += 2) 49. { 50. ans = (ans + c(n, i)*c(n - i, n-m-i>>1) % mod*qpow(qpow(4, n-i)*qpow(2, i) % mod, mod - 2) % mod) % mod; 51. } 52. printf("%lld\n", ans); 53. } 54. return 0; 55. }
