卢俊达

题目大意：

题目给出一个由“*”构成的乘法式子。已知一个范围为[0,9]的整数集合，用集合中的数字替换“*”可能使式子成立，要求编程求出使式子成立的方案的数量。

思路：

用深搜遍历所有可能方案即可，具体思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: crypt1
*/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdio>
#include<stdlib.h>
using namespace std;
//num[]用于存储两个乘数，例如123*45，那么num[]={1,2,3,4,5}。 
int num[5];
//mark[]用于判断某数字是否属于所给集合。 
bool mark[10];
//输入 
void input()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<10;i++)
		mark[i]=false;
	for(int i=0,temp;i<n;i++)
	{
		scanf("%d",&temp);
		mark[temp]=true;
	}
}
//判断整数n的各位数字是否都属于集合 
int check_num(int n)
{
	//length用于记录整数n的长度。 
	int length=0;
	for(;n;n/=10,length++)
		//若某位数字不属于集合，则返回-1。 
		if(!mark[n%10])
			return -1;
	//若整数n的各位数字都属于集合，则返回其长度。
	//返回长度是因为题目所给乘法式子对不同位置的整数有格式（长度）限制，要判断整数n是否符合格式。 
	return length;
}
//判断当前num[]所表示的乘数组合是否符合乘法式子与格式的要求。 
bool check()
{
	//a是被乘数，b是乘数，d是乘数的个位，c是乘数的十位。 
	int a=num[0]*100+num[1]*10+num[2],b=num[3]*10+num[4],c=num[4],d=num[3];
	//a*c和a*d分别是乘法式子第4行和第3行上的整数。它们的长度为3。 
	//a*b是结果，长度应该为4。 
	if(check_num(a*c)==3&&check_num(a*d)==3&&check_num(a*b)==4)
		return true;
	return false;
}
//利用深搜，遍历所有可能的乘数组合。
//order表示num[]中的第order位，从0开始。 
int dfs(int order)
{
	if(order==5)
		return check()?1:0;
	int sum=0;
	for(int i=0;i<10;i++)
		if(mark[i])
		{
			//不能有前导0 
			if((order==0||order==3)&&i==0)
				continue;
			num[order]=i;
			sum+=dfs(order+1);
		}
	return sum;
}
int main()
{
	freopen("crypt1.in","r",stdin);
	freopen("crypt1.out","w",stdout);
	input();
	printf("%d\n",dfs(0));
}