A Boring Question

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 487 Accepted Submission(s):
271

Problem Description

There are an equation.
∑0≤k1,k2,⋯km≤n∏1⩽j<m(kj+1kj)%1000000007=?
We define that (kj+1kj)=kj+1!kj!(kj+1−kj)! . And (kj+1kj)=0 while kj+1<kj .
You have to get the answer for each n and m that given to you.
For example,if n=1 ,m=3 ,
When k1=0,k2=0,k3=0,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=0,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=0,(k2k1)(k3k2)=0 ;
Whenk1=0,k2=0,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=0,k2=1,k3=1,(k2k1)(k3k2)=1 ;
Whenk1=1,k2=0,k3=1,(k2k1)(k3k2)=0 ;
Whenk1=1,k2=1,k3=1,(k2k1)(k3k2)=1 .
So the answer is 4.

Input

The first line of the input contains the only integer
T ,(1≤T≤10000)
Then T lines follow,the i-th line contains two integers n ,m ,(0≤n≤109,2≤m≤109)

Output

For each n and m ,output the answer in a single line.

Sample Input

1 2

2 3

Sample Output

Author

UESTC

题意：根据题目中规定的结算方式，给定n,m的值，求结果。

打表找规律，比赛的时候找到了还是没写出来。。因为有除法还有取模，所以要用到逆元，第一次使用逆元，找了一个模板。

附上代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #define ll long long

 #define mod 1000000007

 using namespace std;

 ll mat(ll a,ll b)///a^b，结果对mod取膜，b的值很大的时候

 {

     ll c=;

     if(b==) return a%mod; ///当b为1时，只剩下最后一个a

     else if(b&)  ///b为奇数

         return mat(a,b-)*a%mod; ///把单独的a拿出来

     else ///b为偶数

         return mat(a*a%mod,b/)%mod; ///直接相乘，系数除以2

 }

 ll extend_gcd(ll a,ll b,ll &x,ll &y)

 {

     if(a==&&b==) return -;//无最大公约数

     if(b==){x=;y=;return a;}

     ll d=extend_gcd(b,a%b,y,x);

     y-=a/b*x;

     return d;

 }

 //*********求逆元素*******************

 //ax = 1(mod n)

 ll mod_reverse(ll a,ll n)

 {

     ll x,y;

     ll d=extend_gcd(a,n,x,y);

     if(d==) return (x%n+n)%n;

     else return -;

 }

 ll c(ll n,ll m)

 {

     ll i,j,t1,t2,ans;

     t1=((mat(m,n+)-)%mod+mod)%mod;

     t2=(m-)%mod;

     return  t1*mod_reverse(t2,mod)%mod;

 }

 int main()

 {

     int T,n,m;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d%d",&n,&m);

         ll ans=c(n,m);

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

hdu 5793 A Boring Question（2016第六场多校）

A Boring Question

最新文章

热门文章