A preliminary study of the relationship between combinatorial mathematics and DP, and the derivation of resettable combinatorial formulas

4002. Construct an array ( Reveals DP The essence of is combinatorics )

---

Now you need to construct a pair of arrays $(a,b)$, requirement ：

• Array $a$ And an array $b$ The length of each of them is $m$.
• The value range of the elements in both arrays is $[1,n]$.
• $\forall i\in [1,m]$,$ai\le bi$.
• Array $a$ Elements in are not strictly monotonically increasing .
• Array $b$ Elements in are not strictly monotonically decreasing .

Excuse me, , How many pairs of arrays that meet the conditions can be constructed ？

Output pair $10^9+7$ The result after taking the mold .

---

At first glance, there are many conditions , It's hard .

Method ： A combination of numbers and shapes , Multiplication principle （ Consider step by step ）

Just draw casually on the paper $a$ and $b$ You can find that the problem can be transformed into ：

1. from $n$ In number （ Each number can be selected repeatedly ） choose $2\ast m$ Number , Arrange these numbers , The big half is for $b$ , Give the other half $a$ .
2. analysis $a$ Medium $m$ Number , How many distribution schemes are there ？

answer 2 ： Find the given $m$ After the number is determined , The plan is the only .

So the problem is equivalent to 1 Number of alternatives （ Classical reconfigurable set combinatorial problem ）, The answer is $C(2m+n-1,n-1)$

---

Mathematical derivation ：（ Ideas , It is known that $C(n,m)$ From $n$ individual Different Take from the number of $m$ Number of projects ）.

The following is the template thinking routine in Mathematics ：

1. set up $x_i$ It means the first one $i$ How many to take . Yes ${\sum }_{i=1}^n{x}_i=2\ast m,x_i\ge 0$
2. set up $x_i^{\prime }=x_i+1$ Yes ${\sum }_{i=1}^n{x}_i=2\ast m+n,x_i>0$
3. The problem turns into a given $2\ast m+n$ A little ball , use $n-1$ A partition divides all the small balls into $n$ part , The number of balls in each part must Greater than $0$ . because $x_i>0$ , So the clapboard has $2\ast m+n-1$ A place , And because each partition is different , So it can be used $C(2m+n-1,n-1)$ Express . Obtain evidence .

One small TRICK $C(2m+n-1,n-1)$ = $C(2m+n-1,2m)$ Which data range is small, which one is used

---

How to find the combination number ？$C(n,m)=C(n-1,m-1)+C(n-1,m)$ Isn't that what 0/1 The derivation of knapsack ？

---

therefore ：$C(2m+n-1,n-1)$ It can be used $0/1$ knapsack .$2m+n-1$ It's the volume of the backpack , The volume of each element is $1$ .

original DP The number of schemes can be calculated because DP The underlying logic of is combinatorics , The principle of multiplication and addition in combinatorics can solve the number of schemes .

So an obvious idea , Is it possible to use complete knapsack directly to find the number of schemes in a re set ？ The answer is obvious ！

The following is the code of two knapsacks seeking the same problem .

0/1 knapsack 
f[0]=1;
for(int i=1;i<=2*m+n-1;i++){
    
    for(int j=2*m;j>=1;j--){
    
        f[j]= ((f[j] + f[j-1]) + M )%M;
    }
}
cout<<f[2*m]<<endl;

 Completely backpack 
f[0]=1;
for(int i=1;i<=n;i++){
    
    for(int j=1;j<=2*m;j++){
    
        f[j]= ((f[j] + f[j-1]) + M )%M;
    }
}
cout<<f[2*m]<<endl;