阶乘逆元和线性逆元

逆元简介

a×b1(modp)a \times b \equiv 1 ( mod\,\,p),可以称ab在模p情况下的逆元.

逆元其实就是可以看作倒数

阶乘逆元

方式一:

通过费马小定理求逆元:

p为素数,并且gcd(a,p)=1时,我们有ap11(mod p)a^{p−1}≡1(mod\ p)。那么就有ap2×a1(mod p)a^{p−2}×a≡1(mod\ p),则a的逆元就是ap2a^{p−2}

下面ksm函数为快速幂

fact[0] = 1;
for(int i = 1; i < N; i++)
{
	fact[i] = fact[i - 1] * i % mod;
	inv[i] = ksm(fact[i], mod - 2);
}

方式二:

通过式子1(n+1)!×(n+1)=1n!\frac{1}{(n+1)!}\times (n+1)=\frac{1}{n!}倒推接近线性求阶乘逆元

1(n+1)!\frac{1}{(n+1)!}其实就可以看作(n+1)!{(n+1)!}的逆元

for(int i = 1; i <= n; i++)
	fact[i] = fact[i - 1] * i % mod;
inv[n] = ksm(fact[n], mod - 2);
for(int i = n - 1; i >= 1; i--)
	inv[i] = inv[i + 1] * (i + 1) % mod;

线性求逆元

[1,N1][1,N-1]关于mod的逆元时,可以做到在O(N)O(N)时间内解决

设模数为p

对于当前的i,设 p=k×i+rp=k \times i+r,则

k×i+r0(modp)k×i×(i1×r1)+r×(i1×r1)0(modp)k×r1+i10(modp)i1k×r1(modp)i1pi×r1(modp)\begin{aligned} k \times i + r & \equiv 0 & \pmod p \\\\ k \times i \times ( i^{-1} \times r ^{-1}) + r \times (i^{-1} \times r^{-1}) &\equiv 0 & \pmod p \\\\ k \times r^{-1} + i ^ {-1} & \equiv 0 & \pmod p \\\\ i^{-1} & \equiv -k \times r^{-1} & \pmod p \\\\ i^{-1} & \equiv - \left \lfloor \frac{p}{i}\right \rfloor \times r^{-1} & \pmod p \end{aligned}

注意:

inv[1]inv[1]一定要初始化为1,需要从2开始递推,不能从1开始递推

inv[0] = inv[1] = 1;
for(int i = 2; i < N; i++)
	inv[i] = inv[mod % i] * (mod - mod / i) % mod;

同时可以通过线性求逆元求阶乘逆元

只需要再将逆元用类似阶乘的形式乘起来即可,求得的inv[i]即为i!i!的逆元

for(int i = 2; i < N; i++)
	inv[i] = inv[i - 1] * inv[i] % mod;

组合数计算

CnmC_n^m计算

  • 方式一:公式计算
    计算都是在逆元或者阶乘基础上计算的
    Cnm=n!m!(nm)!C_n^m = \frac{n!}{m!*(n-m)!}
ll C(ll n, ll m)
{
	if(n < m) return 0;
	return fact[n] * inv[m] % mod * inv[n - m] % mod;
}
  • 方式二:递推方式
    需要建表,所以如果计算范围比较大时需要的空间也大
    递推公式 : Cnm=Cn1m+Cn1m1C_n^m = C_{n-1}^{m} + C_{n-1}^{m-1}
for(int i = 1; i <= n; i++)
	for(int j = 0; j <= i; j++)
	{
		if(i == j || j == 0) c[i][j] = 1;
		else c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
	}

题目

链接:https://ac.nowcoder.com/acm/contest/23481/J

题目描述:求

i1=1ni2=i1+1nik=ik1+1nai1×ai2××aik\sum \limits_{i_1 = 1}^n \sum \limits_{i_2 = i_1 + 1}^n \cdots \sum \limits_{i_k = i_{k - 1} + 1}^n a_{i_1} \times a_{i_2} \times \cdots \times a_{i_k}

就是在数组中选中k个值相乘,最后把结果相加即可


因为数组中的数大小只有三种情况。所以可以根据这个进行切入口。

首先00可以不用考虑,接下考虑有nn11mm22,如果上述和式中11出现了ii个,那么22需要出现kik-i个,于是答案为

i=0kCniCmki2ki\sum \limits_{i=0}^k C_n^i C_m^{k-i}2^{k-i}


代码中注意各种初始化
线性求逆元中初始化:inv[1] = 1

fac[i]:2i2^i

fact[i]:i!i!

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
const int N = 1e7 + 5, mod = 998244353;

ll fac[N], fact[N], inv[N];

ll C(ll n, ll m)
{
	if(n < m) return 0;
	return fact[n] * inv[m] % mod * inv[n - m] % mod;
}

void solve()
{
	fac[1] = 2;
	fac[0] = fact[0] = fact[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i < N; i++)
	{
		fac[i] = fac[i - 1] * 2 % mod;
		fact[i] = fact[i - 1] * i % mod;
		inv[i] = inv[mod % i] * (mod - mod / i) % mod; 
	}
	for(int i = 2; i < N; i++)
		inv[i] = inv[i - 1] * inv[i] % mod;
		
	int n, k;
	cin >> n >> k;
	vector<int> a(n);
	int o = 0, t = 0;
	
	for(int i = 0; i < n; i++) 
	{
		cin >> a[i];
		if(a[i] == 1) o ++;
		else if(a[i] == 2) t ++;
	}	
	ll res = 0;
	for(int i = 0; i <= k; i++)
	{
		res += C(o, i) * C(t, k - i) % mod * fac[k - i] % mod;
		res %= mod;
	}
	cout << res << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
//	cin >> t;
	t = 1;
	while(t--) solve();
	return 0;
}

   转载规则


《阶乘逆元和线性逆元》 行码棋 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
CF1181C Flag-子矩阵数量统计 CF1181C Flag-子矩阵数量统计
CF1181C Flag子矩阵数量统计 题目介绍 题目链接: https://codeforces.com/problemset/problem/1181/C 大意:有个人想要卖国旗。 一面国旗可以抽象为一个 n×mn \times
2022-06-29 2024-02-20
下一篇 
容斥定理 容斥定理
# 容斥定理 基本描述 对于上述图片,求∣A∪B∪C∣|A\cup B \cup C|∣A∪B∪C∣ 结果为∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣|A\cup B\cup C|=|A|
2022-06-25 2024-02-20
  目录