Description

Problem G - Great Numbers

In this problem you have to count the number of great numbers of length n. Here a great number must have the following property:

• the number must be divisible by all of its decimal digits.
• it does not contain any digit greater than 6 (i.e. 15 is a valid great number but 17 is not).

Input

The first line of the input file contains an integer T (T ≤ 40) which denotes the total number of test cases.The description of each test case is given below:

An integers N (1 ≤ N ≤ 40).

Output

For each case you have to output the number of great numbers in a single line. Print the output modulo 1000007.

2
1
2

6 
10

题意：求用n<=40个1-6的数字组成多少个可以整除它各个位上的数字

思路：8维DP，表示用cur个数字，数字集合是多少，还有各个数字对应的余数的情况， 最后打表输出结果

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 1000007;

int dp[42][1<<6][6][6][6][6][6][6];
int ans[43] = {0, 6, 10, 33, 120, 482, 2105, 9476, 44348, 211097, 19369, 967626, 364709, 62612, 634177, 576187, 751629, 983051, 866460, 769501, 454602, 699208, 521190, 377670, 798034, 381127, 131716, 853137, 531126, 906635, 49193, 784486, 759570, 417710, 570525, 825776, 17000, 10798, 297155, 976859, 86929};

int solve(int pos , int mask, int m1, int m2, int m3, int m4, int m5, int m6) {
	if (pos == 0) {
		if ((mask & (1<<0)) && m1) 
			return 0;
		if ((mask & (1<<1)) && m2)
			return 0;
		if ((mask & (1<<2)) && m3)
			return 0;
		if ((mask & (1<<3) ) && m4)
			return 0;
		if ((mask & (1<<4)) && m5)
			return 0;
		if ((mask & (1<<5) ) && m6) 
			return 0;
		return 1;
	}
	int &ret = dp[pos][mask][m1][m2][m3][m4][m5][m6];
	if (ret != -1)
		return ret ;
	ret = 0;
	for (int i = 1; i <= 6; i++) {
		int x1 = (m1 * 10 + i) % 1;
		int x2 = (m2 * 10 + i) % 2;
		int x3 = (m3 * 10 + i) % 3;
		int x4 = (m4 * 10 + i) % 4;
		int x5 = (m5 * 10 + i) % 5;
		int x6 = (m6 * 10 + i) % 6;
		ret += solve(pos - 1 , (mask|1<<(i-1)) , x1, x2, x3, x4, x5, x6);
		ret %= mod;
	}
	return ret;
}

int main() {
/*	for (int i = 1; i <= 40; i++) {
		memset(dp, -1, sizeof(dp));
		N = i;
		ans[i] = solve(i, 0, 0, 0, 0, 0, 0, 0);
		printf("%d, ", ans[i]);
	}
	printf("\n");
*/
	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);		
		printf("%d\n", ans[n]);
	}
	return 0;
}