P1037 [NOIP2002 普及组] 产生数

题目描述：P1037 [NOIP2002 普及组] 产生数

---

解题思路

---

• 解题思路

  1、对于每次规则的变换 $x, y$，可以看作 $x$ 能被 $y$ 表示。对于每组样例，根据计数原理，分布乘法，因此最终答案可看作每个数字可以被表示的种类(包括自己)相乘
  2、例如给出的样例，$2$ 可以是 $\{ 2, 5 \}$ 两种，$3$ 可以是 $\{3, 6 \}$两种，因此最终答案为 $2 * 2 * 1 = 4$。但特别地，可能 $x$ 能被 $y$ 表示，而 $y$ 又可以被另外的 $z$ 表示，那么 $x$ 实际上可以被 $y$ 或 $z$ 表示，难以统计种类
  3、为了处理这样的情况，可以构建单向图：$x$ 通向 $y$，$y$ 通向所有可能的 $z$，则以 $x$ 为起点，能搜索到的数字都可以表示 $x$，即可统计种类
  4、应使用DFS搜索，要注意防止重复拓展。由于输入和最终答案的数据过大，应采用高精度的方式处理。此处答案为方便直接使用了 $128$ 位 int，应注意需要自己写输出函数，但注意只能使用 C 函数，所以不要关闭输入输出同步

---

代码实现

---

• 代码实现

  #include <bits/stdc++.h>
  using namespace std;
  
  const int N = 15;
  
  vector<int> g[N]; // 邻接表
  bitset<N> vis;    // 标记是否被拓展
  int cnt[N];       // 统计每种数字可以被表示的种类
  
  // 统计能够到达哪些点
  void DFS(int x)
  {
      vis[x] = true;
      for (auto &y : g[x])
      {
          if (!vis[y])
              DFS(y);
      }
  }
  
  // __int128 输出函数
  void output(__int128 x)
  {
      if (x >= 10)
          output(x / 10);
      putchar(x % 10 + '0');
  }
  
  void solve()
  {
      string n;
      cin >> n;
      int k;
      cin >> k;
  
      // 构建单向图
      for (int i = 1; i <= k; i++)
      {
          int x, y;
          cin >> x >> y;
          g[x].push_back(y);
      }
  
      // 统计每种数字可以被表示的种类
      for (int i = 0; i <= 9; i++)
      {
          vis.reset(); // 重置 vis
          DFS(i);
          cnt[i] = vis.count(); // 获取能被拓展的点数
      }
  
      // 128 位 int
      __int128 ans = 1;
      // 分布乘法统计答案
      for (char &i : n)
          ans *= cnt[i - '0'];
  
      output(ans);
  }
  
  int main()
  {
      int T = 1;
      // cin >> T;
      while (T--)
          solve();
      return 0;
  }

---

页底评论

---