ABC134 F. Permutation Oddness

F - Permutation Oddness

Any permutation can be represented as a permutation. For example, [0,8,3,6,9,7,2,5,1,4] can be drawn as the following graph.

f:id:pekempey:20190725173743p:plain

The oddness is the sum of the number of edges across over the lines. Let us consider doing DP. Partial solution is like this.

f:id:pekempey:20190725175141p:plain

There are five transitions.

f:id:pekempey:20190725175633p:plain

#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)

using namespace std;
using ll = long long;

const int MOD = 1000000007;

class mint {
  int n;
public:
  mint(int n_ = 0) : n(n_) {}
  friend mint operator-(mint a) { return -a.n + MOD * (a.n != 0); }
  friend mint operator+(mint a, mint b) { int x = a.n + b.n; return x - (x >= MOD) * MOD; }
  friend mint operator-(mint a, mint b) { int x = a.n - b.n; return x + (x < 0) * MOD; }
  friend mint operator*(mint a, mint b) { return (long long)a.n * b.n % MOD; }
  friend mint &operator+=(mint &a, mint b) { return a = a + b; }
  friend mint &operator-=(mint &a, mint b) { return a = a - b; }
  friend mint &operator*=(mint &a, mint b) { return a = a * b; }
  friend bool operator==(mint a, mint b) { return a.n == b.n; }
  friend bool operator!=(mint a, mint b) { return a.n != b.n; }
  friend istream &operator>>(istream &i, mint &a) { return i >> a.n; }
  friend ostream &operator<<(ostream &o, mint a) { return o << a.n; }
};

mint dp[55][55][2800];

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int N, K; cin >> N >> K;
  dp[0][0][0] = 1;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= N; j++) {
      for (int k = 0; k <= K; k++) {
        if (dp[i][j][k] == 0) continue;
        dp[i+1][j][k+j*2] += dp[i][j][k];
        if (j>0) dp[i+1][j-1][k+(j-1)*2] += j*j*dp[i][j][k];
        dp[i+1][j][k+j*2] += j*dp[i][j][k];
        dp[i+1][j][k+j*2] += j*dp[i][j][k];
        dp[i+1][j+1][k+(j+1)*2] += dp[i][j][k];
      }
    }
  }
  cout << dp[N][0][K] << endl;
}
\documentclass[dvipdfmx,margin=2mm]{standalone}
\usepackage{tikz}
\usepackage{amssymb}
\begin{document}
\begin{tikzpicture}[
    foo/.style={circle,draw}
  ]
  \foreach \i in {0,...,9}{
    \node[foo](\i) at (\i,0) {\i};
  };
  %[0, 8, 3, 6, 9, 7, 2, 5, 1, 4]
  \draw[-latex,loop above] (0) to (0);
  \foreach \i/\j in {1/8, 2/3, 5/7, 3/6, 4/9}{
    \draw[-latex] (\i.north) to[bend left] (\j.north);
  };
  \foreach \i/\j in {6/2, 7/5, 8/1, 9/4}{
    \draw[-latex] (\i.south) to[bend left] (\j.south);
  };

  \foreach \i/\j in {0/0, 1/2, 2/4, 3/4, 4/6, 5/8, 6/6, 7/4, 8/2}{
    \draw[dashed] (\i+0.5,-1.5) -- (\i+0.5,2);
    \node at (\i+0.5,-1.8) {\j};
  }
  \foreach \i in {0,...,7}{
    \node at (\i+1,-1.8) {$+$};
  }
  \node at (9,-1.8) {$=$};
  \node at (9.5,-1.8) {36};
\end{tikzpicture}
\end{document}
\documentclass[dvipdfmx,margin=2mm]{standalone}
\usepackage{tikz}
\usepackage{amssymb}
\begin{document}
\begin{tikzpicture}[
    foo/.style={circle,draw}
  ]
  \foreach \i in {0,...,6}{
    \node[foo](\i) at (\i,0) {\i};
  };
  \node (u1) at (6.9, 1.5) {};
  \node (u2) at (6.9, 1.0) {};
  \node (u3) at (6.9, 0.5) {};
  \node (d1) at (6.9, -0.5) {};
  \node (d2) at (6.9, -1.0) {};
  \node (d3) at (6.9, -1.5) {};

  %[0, 8, 3, 6, 9, 7, 2, 5, 1, 4]
  \draw[-latex,loop above] (0) to (0);
  \foreach \i/\j in {2/3,3/6}{
    \draw[-latex] (\i.north) to[bend left] (\j.north);
  };
  \foreach \i/\j in {6/2}{
    \draw[-latex] (\i.south) to[bend left] (\j.south);
  };
  \draw[-latex] (1.north) to[bend left=20] (u1);
  \draw[-latex] (4.north) to[bend left=20] (u2);
  \draw[-latex] (5.north) to[bend left=20] (u3);
  \draw[-latex] (d1) to[bend left=20] (5.south);
  \draw[-latex] (d2) to[bend left=20] (4.south);
  \draw[-latex] (d3) to[bend left=20] (1.south);

  \draw[dashed] (6.5,-2.0) -- (6.5,2);
  \node at (6.5,-2.2) {$({L \to R},{R \to L})=(3,3)$};
  
