题目链接：Vjudge 传送门

相当于把nnn个点分隔为若干块，求所有方案中大小为kkk的块数量

我们把大小为kkk的块，即使在同一种分隔方案中的块

单独考虑，它可能出现的位置是在nnn个点的首、尾、中

• 出现在首尾时，有222种情况，此时剩下的点有(n−k−1)(n-k-1)(n−k−1)个间隔，每个间隔可分可不分，所以方案数为2⋅2(n−k−1)2\cdot 2^{(n-k-1)}2⋅2(n−k−1)
• 出现在中间时，有(n−k−1)(n-k-1)(n−k−1)种情况，此时剩下的点有(n−k−2)(n-k-2)(n−k−2)个间隔，每个间隔可分可不分，所以方案数为(n−k−1)⋅2(n−k−2)(n-k-1)\cdot 2^{(n-k-2)}(n−k−1)⋅2(n−k−2)

加起来即为(n−k+1)⋅2(n−k−2)(n-k+1)\cdot2^{(n-k-2)}(n−k+1)⋅2(n−k−2)

注意此处要特判3种情况

(1)n<k

(2)n=k

(3)n-k-2=-1

n−k−2n-k-2n−k−2若更小，如为−2-2−2,则nnn已经等于kkk了

AC code

#include <cstdio>

typedef long long LL;

const int mod = 1e9 + 7;

inline int qmul(int a, int b)

{

	int ret = 1;

	while(b)

	{

		if(b & 1) ret = (LL)ret * a % mod;

		a = (LL)a * a % mod; b >>= 1;

	}

	return ret;

}

int main ()

{

	int T, n, k;

	scanf("%d", &T);

	while(T--)

	{

		scanf("%d%d", &n, &k);

		if(n < k) puts("0");

		else if(n == k) puts("1");

		else if(n == k+1) puts("2");

		else

		{

			printf("%lld\n", (LL)(n-k+3) * qmul(2, n-k-2) % mod);

		}

	}

}