#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <bitset>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define  MAX_N 18 
#define MAX_V (1<<MAX_N)
using namespace std;

int T, n, k;
char C[MAX_V];

void init()
{
				memset((char *)&C, 0, sizeof(C));

}

void printbit(bool bit[], int len)
{
				printf("printbit len = %d\n", len);
				for(int i = 0; i<len; i++)
								printf("%d", bit[i]);
				printf("\n");
}


int dfs(int nn, int kk, bool *bit, int tot)
{

				int sum  = 0, temp = 0;
				int half = tot/2 ;

				//cout<<"dfs nn = "<<nn<<",kk = "<<kk<<", tot = "<<tot<<", half = "<<half<<endl;
				//printbit(bit, tot);

				if(nn<kk)
				{
								return 0;
				}

				if(nn == 0 && kk == 0)
				{
								if(bit[0])
												return 1;
								else
												return 0;

				}


				//xn == 0;
				

				bool* bit0 = new bool[half];

				memset(bit0, 0, half);
				memcpy(bit0, bit, half);
				//printf("bit0 ");
				//printbit(bit0, half);

				temp = dfs(nn-1, kk, bit0, half );
				sum += temp;

				delete [] bit0;
				//xn == 1;
				
				if(kk>0)
				{

								bool* bit1 = new bool[half];
								memset(bit1, 0, half);
								for(int i = 0; i<half; i++)
								{
												bit1[i] = bit[i]^bit[i+half]; 
								}
				//				printf("bit1 ");
				//				printbit(bit1, half);
								temp = dfs(nn-1, kk-1, bit1, half);

								sum += temp;

								delete [] bit1;
				}
				
				return sum;

}


	
int main()
{
				int i;
				int len, ans;

				scanf("%d", &T);
	//			printf("T = %d, MAX_V = %d\n", T, MAX_V);
				while(T--)
				{

								init();
								scanf("%d %d %s", &n, &k, C);
								len = strlen(C);
							//	printf("n =  %d, k = %d, C= %s, len = %d\n", n, k, C, len);


								bool* coe = new bool[len];

								memset(coe, 0, len);

								for(i = 0; i<len; i++)
								{
												if(C[i] == '1')
												{
																coe[i] = true;
												}else
												{
																coe[i] = false;
												}

								}
								//printbit(coe, len);

			
								ans = dfs(n, k, coe, len );
								printf("%d\n", ans);

								delete[] coe;
					}

}

几经波折。做了5,6个版本总算不timeout了。。。。还有我用c++提交wa。g++ok了。不过本机上也是用g++提交的。。。