範例程式碼 uva11472

//uva11472
#include <algorithm>
#include <iostream>
#include <cstring>

using namespace std;

int dp[101][11][1025];

int main() {
	int t, n, m;
	while (cin >> t)
	while (t--) {
		cin >> n >> m;
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i < n; ++i)
			dp[0][i][1 << i] = 1;
		int u = 1 << n, b1, b2;
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				for (int k = 1; k < u; ++k) {
					b1 = k | (1 << (j - 1));
					if (j > 0)
						dp[i + 1][j - 1][b1] = (dp[i + 1][j - 1][b1] + dp[i][j][k]) % 1000000007;
					b2 = k | (1 << (j + 1));
					if (j < n - 1)
						dp[i + 1][j + 1][b2] = (dp[i + 1][j + 1][b2] + dp[i][j][k]) % 1000000007;
				}
			}
		}
		
		int sum = 0;
		for (int i = 0; i < m; ++i)
			for (int j = 0; j < n; ++j)
				sum = (sum + dp[i][j][u - 1]) % 1000000007;

		cout << sum << endl;
	}
	return 0;
}