ACM刷题之路（十四）逆元取模 Travel along the Line

亦凉 2024-02-19 13:31 14阅读 0赞

**题目链接**：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4006][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就是质数符合题意。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDY0MTIz_size_16_color_FFFFFF_t_70][]

**我们令i为小明原地不动的步数，但是前提是保证n-i>=m，因为m是有效步数。**

**首先，总步数是n，i是不动的步数，m是有效的动步数，那么我们设无效的动步数（即来回循环但位移是0的步数）为X。**

**则 i+m+X=n；**

**解得X=n-m-i；**

**这里是组合公式的运用。**

![20181118174607410.png][]

**在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)；**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDY0MTIz_size_16_color_FFFFFF_t_70 1][]

**所以最后i从0或1 遍历到n-m即可，步长为2.**

#include<iostream>
    using namespace std;
    
    #define ll long long
    const ll mod = 1e9 + 7;
    ll jc[100005];
    void init()
    {
    	jc[0] = 1;
    	ll ret = 1;
    	for (ll i = 1; i <= 100000; i++)
    	{
    		ret = (ret*i) % mod;
    		jc[i] = ret;
    	}
    }
    ll qpow(ll a, ll b)
    {
    	ll ret = a;
    	ll ans = 1;
    	while (b)
    	{
    		if (b & 1)
    			ans = (ans*ret) % mod;
    		ret = (ret*ret) % mod;
    		b >>= 1;
    	}
    	return ans;
    }
    ll c(ll a, ll b)
    {
    	return jc[a] * qpow(jc[b] * jc[a - b] % mod, mod - 2) % mod;
    }
    int main()
    {
    	int t;
    	scanf("%d", &t);
    	init();
    	while (t--)
    	{
    		ll n, m, i;
    		scanf("%lld%lld", &n, &m);
    		if (m<0)	m = -m;
                    int maxn=n-m;
    		ll ans = 0;
    		if (maxn % 2 == 1) i = 1;
    		else i = 0;
    		for (; i <= maxn; i += 2)
    		{
    			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;
    		}
    		printf("%lld\n", ans);
    	}
    	return 0;
    }

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_4006]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4006
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDY0MTIz_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0e09a0050dce46299f3f33399b98bab9.png
[20181118174607410.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c9b75c3f1d954a3e8333cd8eb83a0c5b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDY0MTIz_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/d7657672233a4d80b00e22a3311449ea.png