# 模反元素/模逆元
## 先備知識
[模運算](/564I9dxSTf6crJP95qRnlQ)

## infro
我們在模運算會學到下面這些運算
- $(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\ {}^\land \ b)\ \%\ p\ =\ ((a\ \%\ p)\ {}^\land\ b)\ \%\ p)$

但就是不見除法的身影，所以這時就要靠模逆元了
## 模反元素/模逆元
一元素$a$乘上$b$後$mod$ $p$得到的單位元素為1
$ab\ =\ 1\ (mod\ p)$，$a$為任意一元素，$b$為$mod\ p$時的模反元素
- $3$在$mod\ 2$時的反元素為$1$
$\implies 3*1\ =\ 1\ (mod\ 2)\implies (3*1)\ mod\ 2 = 1$
- $3$在$mod\ 5$時的反元素為$2$
$\implies 3*2\ =\ 1\ (mod\ 5)\implies (3*2)\ mod\ 5 = 1$

b有時會被寫成$a^{-1}$

## 應用
如果知道$b$的模逆元為$x$，那麼$\frac{a}{b}\ mod\ p$ 就可以表示成 $(a * x)\ mod\ p$
這樣就解決了除法沒有分配律的問題了
- $\frac{63}{7} mod\ 5\implies (63 * x)\ mod\ 5$，$x$為7的模反元素
而$7$在$\ mod\ 5$時的模反元素是$3\implies (7*3)\ mod\ 5\ =\ 1$
$\implies \frac{63}{7} mod\ 5\ =\ (63 * 3)\ mod\ 5\ =\ 4$

## 模逆元的計算方法
在$a\ mod\ p$時的模逆元為$\implies$$a^{p-2}\ mod\ p$
- $7^{5-2}\ mod\ 5\ =\ 3$

### 證明
#### 費馬小定理
有一整數a，一質數p，則$a^{p} - a$是p的倍數，表示為
$\implies\ a^{p}\ -\ a \equiv\ 0\ (mod\ p)$
#### 推導
$\implies\ a^{p}\ -\ a \equiv\ 0\ (mod\ p)$
↓$\ \ \ \ \ \ \ \ \ a^{p}$多一個$a$所以除$p$餘$a$
$\implies\ a^{p}\ \equiv\ a (mod\ p)$
↓$\ \ \ \ \ \ \ \ \ a^{p}\ = pg\ +\ a$
↓$\ \ \ \ \ \ \ \ \ pg\ =\ p * ak$
↓$\ \ \ \ \ \ \ \ \ a^{p}\ =\ p\ *\ ak\ +\ a$
↓$\ \ \ \ \ \ \ \ \ a^{p}\ =\ a(pk\ +\ 1)$
↓$\ \ \ \ \ \ \ \ \ a^{p-1}\ =\ pk\ +\ 1$
$\implies\ a^{p-1}\ \equiv\ 1\ (mod\ p)$

## 練習題
[題目](http://203.64.191.163/ShowProblem?problemid=a689)
這題就是排列組合
只是這題的範圍非常大
所以需要一點模運算
我是先把1\~100000階乘和1\~100000階乘的模逆元都先存起來
然後計算字串重複的個數
然後再用域先處理好的階乘數乘上重複個數階乘的模逆元
(等同於除上重複個數階乘--->費馬小定理$a^{-1}≡1\ (mod\ p)\ p為質數$)

---

:::info
:::spoiler <font color="00FF00">**AC**</font>_code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define maxn 100005
int factorial_inv[maxn];
int factorial[maxn];
int q_pow(int a, int x){
    int sum = 1;
    while(x > 0){
        if(x & 1)sum = (sum %mod)* (a % mod);
        a = (a % mod) * (a % mod);
        x >>= 1;
    }
    return sum % mod;
}
void build(){//a^(p-2)≡a^(-1) (mod p)
    factorial[0] = 1;
    for(int i = 1; i < maxn; i++){
        factorial[i] = (factorial[i - 1] * i)%mod;
        factorial_inv[i] = q_pow(factorial[i], mod-2);
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    build();
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        vector<int> c(1000);
        for(auto& i : c)i = 0;
        for(int i = 0; i < s.size(); i++){
            c[(int)s[i]]++;
        }
        vector<int> vc;
        for(int i = '0'; i <= '9'; i++ ){
            if(c[i] > 1)vc.push_back(c[i]);
        }
        for(int i = 'A'; i <= 'z'; i++){
            if(c[i] > 1)vc.push_back(c[i]);
        }
        int ans = factorial[s.size()] % mod;
        for(int i = 0; i < vc.size(); i++){
            ans = ans *(factorial_inv[vc[i]] % mod);
            ans %= mod;
        }
        cout << ans << '\n';
    }
}

:::