• 欢迎光临~

Good Bye 2022: 2023 is NEAR

开发技术 开发技术 2022-12-31 次浏览

D. Koxia and Game

(ans=prodlimits_{i=1}^{i=n}add_i)(add_i) 就是 (i) 的贡献。
记数字 (i) 只和自己连起来称为 (i) 自环。

例如:

1 2 3
1 2 3

则称 (1,2,3) 自环。

我们先判断 (ans=0) 的情况:
(1)

1 2 1
1 3 1

多次出现 (a_i=b_i=1)

(2)

3 3 1
3 3 1

没有出现 (2)

以上两种情况可以肯定 (ans=0)

接下来考虑贡献怎么算:
(1)

1 2 3
1 2 3

显然自环贡献为 (n),此时 (ans=3times 3times 3=27)

(2)
看样例:

1 2 2
1 3 3

(1) 贡献为 (3),会发现第 (2)(3) 两个位置直接数字 (2,3) 二选一就行了。
(2,3) 两个成环,当 (i=2) 时,将 (a_2)(b_2) 双向边连起来,当 (i=3) 时,将 (a_3)(b_3) 双向边连起来,这时数字 (2)(3) 就是一个环,那么可以知道整个环贡献是 (2)
此时 (ans=2times 3=6)

(3)

4
1 3 3 4
2 3 4 4

这样 (ans=0),会发现是 (1)(2) 这条链导致的,我猜测有链就 (ans=0)
那么又发现:

3
1 2 3
1 3 3

这样 (1) 自环,(3) 自环,(2)(3) 上的链,但这样 (ans=9),那么我猜测存在孤立链就会导致 (ans=0),此时 (2) 的贡献为 (1),就是自环上有链,链的贡献为 (1)

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int M = 998244353;

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
    b[i]--;
  }
  vector<bool> vis(n);
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      if (vis[a[i]]) {
        cout << 0 << 'n';
        return;
      }
      vis[a[i]] = 1;
    }
  }
  vector<vector<int>> g(n);
  for (int i = 0; i < n; i++) {
    g[a[i]].push_back(b[i]);
    g[b[i]].push_back(a[i]);
  }
  for (int i = 0; i < n; i++) {
    if ((int) g[i].size() == 0) {
      cout << 0 << 'n';
      return;
    }
  }
  vis.assign(n, 0);
  i64 ans = 1;
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      ans = ans * n % M;
    }
  }
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    int add = 2;
    int cnt1 = 0, cnt2 = 0;
    function<void(int)> dfs = [&](int cur) {
      vis[cur] = 1;
      cnt1++;
      for (auto x : g[cur]) {
        if (cur == x) {
          add = 1;
        }
        cnt2++;
        if (!vis[x]) {
          dfs(x);
        }
      }
    };
    dfs(i);
    if (cnt1 * 2 != cnt2) {
      cout << 0 << 'n';
      return;
    }
    ans = ans * add % M;
  }
  cout << ans << 'n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tt = 1;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}
程序员灯塔
转载请注明原文链接:Good Bye 2022: 2023 is NEAR
喜欢 (0)