队友推出了一个状态转移方程，最后弄了俩小时还没算对，后来来看，各种方法， 暴力还没看懂，看懂了就补。 网上看到隔板法，特别6 对于1 <= k < n，我们可以等效为n个点排成一列，并取出其中的连续k个，这连续的看K个两端断开；
1、若取得是这K个点包括端点（我们只考虑一个端点的情况），还剩下（n-k-1）个间隔，
每个间隔有断开和闭合两种状态，故有2^（n-k-1），最后乘以2；
2、若取得是这K个点不包括端点，这连续的K个点有（n-k-1）种取法，还剩下（n-k-2）个间隔，
故有2^（n-k-2）*（n-k-1）；
总计2 ∗ 2^(n – k − 1) + 2^(n – k − 2) ∗ (n – k − 1) = (n – k + 3) * 2^(n – k − 2)。 /* * Author: Gatevin * Created Time: 2015/7/15 14:52:46 * File Name: HDU4602.cpp */
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cctype> #include<cmath> #include<ctime> #include<iomanip> using namespace std; const double eps(1e-8); typedef long long lint; const lint mod = 1e9 + 7; lint quick(lint base, int pow) { lint ret = 1; while(pow) { if(pow & 1) ret = ret*base % mod; pow >>= 1; base = base*base % mod; } return ret; } int main() { int T; scanf("%d", &T); while(T--) { int n, k; scanf("%d %d", &n, &k); if(n < k) { puts("0"); continue; } if(n == k) { puts("1"); continue; } if(n == k + 1) { puts("2"); continue; } lint tmp = quick(2LL, n - k - 2); lint ans = (tmp*4LL + (n - k - 1)*tmp) % mod; printf("%I64d\n", ans); } return 0; }