Inverse element & Combinatorial number & Fast power

The first is the derivation of the inverse element

Fermat's theorem mentioned here ：

Then we know the combination number C^k_n=A^k_n/A^k_k=n! / (n-k)! / k!
According to what we deduced before
set up inv[x] by x % mod Inverse element //mod For the value of remainder
Then use the fast power to get the factorial , Then take the inverse element by factorial

Here is the fast power ：

Then use the fast power to get the power , Then use the power to find the inverse element ：

inv[N - 1] = pow_mod(f[N - 1], mod - 2, mod);    // The inverse element of the preconditioned factorial is deduced , among pow_mod Is a fast power 
    for (int i = N - 2; i >= 0; i--) {
    
        inv[i] = inv[i + 1] * (i + 1) % mod;// Can be understood as 1/i!=1/(i+1)! *(i+1)
    }

What we use here is ：

inv[a]=a^m-2=1/a(mod m)

Pushable inv[x] % mod = 1/x;
Available C^k_n=A^k_n/A^k_k=n! / (n-k)! / k!=n! * inv[k] % mod * inv[n - k] % mod
The combinatorial number can be obtained by fast power and inverse element .

Attach title Bheith i ngra le
link ：https://ac.nowcoder.com/acm/contest/18362/B
source ： Cattle from

Komorebi is a primary student who is learning how to draw a mountain.

First of all, he gets an m\times nm×n grid, and he can paint some cells black and others white. Let’s define a grid is good if:

All the black cells are connected.

For every column of the grid, if there are black cells, all the black cells must be connected and there must be one on the bottom.

Let’s call the height of the highest black cell in the ii-th column h_ih
i
​
. Specially, if there isn’t any black cell in the ii-th column, then h_i=0h
i
​
=0. To make the good graph more likely to be a mountain, the graph should satisfy that there at least exists a pair of integers (l,r)(l,r):

1≤l≤r≤n1≤l≤r≤n

All the h_ih
i
​
(1≤i≤l1≤i≤l) are non-decreasing.

All the h_ih
i
​
(r≤i≤nr≤i≤n) are non-increasing.

All the h_ih
i
​
(l≤i≤rl≤i≤r) are equal.

Komorebi wants to know how many kinds of mountain graphs he can draw by his m\times nm×n grid. Can you help him?

Input description :
One line contains two integers nn and mm(1≤n,m≤20001≤n,m≤2000), the number of columns and rows of the grid.
Output description :
One line contains one integer indicates the number of mountain graphs Komorebi can draw.
Answer should mod 10^9+7.

Example 1
Input
1 1

Output
2

Example 2
Input
2 2

Output
9

Example 3
Input
2 3

Output
16

The code is as follows ：

#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#define ll long long
using namespace std;
const int maxn = 1000;
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int n, m;
ll num[N][N], f[N], inv[N];
ll ans;
ll pow_mod(ll a, ll b, ll c) {
    // Fast power 
    ll ans = 1;
    ll base = a % c;
    while (b) {
    
        if (b & 1) ans = (ans * base) % c;
        base = (base * base) % c;
        b >>= 1;
    }
    return ans % c;
}
inline ll C(int k, int n) {
    // Find the combination number 
    if (k > n) return 0;
    return f[n] * inv[k] % mod * inv[n - k] % mod;
}
void init() {
    
    //rev2 = pow_mod(2, mod-2,mod); // 2 Inverse element 
    f[0] = f[1] = 1;
    for (ll i = 2; i < N; i++) {
                  // Preprocessing factorials 
        f[i] = f[i - 1] * i % mod;
    }

    inv[N - 1] = pow_mod(f[N - 1], mod - 2, mod);    // The inverse element of the preconditioned factorial is deduced 
    for (int i = N - 2; i >= 0; i--) {
    
        inv[i] = inv[i + 1] * (i + 1) % mod;
    }
    return;
}
int main() {
    
    cin >> n >> m;
    for (int k = 1;k <= m;k++) {
    
        for (int i = n;i >= 1;i--) {
    
            num[i][k] = (num[i + 1][k] + C(k - 1, n - i + k - 1)) % mod;
        }
    }
    ans = 1;
    for (int i = 1;i <= n;i++) {
    
        for (int k = 1;k <= m;k++) {
    
            ans = (ans + C(k - 1, i + k - 2) * num[i][k] % mod) % mod;
        }
    }
    cout << ans;
    return 0;
}