ABC134 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.
The oddness is the sum of the number of edges across over the lines. Let us consider doing DP. Partial solution is like this.
There are five transitions.
#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}