j.cpp

ACM大赛基本练习题

#include <stdio.h>

#define BASE 10000
#define MAXN 10000

int num[MAXN][2];
int q1, n, qn;

void make_it()
{
	int i;

	num[0][0] = num[0][1] = 0;

	if( q1 )
		num[0][1] = 1;
	else
		num[0][0] = 1;

	for( i = 1; i < n; ++i )
	{
		num[i][0] = ( 2 * num[i - 1][0] + num[i - 1][1] ) % BASE;
		num[i][1] = ( 2 * num[i - 1][1] + num[i - 1][0] ) % BASE;
	}

	printf( "%d\n", num[n - 1][qn] );
}

int main()
{
	int i, testCase;

	scanf( "%d", &testCase );

	for( i = 0; i < testCase; ++i )
	{
		scanf( "%d %d %d", &q1, &n, &qn );
		make_it();
	}

	return 0;
}