当前位置:网站首页>Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting
Fast power template for inverse element, the role of inverse element and example [the 20th summer competition of Shanghai University Programming League] permutation counting
2022-07-06 19:09:00 【Wu Yu 4】
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 .
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;
}
边栏推荐
- Jushan database was among the first batch of financial information innovation solutions!
- Estimate blood pressure according to PPG using spectral spectrum time depth neural network [turn]
- Don't miss this underestimated movie because of controversy!
- A wearable arm device for night and sleeveless blood pressure measurement [translation]
- Abstract classes and abstract methods
- R语言ggplot2可视化时间序列柱形图:通过双色渐变配色颜色主题可视化时间序列柱形图
- Xingnuochi technology's IPO was terminated: it was planned to raise 350million yuan, with an annual revenue of 367million yuan
- How word displays modification traces
- Qlabel marquee text display
- First day of rhcsa study
猜你喜欢
[paper notes] transunet: transformers make strongencoders for medical image segmentation
如何提高网站权重
On AAE
PMP每日一练 | 考试不迷路-7.6
朗坤智慧冲刺科创板:年营收4亿 拟募资7亿
AIRIOT物联网平台赋能集装箱行业构建【焊接工位信息监控系统】
应用使用Druid连接池经常性断链问题分析
How word displays modification traces
数学知识——高斯消元(初等行变换解方程组)代码实现
A wearable arm device for night and sleeveless blood pressure measurement [translation]
随机推荐
AutoCAD - what is the default lineweight for centerline drawing and CAD? Can I modify it?
The second day of rhcsa study
Countdown 2 days | live broadcast preview of Tencent cloud message queue data import platform
Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
php+redis实现超时取消订单功能
Multithreading Basics: basic concepts of threads and creation of threads
五金机电行业供应商智慧管理平台解决方案:优化供应链管理,带动企业业绩增长
ACTF 2022圆满落幕,0ops战队二连冠!!
How to improve website weight
R语言使用dt函数生成t分布密度函数数据、使用plot函数可视化t分布密度函数数据(t Distribution)
Tongyu Xincai rushes to Shenzhen Stock Exchange: the annual revenue is 947million Zhang Chi and Su Shiguo are the actual controllers
Optical blood pressure estimation based on PPG and FFT neural network [translation]
Jushan database was among the first batch of financial information innovation solutions!
Openmv4 learning notes 1 --- one click download, background knowledge of image processing, lab brightness contrast
The list of people who passed the fifth phase of personal ability certification assessment was published
Method of accessing mobile phone storage location permission under non root condition
上海部分招工市場對新冠陽性康複者拒絕招錄
test about BinaryTree
Airiot IOT platform enables the container industry to build [welding station information monitoring system]
Leetcode topic [array] - 119 Yang Hui triangle II