[NICA #3] 星空（Hard Version）

Luogu

IDLGB3903

Time1000ms

Memory512MB

DifficultyP5

O2优化排列组合逆元

小 R 有一个长度为 $n$ 的序列 $a$，保证序列中的每个数都是 $2$ 的整数次幂。小 M 有一个数 $x$，她希望重新排列序列 $a$，使得不存在一个 $i\in[1,n)$ 满足 $a_i+a_{i+1}>x$。重排的方式为：选择一个 $1\sim n$ 的排列 $p$，然后令新序列 $a'$ 满足 $a'_i=a_{p_i}$。$a'$ 即为重排后的序列。现在你想要知道有多少种重排的方式能满足小 M 的要求。两种重排方式不同当且仅当选择的排列 $p$ 不同。 ## Input 第一行输入两个正整数 $n,x$，表示序列长度和小 M 想的那个数；第二行输入 $n$ 个正整数 $a_i$，表示序列； ## Output 输出一行表示答案。答案对 $10^9+7$ 取模。 [samples] ## Background **Easy Version 和 Hard Version 差别在于数据范围。** ## Note 数据保证，$2 \leq n \leq 10^5$，$1 \leq a_i \leq 2^{60}$，$1 \leq x < 2^{63}$。

Samples

Input #1

6 46
4 8 8 16 32 32

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NICA #3] 星空（Hard Version）",
    "description": {
      "content": "小 R 有一个长度为 $n$ 的序列 $a$，保证序列中的每个数都是 $2$ 的整数次幂。 小 M 有一个数 $x$，她希望重新排列序列 $a$，使得不存在一个 $i\\in[1,n)$ 满足 $a_i+a_{i+1}>x$。重排的方式为：选择一个 $1\\sim n$ 的排列 $p$，然后令新序列 $a'$ 满足 $a'_i=a_{p_i}$。$a'$ 即为重排后的序列。 现在你想要知道有多少种",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3903"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 R 有一个长度为 $n$ 的序列 $a$，保证序列中的每个数都是 $2$ 的整数次幂。\n\n小 M 有一个数 $x$，她希望重新排列序列 $a$，使得不存在一个 $i\\in[1,n)$ 满足 $a_i+a_{i+1}>x$。重排的方式为：选择一个 $1\\sim n$ 的排列 $p$，然后令新序列 $a'$ 满足 $a'_i=a_{p_i}$。$a'$ 即为重排后的序列。\n\n现在你想要知道有多少种...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments