#P1149. [NOIP2008 提高组] 火柴棒等式

[NOIP2008 提高组] 火柴棒等式

题目描述

给你 nn 根火柴棍,你可以拼出多少个形如 A+B=CA+B=C 的等式?等式中的 AABBCC 是用火柴棍拼出的整数(若该数非零,则最高位不能是 00)。用火柴棍拼数字 090\sim9 的拼法如图所示:

注意:

  1. 加号与等号各自需要两根火柴棍;
  2. 如果 ABA\neq B,则 A+B=CA+B=CB+A=CB+A=C 视为不同的等式(A,B,C0A,B,C\geq0);
  3. nn 根火柴棍必须全部用上。

输入格式

一个整数 n(1n24)n(1 \leq n\leq 24)

输出格式

一个整数,能拼成的不同等式的数目。

14
2
18
9

提示

【输入输出样例 1 解释】

22 个等式为 0+1=10+1=11+0=11+0=1

【输入输出样例 2 解释】

99 个等式为

0+4=40+4=40+11=110+11=111+10=111+10=112+2=42+2=42+7=92+7=94+0=44+0=47+2=97+2=910+1=1110+1=1111+0=1111+0=11