［DP］ HDOJ 5456 Matches Puzzle Game

#include 
using namespace std;
typedef long long LL;

LL dp[505][2][2][2];
int cnt[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int mod;

void add(LL& a, LL b)
{
	a += b;
	if(a > mod) a -= mod;
}

LL dfs(int n, int carry, int is_b, int is_c)
{
	if(n == 0) {
		if(is_b && is_c && !carry) return true;
		else return false;
	}
	if(dp[n][carry][is_b][is_c] != -1) return dp[n][carry][is_b][is_c];
	dp[n][carry][is_b][is_c] = 0;
	LL &ans = dp[n][carry][is_b][is_c];
	
	if(is_b) {
		if(is_c) {
			if(carry && n == 2) add(ans, 1);
			else ans = 0;
		}
		else {
			for(int c = 0; c = 10) a -= 10, n_carry = 1;
				int t = n - cnt[c] - cnt[a];
				if(t >= 0) {
					add(ans, dfs(t, n_carry, 1, 0));
					if(c) add(ans, dfs(t, n_carry, 1, 1));
				}				
			}
		}
	}
	else {
		if(is_c) {
			for(int b = 0; b = 10) a -= 10, n_carry = 1;
				int t = n - cnt[b] - cnt[a];
				if(t >= 0) {
					add(ans, dfs(t, n_carry, 0, 1));
					if(b) add(ans, dfs(t, n_carry, 1, 1));
				}
			}
		}
		else {
			for(int b = 0; b = 10) a -= 10, n_carry = 1;
					int t = n - cnt[a] - cnt[b] - cnt[c];
					if(t >= 0) {
						add(ans, dfs(t, n_carry, 0, 0));
						if(b) add(ans, dfs(t, n_carry, 1, 0));
						if(c) add(ans, dfs(t, n_carry, 0, 1));
						if(b && c) add(ans, dfs(t, n_carry, 1, 1));
					}
				}
			}
		}
	}
	return ans;
}

void work()
{
	int n;
	memset(dp, -1, sizeof dp);
	scanf("%d%d", &n, &mod);
	printf("%lldn", dfs(n-3, 0, 0, 0));
}

int main()
{
	//freopen("data", "r", stdin);
	int _;
	scanf("%d", &_);
	for(int i = 1; i