这题感觉主要难点有两个，一个是用拓扑排序去把环剥离出来（应该也能用 dfs 去跑一下，如果一个点你第二次遇见，说明成环了），一个是环的染色数量统计，看了眼其他题解里没有环染色数量公式的推导来着，蒟蒻的我就发个完整证明好了：
考虑环染色本身是不大可做的，所以我们考虑从链去推。
假设有一条 个结点的链，有
种颜色。
记 为这条链的染色方案数。
考虑分两种情况讨论：
-
首尾不同，方案数记作
，此时首尾相连可直接成环，是我们要求的东西；
-
首尾相同，方案数记作
，由结点
与结点
颜色相同，结点
与 结点
可得，结点
故若去掉最后一个结点
可得
考虑特例。
考虑 即为
，所以
那么:
注意到， 为等比数列求和。
故 为奇数时，
为偶数时，
贴个参考代码：（其实还是写复杂了，树的部分其实不用考虑来着，处理完环以后先得到 ，考虑
减去环的大小总和以后,剩下的值假设是
,那么
再乘以
的
次方应该就可以得到最终答案了）
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
// const ll MOD = 1e9 + 7;
const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, x, y, z, len, t, l, r, cur, cnt = 0;
string s1, s2;
cin >> n;
vector<ll> a(n), to(n), deg(n), sz(n, 1);
for (ll i = 0; i < n; i++)
{
cin >> x;
x--;
to[i] = x;
deg[x]++;
}
queue<ll> q;
for (ll i = 0; i < n; i++)
{
if (deg[i] == 0)
q.push(i);
}
vector<bool> c(n, 1);
while (!q.empty())
{
ll u = q.front();
q.pop();
c[u] = 0;
ll v = to[u];
sz[v] += sz[u];
deg[v]--;
if (deg[v] == 0)
q.push(v);
}
vector<ll> pow25(n + 1);
pow25[0] = 1;
for (ll i = 1; i <= n; i++)
pow25[i] = pow25[i - 1] * 25 % MOD;
vector<bool> vis(n);
ans = 1;
for (ll i = 0; i < n; i++)
{
if (c[i] && !vis[i])
{
vector<ll> cycle;
cur = i;
while (!vis[cur])
{
vis[cur] = 1;
cycle.push_back(cur);
cur = to[cur];
}
num = cycle.size();
x = 1;
for (auto e : cycle)
x = x * pow25[sz[e] - 1] % MOD;
y = (pow25[num] + ((num & 1) ? MOD - 25 : 25)) % MOD;
ans = ans * x % MOD * y % MOD;
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
//cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
京公网安备 11010502036488号