Ex - Count Strong Test Cases

AtCoder

IDabc318_h

Time3000ms

Memory256MB

Difficulty—

Snuke has come up with the following problem. > You are given permutations $P=(P_1,P_2,\ldots,P_N)$ and $Q=(Q_1,Q_2,\ldots,Q_N)$ of $(1,2,\ldots,N)$. Let us build a graph with $N$ vertices and $N$ edges as follows. > > * For $i=1,2,\ldots,N$ in this order, draw an edge of weight $Q_i$ connecting vertices $i$ and $P_i$ bidirectionally. > > When removing some number of edges to eliminate cycles from the graph, find the minimum possible total weight of the removed edges. Alice and Bob came up with the following solutions. **Alice:** Initialize the answer to $0$. For $i=1,2,\ldots,N$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer. **Bob:** Initialize the answer to $0$. For $i=N,N-1,\ldots,1$ in this order, if the edge connecting vertices $i$ and $P_i$ is contained in a cycle, remove that edge and add its weight to the answer. Snuke has realized that their solutions are both incorrect, and he wants to know the number of inputs for which neither of their solutions gives the correct answer. Among the $(N!)^2$ possible inputs, find the number, modulo $998244353$, of inputs for which neither Alice's nor Bob's solution gives the correct answer. ## Constraints * $1\leq N\leq 2\times 10^5$ * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ [samples]

Samples

Input #1

Output #1

4

The following four inputs satisfy the condition.

*   $P=(2,3,1),Q=(2,1,3)$
*   $P=(2,3,1),Q=(3,1,2)$
*   $P=(3,1,2),Q=(2,1,3)$
*   $P=(3,1,2),Q=(3,1,2)$

For example, for the input $P=(2,3,1),Q=(2,1,3)$, the correct answer is $1$, but Alice's solution gives $2$ and Bob's gives $3$.

Input #2

Output #2

0

There may be no inputs that satisfy the condition.

Input #3

Output #3

Input #4

Output #4

321484323

API Response (JSON)

{
  "problem": {
    "name": "Ex - Count Strong Test Cases",
    "description": {
      "content": "Snuke has come up with the following problem. > You are given permutations $P=(P_1,P_2,\\ldots,P_N)$ and $Q=(Q_1,Q_2,\\ldots,Q_N)$ of $(1,2,\\ldots,N)$. Let us build a graph with $N$ vertices and $N$ ed",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc318_h"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke has come up with the following problem.\n\n> You are given permutations $P=(P_1,P_2,\\ldots,P_N)$ and $Q=(Q_1,Q_2,\\ldots,Q_N)$ of $(1,2,\\ldots,N)$. Let us build a graph with $N$ vertices and $N$ ed...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments