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

Designer 小郑

发布于 2023-07-31 15:43:43

1800

发布于 2023-07-31 15:43:43

文章被收录于专栏：跟着小郑学JAVA跟着小郑学JAVA

题目链接：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.

#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;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除

acm