Submission #31923069

---

Source Code Expand

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

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

int n;
int a[2010];// 读入
int fa[2010]; // 并查集父节点
int sz[2010]; // 点个数
bool cir[2010]; // 是否有环

int getfa(int x){
  return x == fa[x]?x:(fa[x] = getfa(fa[x]));
}

void link(int u,int v){
  int fu = getfa(u);
  int fv = getfa(v);
  if(fu == fv){
    cir[fu] = true; // 有环
    return;
  }
  sz[fv] += sz[fu]; // 大小
  cir[fv] |= cir[fu]; // 环
  fa[fu] = fv;
}

ll mypow(ll v,int pwr){
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}
ll fac[2010] = {1}; // 阶乘

int main(){
  cin>>n;
  int freecnt = 0; // 自由度 -1 个数
  rep(i,1,n+1){
    fa[i] = i;
    sz[i] = 1;
    fac[i] = fac[i-1]*i%MOD;
    scanf("%d",a+i);
    freecnt += a[i] == -1;
  }
  rep(i,1,n+1){
    if(a[i] == -1)continue;
    link(i,a[i]);
  }
  vector<int> arr ;
  int circnt = 0;
  rep(i,1,n+1){
    if(fa[i] != i)continue; // 非联通块根
    if(cir[i]){ // 环
      circnt++;
      continue;
    }
    arr.push_back(sz[i]); // 树 有一个自由度
  }
  ll ans = circnt * mypow(n,freecnt) % MOD; // 本身就是环的贡献
  vector<ll> mulsum(n+10,0); // dp mulsum[树的个数] = sz乘积和
  mulsum[0] = 1;
  rep(i,0,(int)arr.size()){
    rep(k,0,i+1){
      // 注意前面一半只是 k+1个构成环的方案数, 对于环以外的 freecnt-k-1的自由度任意搭配 才是这些环对总答案的贡献值
      (ans += fac[k] * mulsum[k] % MOD * arr[i] % MOD * mypow(n,freecnt-k-1) % MOD)%=MOD;
    }
    per(k,0,i+1){
      (mulsum[k+1] += mulsum[k]*arr[i])%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:50:10: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d",a+i);
      |     ~~~~~^~~~~~~~~~

Judge Result