Interview

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 157 Accepted Submission(s): 60

Problem Description
Alice and Bob are going to Tenbaba for an interview. There are totally N candidates(including Alice and Bob) applying for this job. The recruitment process of Tenbaba is strict. So all of them need to have an interview with the department manager. N candidates will get a unique integer from 1 to N with equal probability. And they will go to interview with the manager according to the number they get. The candidate with number 1 will be interviewed firstly, the candidate with number 2 will be interviewed secondly and so on.

What’s more, HR(the staff to arrange the interview for you) will randomly choose a nonnegative integer K in range [0..N] with equal probability. The candidates whose numbers are not greater than K will be interviewed in order of their numbers on the first day. Remaining candidates will be interviewed in order of their numbers on the second day. Candidates don’t know K. But each one will knows on which day he or she will be interviewed.

Sadly, Alice forgot her number. The only thing she remember is that she will be interviewed on the second day. Alice also knows on which day Bob will be interviewed. But she doesn’t know the exact number Bob has. Assume that Alice would be the Y-th(1≤Y≤N−K) candidate to interview with the manager on the second day. Please help Alice to calculate the expectation of Y because Alice doesn’t want to go out too early.

Input
The first line is the number of test cases. It’s guaranteed that the test cases is not greater than 105.

Each test case contains two integers N and D (2≤N≤109,D= 1 or 2). D=1 means Bob will be interviewed on the first day and D=2 means Bob will be interviewed on the second day.

Output
Each test case contains one line with one integer. Let¡ˉs assume the possibility be equal to the irreducible fraction P/Q. Print the value of P⋅Q−1 in the prime field of integers modulo 1000000007(109+7).

Sample Input
3
2 1
3 2
100 1

Sample Output
1
875000008
500000029

有一场n个人参加的面试，面试分两天进行，每个人等概率的获得面试的顺序，但是他们并不知道自己的面试编号，只知道自己在哪一天面试，每一天进行的人数是随机获取的。Alice和Bob一起去面试，问Bob在已知Alice和自己在哪一天面试的情况下，Bob在面试的当天是期望第几个被面试的，其中Bob一定是第二天面试，分别求出Alice在第一天和第二天面试,Bob第几个被面试的期望

输入T代表有T组数据，每组数据N和D，
代表一共有N个人，其中Alice在第D天面试

从间隔的角度入手，问题首先简化为这样，设alice,bob的序号分别是x1,x2,k为第一天面试的人数，其中Bob的序号暂时和Alice连起来考虑，即假如Bob是第二天第一个被面试的人，那么Bob的序号是k+1, 这样所有可能的情况只需要考虑 x1,x2,k三个数所有可能的种数即可
首先考虑Bob在第二天，Alice在第一天，分母的算法:
问题可表述为

求 0 <x1<= k< x2<=n，即对于三个数 之间的四个间隔 a1+a2+a3+a4 = n,其中a2>=1,a4>=1, 求非负整数解的个数。

答案是C(n+1,3)

推导:首先可以简化成求a1+a2+a3+a4 = n-2,的解的个数
因为可以先分配两个下限1，
接着 我们考虑这样一个问题， k个自然数和为n的解的个数
假设有k+n个标记，当中选k个，第一个标记必须选(为了避免出现有的未标记的点之前没有标记而实行的规则)，每个选中的标记后没有选中的标记个数（直到下一个选中标记之前），就是这个位置的自然数的值，这样选择的方法与此问题形成一个满射，每一种选择方法和一个解一一对应，答案就是 C(n+k-1,k-1)
例：2个自然数的和为3
那么答案就是4
分别是：
0 3
3 0
1 2
2 1
因为从n+k个标记中选择了k个标记，这样最后剩下的所有数的和就是n，而且保证了没有重复和漏掉的情况。*所以 a1+a2+a3+a4 = n-2 的解的个数就是k=4,n = n-2;
答案就是C(c+1,3)

