「KDOI-04」Pont des souvenirs

Luogu

IDLGP9035

Time2000ms

Memory512MB

DifficultyP5

数学洛谷原创O2优化组合数学洛谷月赛

给定正整数 $n,k$，求有多少个长度为 $n$ 的正整数序列 $a$ 满足： * $0<a_1\le a_2\le a_3\le\cdots\le a_n\le k$； * $\forall\ i\not=j$，$a_i+a_j\le k+1$。答案对 $10^9+7$ 取模。 ## Input **本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。对于每组测试数据，输入包含一行两个正整数 $n,k$。 ## Output 对于每组测试数据，输出一行一个整数表示答案。 [samples] ## Background 虽然这是一个 C，但是 ![](https://cdn.luogu.com.cn/upload/image_hosting/dzj8va56.png) ## Note **【样例解释】** 对于第 $1$ 组测试数据，所有满足要求的序列为 $(1,1)$ 和 $(1,2)$。对于第 $2$ 组测试数据，所有满足要求的序列为 $(1)$，$(2)$ 和 $(3)$。 **【数据范围】** 对于 $100\%$ 的数据，保证 $1\le T\le2\times10^5$，$1\le n,k\le10^7$。 **本题开启捆绑测试。** |子任务编号|分值|$T\le$|$n\le$|$k$| |:-:|:-:|:-:|:-:|:-:| |$1$|$8$|$5$|$5$|$\le5$| |$2$|$3$|$10^5$|$10^7$|$=1$| |$3$|$3$|$10^5$|$10^7$|$=2$| |$4$|$8$|$10^5$|$10^7$|$=3$| |$5$|$16$|$10$|$200$|$\le200$| |$6$|$16$|$10$|$3000$|$\le3000$| |$7$|$8$|$10^4$|$10^7$|$\le5$| |$8$|$8$|$100$|$10^7$|$\le10^5$| |$9$|$30$|$2\times10^5$|$10^7$|$\le10^7$|

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「KDOI-04」Pont des souvenirs",
    "description": {
      "content": "给定正整数 $n,k$，求有多少个长度为 $n$ 的正整数序列 $a$ 满足： * $0<a_1\\le a_2\\le a_3\\le\\cdots\\le a_n\\le k$； * $\\forall\\ i\\not=j$，$a_i+a_j\\le k+1$。 答案对 $10^9+7$ 取模。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9035"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定正整数 $n,k$，求有多少个长度为 $n$ 的正整数序列 $a$ 满足：\n\n* $0<a_1\\le a_2\\le a_3\\le\\cdots\\le a_n\\le k$；\n* $\\forall\\ i\\not=j$，$a_i+a_j\\le k+1$。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n**本题包含多组测试数据。**\n\n输入的第一行包含一个正整数 $T$，表示测试数据组数。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments