Submission #59211157

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p_ll;
#define all(vec) vec.begin(), vec.end()
#define repr(i,from,to) for (ll i=from; i<to; ++i)
#define rep(i,N) repr(i,0,N)
#define per(i,N) for(ll i=N-1; i>=0; --i)
template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }

const ll INF = (1ll<<61)-1;
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }

// --------------------------------------------
// mod
// --------------------------------------------
const ll MOD = 998244353;
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll mpow(ll n, ll p, ll m=MOD) { ll result = 1; for (ll i=1; i<=p; i=i<<1) { if (p&i) result = result*n%m; n = n*n%m; } return result; }
ll madd(ll x, ll y, ll m=MOD) { return (x+y)%m; }
ll msub(ll x, ll y, ll m=MOD) { return (x-y+m)%m; }
ll mmul(ll x, ll y, ll m=MOD) { return x*y%m; }
ll mdiv(ll x, ll y, ll m=MOD) { return mmul(x, inv(y)); }

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll nck(ll n, ll k) { return mdiv(fac[n], mmul(fac[k],fac[n-k])); }


int main() {
  c_fac();

  ll N; cin >> N;
  vector<ll> A(N); rep(i,N) cin >> A[i];
  vector<vector<ll>> from(N);
  per(i,N) from[A[i]].push_back(i+1);

  vector<vector<ll>> adj(N+1);
  rep(i,N) {
    if (from[i].size()==0) continue;

    adj[i].push_back(from[i][0]);
    rep(j,from[i].size()-1) adj[from[i][j]].push_back(from[i][j+1]);
  }
  // rep(i,N) { cout << i << ": "; debug(all(adj[i])); }

  vector<ll> size(N+1);
  auto dfs = [&] (auto dfs, ll n) -> ll {
    size[n] = 1;
    for (ll x: adj[n]) size[n] += dfs(dfs, x);
    return size[n];
  };
  dfs(dfs, 0);

  ll result = 1;
  rep(i,N+1) {
    if (adj[i].size()<=1) continue;

    ll now = size[i]-1;
    rep(j,adj[i].size()-1) {
      result = result * nck(now, size[adj[i][j]]) % MOD;
      now -= size[adj[i][j]];
    }
  }
  cout << result << endl;
  return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘ll mdiv(ll, ll, ll)’:
Main.cpp:25:24: warning: unused parameter ‘m’ [-Wunused-parameter]
   25 | ll mdiv(ll x, ll y, ll m=MOD) { return mmul(x, inv(y)); }
      |                     ~~~^~~~~
Main.cpp: In function ‘int main()’:
Main.cpp:7:42: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define repr(i,from,to) for (ll i=from; i<to; ++i)
      |                                          ^
Main.cpp:8:18: note: in expansion of macro ‘repr’
    8 | #define rep(i,N) repr(i,0,N)
      |                  ^~~~
Main.cpp:45:5: note: in expansion of macro ‘rep’
   45 |     rep(j,from[i].size()-1) adj[from[i][j]].push_back(from[i][j+1]);
      |     ^~~
Main.cpp:7:42: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    7 | #define repr(i,from,to) for (ll i=from; i<to; ++i)
      |                                          ^
Main.cpp:8:18: note: in expansion of macro ‘repr’
    8 | #define rep(i,N) repr(i,0,N)
      |                  ^~~~
Main.cpp:62:5: note: in expansion of macro ‘rep’
   62 |     rep(j,adj[i].size()-1) {
      |     ^~~

Judge Result