「WHOI-2」ぽかぽかの星

Luogu

IDLGP8432

Time2000ms

Memory256MB

DifficultyP4

数学洛谷原创O2优化

有多少个长度为 $n$ 的**正整数**数列 $a_i$ 满足： - $0<a_1\leq a_2\leq a_3\dots \leq a_n\leq k$。 - $\forall i\not = j,a_i+a_j\not = k+1$。答案对 $10^9+7$ 取模。 ## Input **本题多测** 第一行一个正整数表示 $T$。接下来 $T$ 行，每行两个正整数表示 $n,k$。 ## Output $T$ 行，每行一个正整数表示答案。 [samples] ## Background ![](bilibili:BV16J411x7nS) 你在雪洞里喝着热可可数星星。但这次，星星换成了数列，不过聪明的你一定能数清楚数列的吧。 ## Note **本题采用捆绑测试** - $\text{subtask1(20pts)}:T=5,1\leq n,k\le5$。 - $\text{subtask2(80pts)}:$ 无特殊限制。对于 $100\%$ 的数据，$T\leq100,1\le n,k\le 5\times 10^6,1\leq \sum n, \sum k\le6\times 10^7$。

Samples

Input #1

3
2 2
1145 1419
19198 12321

Output #1

2
66937457
949924930

API Response (JSON)

{
  "problem": {
    "name": "「WHOI-2」ぽかぽかの星",
    "description": {
      "content": "有多少个长度为 $n$ 的**正整数**数列 $a_i$ 满足： - $0<a_1\\leq a_2\\leq a_3\\dots \\leq a_n\\leq k$。 - $\\forall i\\not = j,a_i+a_j\\not = k+1$。 答案对 $10^9+7$ 取模。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8432"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有多少个长度为 $n$ 的**正整数**数列 $a_i$ 满足：\n\n- $0<a_1\\leq a_2\\leq a_3\\dots \\leq a_n\\leq k$。\n- $\\forall i\\not = j,a_i+a_j\\not = k+1$。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n**本题多测**\n\n第一行一个正整数表示 $T$。\n\n接下来 $T$ 行，每行两个正整数表示 $n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments