当前位置:网站首页>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;
}
边栏推荐
- Word如何显示修改痕迹
- Use map function and split function to type multiple elements in one line
- English topic assignment (25)
- From 2022 to 2024, the list of cifar azrieli global scholars was announced, and 18 young scholars joined 6 research projects
- 安装Mysql报错:Could not create or access the registry key needed for the...
- Reptiles have a good time. Are you full? These three bottom lines must not be touched!
- R language ggplot2 visualization: use the ggstripchart function of ggpubr package to visualize the grouped dot strip plot, and set the add parameter to add box plots for different levels of dot strip
- R language ggplot2 visual time series histogram: visual time series histogram through two-color gradient color matching color theme
- Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
- 【论文笔记】TransUNet: Transformers Make StrongEncoders for Medical Image Segmentation
猜你喜欢
Synchronous development of business and application: strategic suggestions for application modernization
Master Xuan joined hands with sunflower to remotely control enabling cloud rendering and GPU computing services
Mathematical knowledge -- code implementation of Gaussian elimination (elementary line transformation to solve equations)
MRO industrial products enterprise procurement system: how to refine procurement collaborative management? Industrial products enterprises that want to upgrade must see!
AIRIOT物联网平台赋能集装箱行业构建【焊接工位信息监控系统】
Deep circulation network long-term blood pressure prediction [translation]
关于静态类型、动态类型、id、instancetype
Analysis of frequent chain breaks in applications using Druid connection pools
AutoCAD - what is the default lineweight for centerline drawing and CAD? Can I modify it?
[depth first search] Ji suanke: Square
随机推荐
Computer network: sorting out common network interview questions (I)
wx小程序学习笔记day01
php+redis实现超时取消订单功能
Crawling data encounters single point login problem
Take a look at how cabloyjs workflow engine implements activiti boundary events
美庐生物IPO被终止:年营收3.85亿 陈林为实控人
English topic assignment (25)
Word如何显示修改痕迹
R语言ggplot2可视化时间序列柱形图:通过双色渐变配色颜色主题可视化时间序列柱形图
Binary search tree
Solution of intelligent management platform for suppliers in hardware and electromechanical industry: optimize supply chain management and drive enterprise performance growth
Interview assault 63: how to remove duplication in MySQL?
R语言使用dt函数生成t分布密度函数数据、使用plot函数可视化t分布密度函数数据(t Distribution)
Airiot IOT platform enables the container industry to build [welding station information monitoring system]
中缀表达式转后缀表达式详细思路及代码实现
The second day of rhcsa study
helm部署etcd集群
AIRIOT物联网平台赋能集装箱行业构建【焊接工位信息监控系统】
Sanmian ant financial successfully got the offer, and has experience in Android development agency recruitment and interview
Actf 2022 came to a successful conclusion, and 0ops team won the second consecutive championship!!