【UESTC】1423 - Run Step（打表 & 组合）

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define LL long long
LL ans[102];
LL C[40][40];
void GetC()
{
	for (int i = 1 ; i <= 40 ; i++)
		C[i][i] = C[i][0] = 1 , C[i][1] = i;
	for (int i = 3 ; i <= 40 ; i++)
	{
		for (int j = 2 ; j < i ; j++)
			C[i][j] = C[i-1][j-1] + C[i-1][j];
	}
}
LL solve(int n)
{
	int two = n >> 1;
	if (two & 1)
		two--;
	int one = n - 2*two;
	ans[n] = 0;
	while (two >= one)
	{
		ans[n] += C[(one+two)>>1][two/2]*C[(one+two)>>1][two/2];
		two -= 2;
		one = n - 2*two;
	}
}
int main()
{
	GetC();
	for (int i = 2 ; i <= 100 ; i += 2)
		solve(i);
	int u;
	scanf ("%d",&u);
	int Case,n;
	while (u--)
	{
		scanf ("%d %d",&Case,&n);
		printf ("%d %lld\n",Case,ans[n]);
	}
	return 0;
}