Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting

Definition of multiplicative inverse

If integer  b,m  Coprime , And for any integer  a, If meet  b|a( to be divisible by ), Then there is an integer  x, bring  a/b≡a*x(mod m), said  x  by  b  The mold  m  Multiplicative inverse element , Write it down as  (mod m). b The necessary and sufficient condition for the existence of multiplicative inverse is  b  And modulus  m  Coprime . When modulus  m Prime number ,  namely by  b  Multiplicative inverse element of .

So we can use the template of fast power to solve the inverse element .

Example ：876. Fast power inverse - AcWing Question bank

Topic ：

  Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
// Fast power template 
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll) a*a%p;
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    while(n--)
    {
        ll a,p;
        cin>>a>>p;
        if(a%p) cout<<qmi(a,p-2,p)<<endl;// Only when a No p A multiple of the , Only then has the inverse element .
// if a yes p Multiple , Then there are a/b=0, Will not be the same as a*x 了 , That is, there is no inverse element .
        else cout<<"impossible"<<endl;
    }
    return 0;
}

Let's talk about the function of inverse element

First, let's talk about the concept of addition, subtraction, multiplication and division

(a + b) % p = (a%p + b%p) %p   （√）

(a - b) % p = (a%p - b%p) %p    （√）

(a * b) % p = (a%p * b%p) %p    （√）

(a / b) % p = (a%p / b%p) %p   （×）

It's not hard to see that it's wrong to do division and remainder , Look at an example ：

(100/50)%20 = 2 ≠ (100%20) / (50%20) %20 = 0

For some topics , Because the number is too big , The computer can't save , We must find the remainder in the middle process . If division occurs in this expression , We can't divide first and then take the module , From the top “ Division and remainder are wrong ”, Therefore, we need to use the inverse element to replace .

Example ：E- Permutation count _ The first 20 Shanghai University Programming League summer competition （ Off campus synchronized competition ） (nowcoder.com)
 

Title Description

Input description :

Output description :

 Output a line of integers , Indicates the number of permutations that meet the conditions , Because the answer can be big , Yes, please. 1e9+7 modulus 

Example 1

Input

1

Output

1

Example 2

Input

3

Output

360

It can be seen from the title , What we need to ask for is 2*n!/2 Value output of .

If you write factorial modulo output directly , Of course. wa Slightly .

  Here, put that slightly except 2 The operation of is changed to Multiply 2（ model mod） And then take the module will ac 了 .

Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// Fast power template 
int qmi(int a,int k,int p)
{
    int res=1;
    while(k)
    {
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll) a*a%p;
    }
    return res;
}
int main()
{
    IOS;
    ll n;
    cin>>n;
    ll ans=1;
    for(int i=1;i<=2*n;i++)
        ans=(ans*i)%mod;
    cout<<ans*qmi(2,mod-2,mod)%mod<<endl;
    return 0;
}