[集训队互测 2021] 数列重排

Luogu
IDLGP9055
Time600ms
Memory256MB
DifficultyP6
贪心集训队互测2021O2优化组合数学构造分类讨论
定义一个数列区间的 $\textrm{mex}$ 为区间中最小的没有出现过的自然数,定义一个数列的价值为其中 $\textrm{mex}\geq k$ 的区间数量。 给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$,令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值,对于每一个 $k\in [l,r]$,求出 $f(k)$。 令 $a_i$ 表示数字 $i$ 出现的次数,保证存在正整数 $X$,使得 $\forall i\le m-1,a_i\in \{X,X+1\}$。 ## Input 由于 $n$ 可能很大,将采取如下方式减少读入量: 第一行四个整数 $m,l,r,X$。 第二行一个长度为 $m$ 的 $01$ 串,若其中第 $i$ 个位置为 $1$ 则数字 $i-1$ 的出现次数为 $X+1$,否则出现次数为 $X$。 根据输入可以推出 $n=mX+S$,其中 $S$ 为 $01$ 串中 $1$ 的数量。 ## Output 为了减少输出量,令 $ans=\displaystyle{\bigoplus_{i=l}^r} (233^if(i)\bmod 998244353)$,其中 $\displaystyle\bigoplus$ 表示二进制下的按位异或,输出一行一个整数 $ans$。 [samples] ## Background dottle bot。 ## Note #### 样例 1 解释 在样例给出的数列中,有 $3$ 个 $0$ 和 $2$ 个 $1$,任意排列 $f(0)$ 均为 $15$,排列为 $\textrm{01010}$ 时 $f(1)$ 有最大值 $13$,答案为: $$ \displaystyle (233^0\times 15\bmod 998244353)\oplus(233^1\times 13\bmod 998244353)=3034 $$ #### 数据范围 - Subtask 1(5 points):$n,m\leq 9$。 - Subtask 2(15 points):$n,m\leq 200$。 - Subtask 3(15 points):$n,m\leq 5\times 10^3$。 - Subtask 4(5 points):$m\leq 2$,$l=0$,$r=1$。 - Subtask 5(10 points):$m\leq 10^6$,$l=m$,$r=m$。 - Subtask 6(10 points):$m\leq 10^6$,$X=1$,$s_i=0$。 - Subtask 7(15 points):$m\leq 10^6$,$r-l+1\leq 10^4$。 - Subtask 8(15 points):$m\leq 2\times 10^6$。 - Subtask 9(10 points):无特殊限制。 对于所有数据,满足 $n\leq 10^9$,$m\leq 10^7$,$0\leq l\leq r\leq m$,$X\geq 1$。
Samples
Input #1
2 0 1 2
10
Output #1
3034
Input #2
14 1 14 13
10110101110101
Output #2
379883349
API Response (JSON)
{
  "problem": {
    "name": "[集训队互测 2021] 数列重排",
    "description": {
      "content": "定义一个数列区间的 $\\textrm{mex}$ 为区间中最小的没有出现过的自然数,定义一个数列的价值为其中 $\\textrm{mex}\\geq k$ 的区间数量。 给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$,令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值,对于每一个 $k\\in [l,r]$,求出 $f(k)$。 令 $a_i$ 表示数字 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 600,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9055"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "定义一个数列区间的 $\\textrm{mex}$ 为区间中最小的没有出现过的自然数,定义一个数列的价值为其中 $\\textrm{mex}\\geq k$ 的区间数量。\n\n给定 $n$ 个小于 $m$ 的自然数和一个区间 $[l,r]$,令 $f(k)$ 表示 $n$ 个数构成的数列所有重排列中数列价值的最大值,对于每一个 $k\\in [l,r]$,求出 $f(k)$。\n\n令 $a_i$ 表示数字 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments