折返跑
时间限制：1 秒 空间限制：512M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！ 
题目描述
折返跑是一种跑步运动形式，运动者从一侧的杆子出发，跑向另一侧的杆子，绕过杆子跑回起点，绕过起点的杆子再跑向另一侧，不断重复这一过程。这种运动形式有助于高效利用空间，运动者可以在有限的区域内进行无限的锻炼。
了解了折返跑的运动方法后，Zaoly 不屑道："哼，杆子不动的折返跑没有灵魂，杆子不断移动的才有意思！"说干就干，他立即进行了一场移动杆折返跑运动。
上体育课了！今天的项目是折返跑，笔直的跑道可以看作是一条数轴。跑道上有
n
n
n 个位点，其中，老师在
1
1
1 点和
n
n
n 点处各放了两根杆子，称为左杆和右杆，作为折返跑的折返点。
老师规定，今天一共需要跑
m
m
m 趟。我们认为，从一根杆子开始，跑到另一根杆子结束为一趟。显然，一共需要进行
m
−
1
m – 1
m−1 次折返。Zaoly 偶然发现，杆子是可推动的，所以他有了一个大胆的想法——
- 每次跑到右杆折返后，都需要把右杆向左推动一段距离（大于
0
0
0），但仍保证右杆位于整数点，且在左杆的右边（不能与左杆重合）； - 每次跑到左杆折返后，都需要把左杆向右推动一段距离（大于
0
0
0），但仍保证左杆位于整数点，且在右杆的左边（不能与右杆重合）；
现在，给出整数
n
n
n 和
m
m
m 的值，请问 Zaoly 一共有多少种不同的推杆方法？由于答案可能很大，请将答案对
(
10
9
+
7
)
(10^9 + 7)
(109+7) 取模后输出。注意，每次折返时都需要推杆，如果某一轮无法推动，则这一轮推杆非法。
输入描述
每个测试文件均包含多组测试数据。第一行输入一个整数
T
(
1
≤
T
≤
10
4
)
T\\ (1 \\le T \\le 10^4)
T (1≤T≤104) 代表数据组数，每组测试数据描述如下：
对于每一组测试数据，输入两个整数
n
,
m
(
1
≤
m
<
n
≤
10
6
)
n, m\\ (1 \\le m < n \\le 10^6)
n,m (1≤m<n≤106) 代表位点的数量、折返跑的趟数。
输出描述
对于每组数据，在一行上输出一个整数代表合法的推杆方法种类数。由于答案可能很大，请将答案对
(
10
9
+
7
)
(10^9 + 7)
(109+7) 取模后输出。
示例 1
输入：
3
4 3
5 3
100 1
输出：
1
3
1
说明：
对于第一组测试数据，有且仅有唯一的推杆方法：
- 在第一次折返时（位于右杆），将右杆向左推一个位点；随后在第二次折返时（位于左杆），将左杆向右推一个位点；
对于第二组测试数据，有以下三种推杆方法：
- 在第一次折返时（位于右杆），将右杆向左推一个位点；随后在第二次折返时（位于左杆），将左杆向右推一个位点；
- 在第一次折返时，将右杆向左推两个位点；随后在第二次折返时，将左杆向右推一个位点；
- 在第一次折返时，将右杆向左推一个位点；随后在第二次折返时，将左杆向右推两个位点。
对于第三组测试数据，由于只跑一趟，没有折返，所以没有推杆，这也算作一种推杆方法。
数据范围与提示
-
1
≤
T
≤
10
4
1 \\le T \\le 10^4
1≤T≤104 -
1
≤
m
<
n
≤
10
6
1 \\le m < n \\le 10^6
1≤m<n≤106 - 答案对
10
9
+
7
10^9 + 7
109+7 取模 - 核心推导：
- 记第
k
k
k 次折返的推动距离为d
k
≥
1
d_k \\ge 1
dk≥1（k
=
1
,
2
,
…
,
m
−
1
k = 1, 2, \\dots, m-1
k=1,2,…,m−1）。奇数次折返发生在右杆处，使R
R
R 减小；偶数次折返发生在左杆处，使L
L
L 增大。于是R
=
n
−
(
d
1
+
d
3
+
…
)
,
L
=
1
+
(
d
2
+
d
4
+
…
)
R = n – (d_1 + d_3 + \\dots),\\qquad L = 1 + (d_2 + d_4 + \\dots)
R=n−(d1+d3+…),L=1+(d2+d4+…) - 任何时刻都要求
L
<
R
L < R
L<R，即1
+
(
d
2
+
d
4
+
…
)
<
n
−
(
d
1
+
d
3
+
…
)
⟺
∑
k
=
1
m
−
1
d
k
≤
n
−
2
1 + (d_2 + d_4 + \\dots) < n – (d_1 + d_3 + \\dots) \\iff \\sum_{k=1}^{m-1} d_k \\le n – 2
1+(d2+d4+…)<n−(d1+d3+…)⟺k=1∑m−1dk≤n−2 - 因此方案数就是「
m
−
1
m-1
m−1 个正整数之和不超过n
−
2
n-2
n−2」的解数。作代换d
k
′
=
d
k
−
1
≥
0
d_k' = d_k – 1 \\ge 0
dk′=dk−1≥0，得∑
d
k
′
≤
n
−
m
−
1
\\sum d_k' \\le n – m – 1
∑dk′≤n−m−1，其非负整数解数为(
(
n
−
m
−
1
)
+
(
m
−
1
)
m
−
1
)
=
(
n
−
2
m
−
1
)
\\binom{(n-m-1) + (m-1)}{m-1} = \\binom{n-2}{m-1}
(m−1(n−m−1)+(m−1))=(m−1n−2) - 故答案为
(
n
−
2
m
−
1
)
m
o
d
(
10
9
+
7
)
\\dbinom{n-2}{m-1} \\bmod (10^9+7)
(m−1n−2)mod(109+7)。由于n
≤
10
6
n \\le 10^6
n≤106，预处理阶乘与阶乘逆元（O
(
n
)
O(n)
O(n)），每组询问O
(
1
)
O(1)
O(1) 回答即可，总复杂度O
(
max
n
+
T
)
O(\\max n + T)
O(maxn+T)。
解题思路
本题是组合计数问题。通过分析折返跑过程中杆子的移动规律，将推杆方案数转化为正整数解的组合数问题。
1. 问题等价转化
- 跑道数轴上有左杆初始在位置
1
1
1，右杆初始在位置n
n
n。共跑m
m
m 趟，因此有m
−
1
m-1
m−1 次折返。 - 第
k
k
k 次折返时推动距离记为d
k
≥
1
d_k \\ge 1
dk≥1（整数），k
=
1
,
2
,
…
,
m
−
1
k = 1, 2, \\dots, m-1
k=1,2,…,m−1。- 奇数次折返发生在右杆处，右杆向左移动，因此右杆位置变为
n
−
(
d
1
+
d
3
+
…
)
n – (d_1 + d_3 + \\dots)
n−(d1+d3+…)。 - 偶数次折返发生在左杆处，左杆向右移动，因此左杆位置变为
1
+
(
d
2
+
d
4
+
…
)
1 + (d_2 + d_4 + \\dots)
1+(d2+d4+…)。
- 奇数次折返发生在右杆处，右杆向左移动，因此右杆位置变为
- 任意时刻必须保证左杆在右杆左边（不能重合），即：
1
+
(
d
2
+
d
4
+
…
)
<
n
−
(
d
1
+
d
3
+
…
)
1 + (d_2 + d_4 + \\dots) < n – (d_1 + d_3 + \\dots)
1+(d2+d4+…)<n−(d1+d3+…) 移项得：∑
k
=
1
m
−
1
d
k
≤
n
−
2
\\sum_{k=1}^{m-1} d_k \\le n – 2
k=1∑m−1dk≤n−2 - 因此问题转化为：求
m
−
1
m-1
m−1 个正整数d
1
,
d
2
,
…
,
d
m
−
1
d_1, d_2, \\dots, d_{m-1}
d1,d2,…,dm−1 之和不超过n
−
2
n-2
n−2 的方案数。
2. 组合数推导
- 令
d
k
′
=
d
k
−
1
≥
0
d_k' = d_k – 1 \\ge 0
dk′=dk−1≥0，则：∑
k
=
1
m
−
1
d
k
′
≤
n
−
2
−
(
m
−
1
)
=
n
−
m
−
1
\\sum_{k=1}^{m-1} d_k' \\le n – 2 – (m-1) = n – m – 1
k=1∑m−1dk′≤n−2−(m−1)=n−m−1 - 设
S
=
∑
k
=
1
m
−
1
d
k
′
S = \\sum_{k=1}^{m-1} d_k'
S=∑k=1m−1dk′，则0
≤
S
≤
n
−
m
−
1
0 \\le S \\le n – m – 1
0≤S≤n−m−1。对于固定的S
S
S，非负整数解的数量为(
S
+
(
m
−
1
)
−
1
m
−
2
)
\\binom{S + (m-1) – 1}{m-2}
(m−2S+(m−1)−1)。 - 对所有可能的
S
S
S 求和，利用组合恒等式：∑
S
=
0
n
−
m
−
1
(
S
+
m
−
2
m
−
2
)
=
(
n
−
2
m
−
1
)
\\sum_{S=0}^{n-m-1} \\binom{S + m – 2}{m – 2} = \\binom{n – 2}{m – 1}
S=0∑n−m−1(m−2S+m−2)=(m−1n−2) - 因此答案为
(
n
−
2
m
−
1
)
m
o
d
(
10
9
+
7
)
\\dbinom{n-2}{m-1} \\bmod (10^9+7)
(m−1n−2)mod(109+7)。
3. 算法实现
- 由于
n
≤
10
6
n \\le 10^6
n≤106，可以预处理阶乘f
[
i
]
f[i]
f[i] 和阶乘逆元i
n
v
f
[
i
]
invf[i]
invf[i]，以便O
(
1
)
O(1)
O(1) 计算组合数。 - 预处理：
-
f
[
0
]
=
i
n
v
f
[
0
]
=
1
f[0] = invf[0] = 1
f[0]=invf[0]=1 -
f
[
i
]
=
f
[
i
−
1
]
×
i
m
o
d
M
O
D
f[i] = f[i-1] \\times i \\bmod MOD
f[i]=f[i−1]×imodMOD - 用快速幂求
f
[
N
−
1
]
f[N-1]
f[N−1] 的逆元，然后倒推i
n
v
f
[
i
]
=
i
n
v
f
[
i
+
1
]
×
(
i
+
1
)
m
o
d
M
O
D
invf[i] = invf[i+1] \\times (i+1) \\bmod MOD
invf[i]=invf[i+1]×(i+1)modMOD
-
- 组合数计算：
C
(
a
,
b
)
=
f
[
a
]
×
i
n
v
f
[
b
]
×
i
n
v
f
[
a
−
b
]
m
o
d
M
O
D
C(a, b) = f[a] \\times invf[b] \\times invf[a-b] \\bmod MOD
C(a,b)=f[a]×invf[b]×invf[a−b]modMOD - 对于每组询问，直接输出
C
(
n
−
2
,
m
−
1
)
C(n-2, m-1)
C(n−2,m−1)。
4. 复杂度分析
- 时间复杂度：预处理
O
(
N
)
O(N)
O(N)，每组询问O
(
1
)
O(1)
O(1)。总复杂度O
(
max
n
+
T
)
O(\\max n + T)
O(maxn+T)，N
=
10
6
N = 10^6
N=106，T
≤
10
4
T \\le 10^4
T≤104，完全可行。 - 空间复杂度：需要存储阶乘和逆元数组，
O
(
N
)
O(N)
O(N)。
总结
通过分析杆子移动的约束，将推杆方案数转化为“
m
−
1
m-1
m−1 个正整数之和不超过
n
−
2
n-2
n−2”的解数，再利用组合恒等式得到答案
(
n
−
2
m
−
1
)
\\binom{n-2}{m-1}
(m−1n−2)。预处理阶乘和逆元后，每组询问可在
O
(
1
)
O(1)
O(1) 时间内回答。
代码内容
#include <bits/stdc++.h>
using namespace std;
#define endl '\\n'
typedef long long ll;
typedef unsigned long long ull;
typedef vector<vector<ll>> vvt;
typedef pair<ll,ll> pll;
const ll N=1e6+10;
const ll mod=1e9+7;
const ll inf=1e18;
ll n,m,f[N],invf[N],ans;
ll ksm(ll x,ll n)
{
ll res=1;
while(n)
{
if(n&1)res=res*x%mod;
x=x*x%mod;
n>>=1;
}
return res;
}
ll inv(ll x)
{
return ksm(x,mod–2);
}
void init()
{
f[0]=invf[0]=1;
for(ll i=1;i<N;i++)f[i]=f[i–1]*i%mod;
invf[N–1]=inv(f[N–1]);
for(ll i=N–2;i>0;i—)invf[i]=invf[i+1]*(i+1)%mod;
}
ll C(ll a,ll b)
{
return f[a]*invf[b]%mod*invf[a–b]%mod;
}
void solve()
{
cin>>n>>m;
cout<<C(n–2,m–1)<<"\\n";
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
init();
int T;
cin>>T;
while(T—)solve();
return 0;
}
![华为OD机试2025A卷-分苹果[100分]（Java_Python3_C++_C语言_JsNode）实现100%通过率-171主机测评](https://www.171host.com/wp-content/uploads/2026/10/20261026191216-6adfa61015a7f-220x80.gif)
