『JROI-4』沈阳大街 2

Luogu

IDLGP8321

Time1000ms

Memory512MB

DifficultyP6

动态规划 DP2022洛谷原创O2优化排序洛谷月赛

给定两个长度为 $n$ 的序列 $A,B$，满足： * $\forall 1\le i<n,A_i \ge A_{i+1}$ * $A_n\ge \min\limits_{i=1}^n(B_i)$ $\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\pi)$： $$ f(\pi)=\prod_{i=1}^n\min(A_i,B_{\pi(i)}) $$ 每种排列出现的概率相等，求 $f(\pi)$ 的期望对 $998244353$ 取模的结果。即求: $$ \left(\dfrac{1}{n!}\sum_\pi f(\pi)\right) \bmod 998244353 $$ ## Input 第一行输入一个整数 $n$。第二行 $n$ 个整数表示 $A_i$。第三行 $n$ 个整数表示 $B_i$。 ## Output 输出一行一个整数，为答案。 [samples] ## Note **本题采用捆绑测试。** | 子任务编号 | 分值 | 特殊限制 | | :-----------: | :---:| :-----------: | | 1 | 5 | $1\le n\le 8$ | | 2 | 35 | $1\le n\le 50$ | | 3 | 20 | $A_n\ge \max\limits_{i=1}^n(B_i)$ | | 4 | 40 | 无 | 对于 $100\%$ 的数据满足 $1\le n\le 5000$，$1\le A_i,B_i\le 10^9$。

Samples

Input #1

8
15 14 13 10 9 6 3 2 
2 10 8 2 9 1 10 2

Output #1

114102208

API Response (JSON)

{
  "problem": {
    "name": "『JROI-4』沈阳大街 2",
    "description": {
      "content": "给定两个长度为 $n$ 的序列 $A,B$，满足： * $\\forall 1\\le i<n,A_i \\ge A_{i+1}$  * $A_n\\ge \\min\\limits_{i=1}^n(B_i)$ $\\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\\pi)$： $$ f(\\pi)=\\prod_{i=1}^n\\min(A_i,B_{\\pi(i)}) $$ 每种排列出现的概率相",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8321"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个长度为 $n$ 的序列 $A,B$，满足：\n\n* $\\forall 1\\le i<n,A_i \\ge A_{i+1}$ \n\n* $A_n\\ge \\min\\limits_{i=1}^n(B_i)$\n\n$\\pi$ 是一个长度为 $n$ 的排列，定义价值函数 $f(\\pi)$：\n\n$$\nf(\\pi)=\\prod_{i=1}^n\\min(A_i,B_{\\pi(i)})\n$$\n\n每种排列出现的概率相...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments