题目描述
<p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">我们定义一个数列<span>F(n)</span><span>代表</span><span>n</span><span>的有序拆分数：</span></span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">比如</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal" style="text-indent:37.2000pt;"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">3=3 </span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 3=1+2 </span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 3=2+1 </span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 3=1+1+1</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">3<span>的有序拆分数为</span><span>4</span><span>种。</span></span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">再比如</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=4</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=1+3</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=3+1</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=2+2</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=1+1+2</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=1+2+1</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=2+1+1</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"> 4=1+1+1+1</span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;">4<span>的有序拆分数有</span><span>8</span><span>种，当然我们很容易发现</span><span>F(n)=2^(n-1)</span><span>，所以咱们的题目肯定不可能是这么简单的。现在我想问的是，给定任意两个数</span><span>n</span><span>和</span><span>k</span><span>，求</span><span>n</span><span>的所有拆分情况中，</span><span>k</span><span>出现的次数是多少。</span></span><span style="font-family:宋体;font-weight:bold;font-size:15.0000pt;"></span> </p>
输入格式
<p class="MsoNormal"> <span style="font-family:宋体;font-size:12.0000pt;">输入文件包含多组测试数据。第一行，给出一个整数 <span>T</span><span>（</span><span>T<=20</span><span>），为数据组数。</span></span><span style="font-family:Calibri;font-size:12.0000pt;"></span> </p> <p class="MsoNormal"> <span style="font-family:宋体;font-size:12.0000pt;">接下来有一行，分别输入两个数<span>n,k</span><span>（</span><span>1<=n,k<=10^9</span><span>）</span></span><span style="font-family:宋体;font-size:12.0000pt;"></span> </p>
输出格式
<p class="MsoNormal"> <span style="font-family:宋体;font-size:12.0000pt;">输出结果并对<span>1e9+7</span><span>取余</span></span><span style="font-family:Calibri;font-size:12.0000pt;"></span> </p>
样例
样例输入 1
2
4 2
5 5
样例输出 1
5
1
提交代码
请先登录后提交
🤖 AI 解题助手
OpenRouter
就绪