hdu5793——A Boring Question（快速幂+逆元）-白红宇

hdu5793——A Boring Question（快速幂+逆元）

阅读量：2344 次

发布时间：2019-05-10

本文共 1684 字，大约阅读时间需要 5 分钟。

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

打表推推推，最后发现是等比数列求和

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            #include 
            
             #define INF 0x3f3f3f3f#define MAXN 100010#define mod 1000000007using namespace std;long long PowerMod(long long a, long long b, long long c){ long long ans = 1; a = a % c; while(b>0) { if(b % 2 == 1) ans = (ans * a) % c; b = b/2; a = (a * a) % c; } return ans;}long long extend_gcd(long long a,long long b,long long &x,long long &y)//ax+by=1返回a,b的gcd，同时求的一组满足题目的最小正整数解{ long long ans,t; if(b==0) { x=1; y=0; return a; } ans=extend_gcd(b,a%b,x,y); t=x; x=y; y=t-(a/b)*y; return ans;}int main(){ long long t,n,m,ans,x,y; scanf("%I64d",&t); while(t--) { scanf("%I64d%I64d",&n,&m); long long a=PowerMod(m,n+1,mod)-1,b=m-1; extend_gcd(b,mod,x,y); while(x<0) x+=mod; ans=a*x%mod; printf("%I64d\n",ans); } return 0;}