传送门：https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370217
题意
起点在0点，有n步，每一步有$\frac{1}{4}$往左走、$\frac{1}{4}$往右走、$\frac{1}{2}$不动。 已知终点在点m，问所有方案到达m时$\frac{P}{Q}$是多少，请对1e9+7取模。
思路
假设往左走了x步，往右走了y步，z步不动，即可得： $x、-x+y=m、x+y+z=n$，得： $x>=0$ $y=x+m\ge 0 \rightarrow x\ge -m$ $z=n-x-y\ge 0 \rightarrow x\leq \frac{n-m}{2}$
所以x的范围为$[max(-m, 0),\frac{n-m}{2}]$
$对于每一个x的贡献为C_n^x(\frac{1}{4})^x*C_{n-x}^y(\frac{1}{4})^y*\frac{1}{2}^z，变量替换一下得：$ $$ans=(\frac{1}{2})^{n+m}*\sum_{x=max(-m,0)}^{\frac{n-m}{2}}C_n^xC_{n-x}^{x+m}(\frac{1}{4})^x$$
$算之前要判断x的范围是否错误即可。$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
ll quick_pow(ll a, ll b) {
ll ans = 1;
while(b > 0) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans % mod;
}
const int N = 1e5 + 10;
ll f[N], inv[N], invF[N];
void Init() {
f[0] = f[1] = inv[0] = inv[1] = invF[0] = invF[1] = 1;
for(int i = 2;i < N; i++) {
f[i] = f[i - 1] * i % mod;
inv[i] = mod - (mod / i) * inv[mod % i] % mod;
invF[i] = invF[i - 1] * inv[i] % mod;
}
}
ll C(ll m, ll n) {
if(m < 0 n < 0 n > m)
return 0;
ll ans = f[m];
ans = ans * invF[n] % mod;
ans = ans * invF[m - n] % mod;
return ans;
}
void solve() {
Init();
int _; scanf("%d",&_);
ll inv2 = quick_pow(2, mod - 2);
ll inv4 = quick_pow(4, mod - 2);
while(_--) {
ll n, m;
scanf("%lld%lld",&n,&m);
if(abs(m) > n) {
printf("0\n");
continue;
}
ll xo = max(-m, 0ll), xn = (n - m) / 2;
ll ans = quick_pow(inv2, n + m);
ll res = 0;
for(ll i = xo;i <= xn; i++) {
res += quick_pow(inv4, i) * C(n, i) % mod * C(n - i, m + i) % mod;
res %= mod;
}
ans = ans * res % mod;
printf("%lld\n",(ans + mod) % mod);
}
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/03/01/zoj-4006/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！