Spoj-ANTP Mr. Ant & His Problem

Mr. Ant has 3 boxes and the infinite number of marbles. Now he wants to know the number of ways he can put marbles in these three boxes when the following conditions hold.

1) Each box must contain at least 1 marble.

2) The summation of marbles of the 3 boxes must be in between X and Y inclusive.

Now you are given X and Y. You have to find the number of ways Mr. Ant can put marbles in the 3 boxes.

Input

Input starts with an integer T, denoting the number of test cases. Each test case contains two integers X and Y.

Constraints

1<=T<=1000000

1<=X<= Y<=1000000

Output

For each test case, print the required answer modulo 1000000007.

Sample Input

Sample Output

4 5

Explanation for the first test case

Way 01

Way 02

Way 03

Way 04

Way 05

Way 06

Way 07

Way 08

Way 09

Note: use faster i/o method.

n个相同的东西放进三个不同的盒子里，每个盒子至少要有一个

这就是裸的排列组合题

用隔板法很容易知道，对于一个单独的n，答案就是C(n-1,2)，令f(x)=C(x-1,2)

对于f(x)的一段求和，显然在n>=3时才有方案，即f(x)定义域x>=3

令g(x)=f(3)+f(4)+...+f(x)，那么答案就是g(r)-g(l-1)，（考虑到定义域应当是g(r)-g(l)+f(l)不过似乎不这样也行）

然后根据组合数的性质C(2,2)+C(3,2)+...+C(x-1,2)=C(x,3)

所以g(x)=C(x,3)

然后做完了

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<set>

 #include<map>

 #include<ctime>

 #define LL long long

 #define inf 0x7ffffff

 #define pa pair<int,int>

 #define mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 #define mod 1000000007

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 inline LL calc(LL a)//return C a 3

 {

     if (a<)return ;

     return a*(a-)*(a-)/%mod;

 }

 int main()

 {

     int T=read();

     while (T--)

     {

         LL a=read(),b=read();

         printf("%lld\n",(calc(b)-calc(a-)+mod)%mod);

     }

 }

Spoj ANTP

巴特西

Spoj-ANTP Mr. Ant & His Problem

最新文章

热门文章