{"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\n对于每组测试数据，输入包含一行两个正整数 $n,k$。\n\n## Output\n\n对于每组测试数据，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n虽然这是一个 C，但是\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/dzj8va56.png)\n\n## Note\n\n**【样例解释】**\n\n对于第 $1$ 组测试数据，所有满足要求的序列为 $(1,1)$ 和 $(1,2)$。\n\n对于第 $2$ 组测试数据，所有满足要求的序列为 $(1)$，$(2)$ 和 $(3)$。\n\n**【数据范围】**\n\n对于 $100\\%$ 的数据，保证 $1\\le T\\le2\\times10^5$，$1\\le n,k\\le10^7$。\n\n**本题开启捆绑测试。**\n\n|子任务编号|分值|$T\\le$|$n\\le$|$k$|\n|:-:|:-:|:-:|:-:|:-:|\n|$1$|$8$|$5$|$5$|$\\le5$|\n|$2$|$3$|$10^5$|$10^7$|$=1$|\n|$3$|$3$|$10^5$|$10^7$|$=2$|\n|$4$|$8$|$10^5$|$10^7$|$=3$|\n|$5$|$16$|$10$|$200$|$\\le200$|\n|$6$|$16$|$10$|$3000$|$\\le3000$|\n|$7$|$8$|$10^4$|$10^7$|$\\le5$|\n|$8$|$8$|$100$|$10^7$|$\\le10^5$|\n|$9$|$30$|$2\\times10^5$|$10^7$|$\\le10^7$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9035","tags":["数学","洛谷原创","O2优化","组合数学","洛谷月赛"],"sample_group":[["5\n2 2\n1 3\n4 5\n4030 218\n1145 1419\n","2\n3\n20\n571656908\n172735629\n"]],"created_at":"2026-03-03 11:09:25"}}