Submission #33643608

---

Source Code Expand

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

using mint = atcoder::modint1000000007;

typedef long long ll;
#define MOD 1000000007
#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

ll read(){ll r;scanf("%lld",&r);return r;} // read

#define INF 0x3f3f3f3f
const int N = 3000;
int p[N+10];
int q[N+10];
int e[N+10]; // 单向边
int vis2[N+10]; // 每个环的结束位置 = 1, 例如环为 2 3 5, 那么 [2]=1,[2+3=5]=1,[5+5=10]=1, 自环结束位置=2
// 0 不分配, 1 分配左点, 2分配右点
mint g[N+10][N+10][3][3]; // [i][j][s0][si] 每个环剖成链以后,长度i的链 分配了j条, 当前环 首个点state 0, 最后一个点statei
mint fac[N+10];

int main() {
  int n=read();
  fac[0]=1;
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  rep(i,0,n) p[i] = read();
  rep(i,0,n) e[p[i]] = q[i] = read(); // 建立边 p,q => e

  { // e => vis2
    vector<bool> vis(n+1,false); // 点是否被访问
    int m = 0;
    rep(i,1,n+1) if(!vis[i]){
      if(e[i]==i) { // 自环
        vis2[++m]=2;
        continue;
      }
      for(int j=i;!vis[j];j=e[j]) {
        vis[j]=1;
        m++;
      }
      vis2[m]=1;
    }
  }
  g[0][0][0][0] = 1; // 初始状态
  vis2[0] = 1;       // 初始状态
  rep(i,0,n+1) rep(j,0,i+1){ // 剖成链, 前i个边, 指定j个不合法, 第i个点所在环首个点s0,第i个点s1状态
    if(vis2[i]) { // 环结束位置
      g[i][j][1][2] = 0;
      if(vis2[i]==2) g[i][j][1][1]=0; // 自环, 不选是一种, 选左和选右相同, 去掉一个
      rep(k,0,3) rep(l,0,3) { // i+1 是新的环
        auto v = g[i][j][k][l];
        g[i+1][j  ][0][0] += v; // 新环 本身与i 无关, 应该是1,这里相当于全部乘上前面的倍数
        g[i+1][j+1][1][1] += v;
        g[i+1][j+1][2][2] += v;
      }
    } else { // 环内
      rep(k,0,3) rep(l,0,3){
        auto v = g[i][j][k][l];
        g[i+1][j  ][k][0] += v;
        g[i+1][j+1][k][1] += ((l == 2) ? 0 : v);
        g[i+1][j+1][k][2] += v;
      }
    }
  }

  mint res = 0;
  rep(i,0,n+1) {
    mint cnt = 0; // 方案数
    rep(j,0,3) rep(k,0,3) cnt += g[n][i][j][k];
    res += fac[n-i]*cnt*(i%2?-1:1); // 容斥
  }
  printf("%d",res.val());
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:13:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   13 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result