接着考虑Alice在第二天的时候，分母是多少
和上面类似问题转化成
0<=k< x1< x2<=n
0<=k< x2 < x1<=n
的和，
所以这时候分母是2*C(n+1,3)

下面来考虑一下分子，Alice在第一天的时候，枚举Bob和Alice之间序号相差i的情况，相差i时，bob和alice两个人的位置情况有（n-i）种，i变化范围（1~n-1）,
例：n=4,i=1 就有1,2;2,3;3,4;三种情况
此时k可以取1,2,3这时bob的编号能取的排名只有1
n=4 i=2 时 有1，3 ； 2，4这两种情况，此时k取1，2
bob能取的排名有1,2
n=4,i=3时 有1,4 这一种情况，此时k取1
bob能取的排名有1,2,3
观察可以看出对于（n-i）的每一种情况，k都可以取ALice的所有编号，但是对于每个i，bob能取得却只有（1-i），这样bob排名对其最后答案期望的贡献就是 sum(1,i)
即
求

在这里要求这个和有3种方法，
1，数两次原理 ：
首先有这样一个结论对于一个数列第i项是C(i+k-1,k)
其前缀和就是C(i+k,k+1)
此时求和的两个数列分别是
（1）n，……5,4,3,2,1
( 2 ) i(i+1)/2 即C（i+1，2）
（1） 5 4 3 2 1
（2） 1 3 6 10 15 21 28 36
对于这样两个数列求卷积，就等于把第二个数列求两次前缀和
即C(n,2) 求两次前缀和就是C(n+2,4)
2: 拉格朗日插值法：
对于分母分子求出前四项分别进行插值
3. 利用生成函数

所以最后得到的和就是C(n+2,4)

那么如何利用生成函数呢？ 对于上面这个式子 要计算两个数列的卷积 a 5 4 3 2 1 b 1 3 6 10 15 21 28 36 对于第一个数列求和 x/（1-x）^2 对于第二个数列求和 x/ (1-x)^3 乘起来是 (x^2)/(1-x)^5 （6） 由下图（7）式 对于这个式子展开第k项正好是C（k,k+4） 但是由于（7）式是不带分子上的X^2的 所以相当于整体乘了一个x^2 这样在找（6）式中x次数为n的项的时候只需要在（7)式中向前找两项即找x次数是n-2的即可 第k-2项是C（k-2,k+2）即C(4,k+2) 所以第n-2项就是C（4，n+2） 就是a，b两个数列的卷积结果了

然后我们考虑Alice在第二天，分子是多少
还是从刚才那种思路入手，
刚才是
Alice,k,Bob
现在是k ，Bob, alice和k alice Bob
首先K bob alice这种情况正好倒过来答案和刚才完全一样
k alice Bob 这种情况Bob在后面，就是枚举k和Bob的序号差
然后Alice每有一个地方可以放，对Bob的贡献就加i+1
就是刚才的式子把i（i+1）/2替换成i（i+1）
就是第一种情况的两倍
所以Alice在第二天，分子是第一种情况的3倍
就是3c（n+2，4）

这样第一天，第二天的分子分母都求出来了，那么最后的答案也就出来了，alice在第一天答案是 （n+2）/4，alice在第二天答案是（3*n+6）/8,最后再求一下逆元即可。

code:

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const long long mod = 1e9+7;
long long n,d;
long long qpow(long long x,long long y)
{
    long long re = 1,t = x;
    while(y)
    {
        if(y&1)re =re*t%mod;
        y>>=1;
        t =t *t%mod;
    }
    return re;
}


int main()
{
     int t;
     cin>>t;
     while(t--)
     {
         cin>>n>>d;
         long long fm,fz;
         if(d==2)
         {
             fz = qpow(8,mod-2)*(3*n+6)%mod;
             printf("%lld\n",fz);
         }
         else
         {
             fz = qpow(4,mod-2)*(n+2)%mod;
             printf("%lld\n",fz);
         }
     }
    return 0;
}