提出 #61439547

---

ソースコード 拡げる

// Problem: F - Count Arrays
// Contest: AtCoder - AtCoder Beginner Contest 387
// URL: https://atcoder.jp/contests/abc387/tasks/abc387_f
// 
// By Muaath Alqarni
// Blog: https://muaath.dev/blog
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;

const int N = 2027, MOD = 998244353;

ll binpow(ll h, ll y) {
	ll res = 1;
	while (y > 0) {
		if (y & 1)
		{
			res = res * h;
			if (res >= MOD)
				res %= MOD;
		}
		h = h * h;
		if (h >= MOD)
			h %= MOD;
		y >>= 1;
	}
	return res % MOD;
}

int n, m, a[N];
vector<int> adj[N], mdj[N];

ll dp[N][N];
ll pref[N];
int vis[N];

void dfs(int i) {
	for (int c : adj[i])
		dfs(c);
	
	
	for (int j = 1; j <= m; j++) {
		dp[i][j] = (j == 1 ? 1 : dp[i][j-1]);
		for (int c : adj[i]) {
			if (pref[c])
				(dp[i][j] *= binpow(pref[c], MOD-2)) %= MOD;
			(pref[c] += dp[c][j]) %= MOD;
			(dp[i][j] *= pref[c]) %= MOD;
		}
	}
}

int cyc[N];
int cmp = 0;
void visit(int x) {
	vis[x] = cmp;
	for (int c : mdj[x])
		if (!vis[c])
			visit(c);
}

ll solve_for(int x) {
	while (vis[x] != -cmp) { vis[x] = -cmp; x = a[x]; }
	int root = x;

	for (int _ = 0; _ < n; _++) {
		cyc[x] = cmp;
		x = a[x];
	}
	
	for (int i = 1; i <= n; i++) {
		if (abs(vis[i]) == cmp) {
			if (cyc[i] == cmp) continue;
			adj[cyc[a[i]] ? root : a[i]].push_back(i);
		}
	}
	dfs(root);
	ll sum = 0;
	for (int j = 1; j <= m; j++)
		(sum += dp[root][j]) %= MOD;
	return sum;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; cin >> a[i++]);
	for (int i = 1; i <= n; i++) {
		mdj[i].push_back(a[i]);
		mdj[a[i]].push_back(i);
	}
	ll sol = 1;
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			cmp = i;
			visit(i);
			cmp = i;
			(sol *= solve_for(i)) %= MOD;
		}
	}
	cout << sol;
}

提出情報

ジャッジ結果