\end{tikzpicture}
\end{document}
\documentclass[dvipdfmx,margin=2mm]{standalone}
\usepackage{tikz}
\usepackage{amssymb}
\begin{document}
\begin{tikzpicture}[
    foo/.style={circle,draw}
  ]
  \begin{scope}
    \node[foo](x) at (0,0) {$x$};
    \node(lb) at(-1,-0.5) {};
    \node(lu) at(-1,0.5) {};
    \node(rb) at(1,-0.5) {};
    \node(ru) at(1,0.5) {};
    \draw[-latex] (lu) to[bend left] (x);
    \draw[-latex] (x) to[bend left] (lb);
    \draw[dashed] (-0.5,-1) -- (-0.5,1);
    \draw[dashed] (0.5,-1) -- (0.5,1);
    \node at (-0.5,-1.3) {$a$};
    \node at (0.5,-1.3) {$a-1$};
    \draw[-latex] (-0.9,0.9) to (0.9,0.9);
    \draw[-latex] (-0.9,0.7) to (0.9,0.7);
    \draw[-latex] (0.9,-0.9) to (-0.9,-0.9);
    \draw[-latex] (0.9,-0.7) to (-0.9,-0.7);

  \end{scope}
  

  \begin{scope}[xshift=3cm]
    \node[foo](x) at (0,0) {$x$};
    \node(lb) at(-1,-0.5) {};
    \node(lu) at(-1,0.5) {};
    \node(rb) at(1,-0.5) {};
    \node(ru) at(1,0.5) {};
    \draw[-latex] (lu) to[bend left] (x);
    \draw[-latex] (x) to[bend left] (ru);
    \draw[dashed] (-0.5,-1) -- (-0.5,1);
    \draw[dashed] (0.5,-1) -- (0.5,1);
    \node at (-0.5,-1.3) {$a$};
    \node at (0.5,-1.3) {$a$};
    \draw[-latex] (-0.9,0.9) to (0.9,0.9);
    \draw[-latex] (-0.9,0.7) to (0.9,0.7);
    \draw[-latex] (0.9,-0.9) to (-0.9,-0.9);
    \draw[-latex] (0.9,-0.7) to (-0.9,-0.7);
    \draw[-latex] (0.9,-0.5) to (-0.9,-0.5);

  \end{scope}

  \begin{scope}[xshift=6cm]
    \node[foo](x) at (0,0) {$x$};
    \node(lb) at(-1,-0.5) {};
    \node(lu) at(-1,0.5) {};
    \node(rb) at(1,-0.5) {};
    \node(ru) at(1,0.5) {};
    \draw[-latex] (rb) to[bend left] (x);
    \draw[-latex] (x) to[bend left] (lb);
    \draw[dashed] (-0.5,-1) -- (-0.5,1);
    \draw[dashed] (0.5,-1) -- (0.5,1);
    \node at (-0.5,-1.3) {$a$};
    \node at (0.5,-1.3) {$a$};
    \draw[-latex] (-0.9,0.9) to (0.9,0.9);
    \draw[-latex] (-0.9,0.7) to (0.9,0.7);
    \draw[-latex] (-0.9,0.5) to (0.9,0.5);
    \draw[-latex] (0.9,-0.9) to (-0.9,-0.9);
    \draw[-latex] (0.9,-0.7) to (-0.9,-0.7);


  \end{scope}

  \begin{scope}[xshift=9cm]
    \node[foo](x) at (0,0) {$x$};
    \node(lb) at(-1,-0.5) {};
    \node(lu) at(-1,0.5) {};
    \node(rb) at(1,-0.5) {};
    \node(ru) at(1,0.5) {};
    \draw[-latex] (x) to[bend left] (ru);
    \draw[-latex] (rb) to[bend left] (x);
    \draw[dashed] (-0.5,-1) -- (-0.5,1);
    \draw[dashed] (0.5,-1) -- (0.5,1);
    \node at (-0.5,-1.3) {$a$};
    \node at (0.5,-1.3) {$a+1$};
    \draw[-latex] (-0.9,0.9) to (0.9,0.9);
    \draw[-latex] (-0.9,0.7) to (0.9,0.7);

    \draw[-latex] (0.9,-0.9) to (-0.9,-0.9);
    \draw[-latex] (0.9,-0.7) to (-0.9,-0.7);


  \end{scope}

  \begin{scope}[xshift=12cm]
    \node[foo](x) at (0,0) {$x$};
    \node(lb) at(-1,-0.5) {};
    \node(lu) at(-1,0.5) {};
    \node(rb) at(1,-0.5) {};
    \node(ru) at(1,0.5) {};
    \draw[-latex,loop above] (x) to (x);
    \draw[dashed] (-0.5,-1) -- (-0.5,1);
    \draw[dashed] (0.5,-1) -- (0.5,1);
    \node at (-0.5,-1.3) {$a$};
    \node at (0.5,-1.3) {$a$};
        \draw[-latex] (-0.9,0.9) to (0.9,0.9);
    \draw[-latex] (-0.9,0.7) to (0.9,0.7);

    \draw[-latex] (0.9,-0.9) to (-0.9,-0.9);
    \draw[-latex] (0.9,-0.7) to (-0.9,-0.7);


  \end{scope}
\end{tikzpicture}
\end{document}