P14009

1.3.4 Prime Cryptarithm 牛式

难度 小学 算法入门 递归 DFS 枚举
讨论 统计 6通过 6提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

下面是一个乘法竖式:

          222
    x      22
   ----------
         444
        444
   ----------
        4884

其中每个 * 代表一个数字,这些数字必须来自给定的数字集合。
所有 * 都可以被给定集合中的数字替换,但乘法竖式的首位不能为 0(即三位乘数的百位、两位乘数的十位、以及最终结果和中间结果的最高位都不能为 0)。
给定一个数字集合(每个数字在 1~9 之间),请你计算一共有多少种不同的牛式。

注意:给定的数字可以重复使用。
两个牛式如果对应的竖式中的数字不同,则视为不同。

输入

  • 第一行包含一个整数 N ( 1 \le N \le 9 ),表示给定数字的个数。
  • 第二行包含 N 个整数,表示可用的数字(互不相同,范围 1~9),用空格隔开。

输出

输出一个整数,表示满足条件的牛式总数。

样例

样例 1
输入
5
2 3 4 6 8
输出
1

提示

其中所有出现的数字(2, 4, 8)都在给定集合内,且首位不为 0,因此总数为 1。

数据范围与约定

  • 1 \le N \le 9
  • 给定数字均为 1~9 之间的整数,互不相同。

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交