Solution to the problem of permutation and counting of Logu P4071-[SDOI2016]

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.

Main idea:

A sequence whose length is n and 1~n occurs once respectively is expected to find out the number of sequences under the condition that "there are only m numbers in the sequence whose value is equal to its position". The answer is to model 100000007.

Topic analysis:

This problem may be an enhanced version of "misplaced envelope". Just play with Billy on the "misplaced envelope". We may set:
The number whose value is equal to the position is stable
The value is not equal to the position, the number is unstable

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.

Number of stable selection methods:

We have known that the stable numbers are increasing from left to right, so we only need to simulate which numbers are stable.

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

Number of unstable selection methods (staggered):

If we have known which m numbers are stable, we can only look at the unstable numbers in the array for the time being.

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} \)

Specific operation ideas:

We need to initialize first. We need to initialize factorials for \ (C ^ y \) and recurs for \ (f ^ I \).

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

But (not over yet):

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)

What is 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

How to apply inverse element to the problem

We initialize the inverse element array inv, inv is the inverse element of factorial

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

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 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
{
{
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;
}

Keywords: C++

Added by jaql on Sun, 12 Jan 2020 15:34:52 +0200