SDOI2016 permutation count

It is found that many solutions fail to explain why the inverse element and recurrence formula are used in this problem. I, wind and rain 30 years, just to write a good problem. Let me help you.

A stable number is incremented from the left to the right of the sequence because it is necessary to ensure that the value is equal to the position

First of all, we can know according to the idea of combination number:

Answer = number of stable selection methods multiplied by number of unstable selection methods.

So now our goal is to find out the number of stable and unstable selection methods.

It is not hard to think that the number is actually the number of schemes selected from n numbers.

Isn't this the \ (C ^ m \) in combinatorial numbers? There are \ (C_n^m\) = \(\frac{n!}{m!(n-m)!} \)

Settle

That is to say, wrong arrangement

We make the array \ (F_x \) have X numbers, and each number is an unstable method number.

Since these numbers are unstable, there is no incremental relationship between the values, so we need to discuss the classification of each \ (F_x \).

\[suppose a number k, with n in the K position: \begin{cases} When k is in the N position & \ text {the number of permutations is $f {n-2} $(because the position of K has been determined, that is, the number of permutations of the remaining n-2 numbers)}\ When k is not in the nth position & \ text {the number of permutations is $f {n-1} $} \end{cases}\]

So for each \ (f {I \), there are \ (f {X-1} \) = (I - 1) × (\ (f {X-1} \) + \ (f {X-2} \)

So the final answer is: (\ (C {m \ times \) \ (f {N-M} \)% Mod

Then, for each set of data, set (\ (C {m \ times \) \ (f {N-M} \))% mod.

According to the meaning of the question, the number of final solutions may be very large (so we need to take modulus). When we multiply the answers, the accuracy of (\ (C ᦉ m \ times \) \ (f {N-M} \)% mod may explode, so we need to use:

Inverse element (inv)

For example, when there is (a/b)%MOD, it can prevent B from being too large and explosive, and convert a/b to some simple multiplication.

If C is the inverse of B, then there is (b * c) ≡ 1 (mod module)

Then (a/b)%mod = (a/b)1%mod = (a/b)bc%mod = (ac)%mod

That is (one number divided by another number)% modulus = (one number multiplied by the inverse of another number)% modulus

So for a fixed value in modulus, how to find the inverse of that value?

Please refer to Fermat's theorem

Give the answer directly: for the inverse of a% 100000007, it is \ (a ^ {100000007-2} \)

Just get a fast power

Code:

#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define Max(a,f) a > b ? a : b
#define Min(a,b) a < b ? a : b
#define in(n) n = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define New ll
#define ll long long
#define rg register
using namespace std;

namespace IO_Optimization//Optimization function 
{
    inline New read()//Fast reading 
    {
        New X = 0,w = 0;
        char ch = 0;

        while(!isdigit(ch))
        {
            w |= ch == '-';
            ch=getchar();
        }
        while(isdigit(ch))
        {
            X = (X << 3) + (X << 1) + (ch ^ 48);
            ch = getchar();
        }
        return w ? -X : X;
    }

    inline void write(New x)//Fast transfusion 
    {
         if(x < 0) putchar('-'),x = -x;
         if(x > 9) write(x / 10);
         putchar(x % 10 + '0');
    }
}
using namespace IO_Optimization;

const int mod = 1000000000 + 7;//modulus 
const int MAXN = 1000000 + 2;//Array size constant 

ll a[MAXN],f[MAXN],inv[MAXN];
// Factorial F array inverse element array 

inline ll ksm(ll a,ll b){//Fast power function, inverse element 
    ll ans = 1;
    a %= mod;
    while(b)
    {
        if(b & 1)
            ans = (a * ans) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

int main()
{
    a[0] = 1;//Initialization 
    for(rg int i = 1;i <= MAXN; ++i)
    {
        a[i] = (a[i - 1] * i) % mod;//Remember to take the mold. 
        inv[i] = ksm(a[i],mod - 2);//Computational inverse element 
    }
    f[1] = 0,f[2] = 1,f[3] = 2;//Initialization 
    for(rg int i = 4;i <= MAXN; ++i)
        f[i] = ((i - 1) * (f[i - 1] + f[i - 2])) % mod;//Recurrence formula 
    int T = read();//Multiple data input 
    while(T--)
    {
        int n = read(),m = read(),k = n - m;//Input n, m, k is purely convenient 
        if(!k)//If n-m=0, the number of schemes is 1 
        {
            puts("1");
            continue;
        }
        if(m == 0)//If there is no stable number, then the answer is directly equal to F[n] 
        {
            outn(f[n]);
            continue;
        }
        if(k == 1)//If n-m=1, there are 0 schemes 
        {
            puts("0");
            continue;
        }
        outn(((( a[n] * inv[k] ) % mod * inv[m]) % mod * f[k]) % mod);//output
        //It's the inverse of multiplication instead of division 
    }
    return 0;
}