[NOIP 2002 普及组] 产生数

Luogu

IDLGP1037

Time1000ms

Memory125MB

DifficultyP3

搜索图论高精度2002NOIP 普及组深度优先搜索 DFSFloyd 算法

给出一个整数 $n$ 和 $k$ 个变换规则。规则： - 一位数可变换成另一个一位数。 - 规则的右部不能为零。例如：$n=234,k=2$。有以下两个规则： - $2\longrightarrow 5$。 - $3\longrightarrow 6$。上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）: - $234$。 - $534$。 - $264$。 - $564$。共 $4$ 种不同的产生数。现在给出一个整数 $n$ 和 $k$ 个规则。求出经过任意次的变换（$0$ 次或多次），能产生出多少个不同整数。仅要求输出个数。 ## Input 第一行两个整数 $n,k$，含义如题面所示。接下来 $k$ 行，每行两个整数 $x_i,y_i$，表示每条规则。 ## Output 共一行，输出能生成的数字个数。 [samples] ## Note 对于 $100\%$ 数据，满足 $n \lt 10^{30}$，$k \le 15$。 **【题目来源】** NOIP 2002 普及组第三题

Samples

Input #1

234 2
2 5
3 6

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NOIP 2002 普及组] 产生数",
    "description": {
      "content": "给出一个整数 $n$ 和 $k$ 个变换规则。 规则： - 一位数可变换成另一个一位数。 - 规则的右部不能为零。 例如：$n=234,k=2$。有以下两个规则： - $2\\longrightarrow 5$。   - $3\\longrightarrow 6$。  上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）: - $234$。 - $534$。 - $264$。 -",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 128000
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1037"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给出一个整数 $n$ 和 $k$ 个变换规则。\n\n规则：\n- 一位数可变换成另一个一位数。\n- 规则的右部不能为零。\n\n例如：$n=234,k=2$。有以下两个规则：\n\n- $2\\longrightarrow 5$。  \n- $3\\longrightarrow 6$。 \n\n上面的整数 $234$ 经过变换后可能产生出的整数为（包括原数）:\n\n- $234$。\n- $534$。\n- $264$。\n-...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments