逆元 Inverse element
1.前铺
（i）若 a mod p = x, a mod q = x,(p,q) = 1, 则 a mod pq = x
证明：设a = k1p + x = k2q + x,得：
k1p = k2q
由于(p,q) = 1 ,我们知道 k1 是 q 的倍数， k2 是 p 的倍数。设k1 = kq,k为非零整数
带回原式 ，得：a = k1q + x = kpq + x = k(pq) + x
由此可得 a mod pq = x
（ii）同余式ca ≡ cb( mod m ),等价于a ≡ b( mod m / (c,m) )
(iii) 费马小定理 : p is a prime ,a不是p的倍数,p>a
有 a^(p-1)≡1(mod p)，得：
` a^(p-2))≡1/a(mod p) false
a^(p-2))≡inv(a)(mod p) true
所以 inv(a)=a^(p-2) mod p
(iiii) inv(ab)=inv(a)inv(b)
2.题目
T1求逆元
时间限制：1秒 内存限制：128M
题目描述
如果一个线性同余方程𝑎𝑥≡1(𝑚𝑜𝑑 𝑏)，则称x为𝑎 𝑚𝑜𝑑 𝑏的逆元，记作𝑎−1。现在令𝑏=109+7，求𝑎−1。
输入描述
输入一个𝑎a，1≤𝑎≤1000
输出描述
输出𝑎−1
样例输入
3
样例输出
333333336
code：
#include<iostream>
using namespace std;
long long a,p=1e9+7;
long long ksm(long long a,long long b,long long p){long long ans = 1;while(b){if(b&1) ans=(ans*a)%p;a=(a*a)%p;b>>=1;}return ans;
}
inline long long inv(int a){return ksm(a,p-2,p);
}
int main(){cin>>a;cout<<inv(a);return 0;
}T2最值序列
时间限制：1秒 内存限制：128M
题目描述
给一个长度为𝑛的序列𝑎𝑛，一开始你有一个数𝐴=0，每次可以从序列中选一个数𝑏b，令𝐴=𝐴+𝑏或者𝐴=𝐴×𝑏，每个数都要使用一次，加的次数要和乘的次数近可能相近，要求最大化𝐴，输出A对998244353取模的值
输入描述
第一行为一个整数𝑛，表示序列的长度。
第二行为n个整数𝑎𝑖，描述这个序列。2≤𝑛≤10^3,1<𝑎𝑖≤10^9
输出描述
一个非负整数，表示𝐴A的最大值对998244353取模的值。
样例输入
43 3 2 4
样例输出
60
code:
#include<iostream>
#include<algorithm>
using namespace std;
int n,a[1005];
const int mod = 998244353;
long long ans;
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);for(int i=1;i<=n/2;i++) ans=(ans+a[i])%mod;for(int i=n/2+1;i<=n;i++) ans = ans*a[i]%mod;cout<<ans;return 0;
}T3线性求逆元
时间限制：1秒 内存限制：128M
题目描述
给定𝑛,𝑝，求11到n所有整数在模p意义下的乘法逆元。
输入描述
两个正整数𝑛,𝑝(1≤𝑛≤3×106,𝑛<𝑝<20000528)，保证𝑝是质数
输出描述
输出𝑛行，第𝑖i行代表𝑖在模𝑝意义下的乘法逆元
样例输入
10 13
样例输出
179108112534
code:
#include<iostream>
using namespace std;
const int N = 3e6+5;
long long mod,n,cnt;
long long vis[N],prime[N],inv[N];
long long ksm(long long a,long long b,long long p){long long ans = 1;while(b){if(b&1) ans=(ans*a)%p;a=(a*a)%p;b>>=1;}return ans;
}int main(){scanf("%d%d",&n,&mod);vis[1]=inv[1]=1;printf("1\n");for(int i=2;i<N;i++){if(!vis[i]){prime[++cnt]=i;inv[i]=ksm(i,mod-2,mod);}for(int j=1;j<=cnt&&1ll*i*prime[j]<N;j++){vis[i*prime[j]]=1;inv[i*prime[j]] = inv[i]*inv[prime[j]]%mod;if(i%prime[j]==0) break;}}for(int i=2;i<=n;i++) printf("%lld\n",inv[i]);return 0;
}but上述代码中，ksm使得并非线性,另有一种真正线性的方法：
#include<iostream>
using namespace std;
const int N = 5e6+5;
long long p,n,cnt,inv[N];
int main(){scanf("%lld%lld",&n,&p);inv[1]=1;cout<<"1\n";for(int i=2;i<=n;i++){inv[i]=(p-p/i)*1ll*inv[p%i]%p;cout<<inv[i]<<"\n";}return 0;
}T4线性求逆元2
题目描述
给出𝑛n个正整数𝑎𝑖ai，求：
∑𝑖=1𝑛𝑎𝑖−1×998244353𝑛−𝑖(𝑚𝑜𝑑 𝑝)
𝑝=10^9+7
输入描述
第一行一个正整数𝑛(1≤𝑛≤5×10^6)
第二行𝑛n个整数𝑎𝑖(1≤𝑎𝑖<𝑝)
输出描述
如题
样例输入
54 7 8 12 123456
样例输出
650798912
code:
#include<iostream>
using namespace std;
const int N = 5e6+5;
const int mod = 998244353,p = 1e9+7;
long long n,cnt,s[N],sinv[N],a[N];
long long ksm(long long a,long long b,long long p){long long ans = 1;while(b){if(b&1) ans=(ans*a)%p;a=(a*a)%p;b>>=1;}return ans%p;
}
void invinit(){// Very important!!!s[0]=1;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]*a[i]%p;}sinv[n]=ksm(s[n],p-2,p);for(int i=n;i>=1;i--){sinv[i-1] = sinv[i]*a[i]%p;}
}
long long inv(long long x){return sinv[x]*s[x-1];
}
int main(){scanf("%lld",&n);invinit();long long ans = 0;for(int i=1;i<=n;i++){ans=ans*mod%p;ans=(ans+inv(i))%p;}cout<<ans<<"\n";return 0;
}T5逆元求组合数
时间限制：1秒 内存限制：128M
题目描述
求组合数𝐶𝑛𝑚对10^9+7取模的值。
输入描述
第一行一个正整数𝑇(1≤𝑇≤1000)，代表有𝑇T组输入。
接下来𝑇T行，每行两个正整数𝑛,𝑚(1≤𝑚≤𝑛≤106)
输出描述
如题。
样例输入
28 21000000 500000
样例输出
28996692777
code:
#include<iostream>
using namespace std;
const int N = 1e6+5;
const int mod = 998244353,p = 1e9+7;
long long n,m,cnt,fac[N],sinv[N],a[N];
long long ksm(long long a,long long b,long long p){long long ans = 1;while(b){if(b&1) ans=(ans*a)%p;a=(a*a)%p;b>>=1;}return ans%p;
}
void invinit(){fac[0]=1;for(int i=1;i<N;i++){fac[i]=fac[i-1]*i%p;}sinv[N-1]=ksm(fac[N-1],p-2,p);for(int i=N-2;i>=0;i--){sinv[i] = sinv[i+1]*(i+1)%p;}
}
long long C(long long a,long long b){if(a<b) return 0;if(a==b||b==0) return 1;return fac[a]*sinv[b]%p*sinv[a-b]%p;
}
int main(){int T;cin>>T;invinit();while(T--){cin>>n>>m;cout<<C(n,m)<<"\n";}return 0;
}oh,三个小时，干完