Article From:

DPGood question
The idea is very simple, that is, to find the arrangement of 1-n, satisfy the number on both sides of a number, which is either larger or smaller than it, and to find such a pair of numbers.\(p\)Take the value of the membrane (for simplicity, we call this arrangement a wave sequence).
When I first saw this question, I was naturally confused. Then I looked at the solution decisively. There were two methods in the solution that I thought were wonderful, but they were not very clear, so I wrote one by myself.


Two Lemma of Forensic

Lemma 1: In a sequence of fluctuations, if\(i-1\)and\(i\)Non adjacent exchange\(i-1\)and\(i\)A new wave series can be obtained.
Lemma 2: Let the length be\(n\)Numbers in a sequence of fluctuations\(a_i\)Become\((n+1)-a_i\)A new wave series will be obtained, and the peaks and valleys of the new wave series are contrary to the original series.

State and Transfer

set up\(f[i][j]\)Represents a number consisting of 1 to I and satisfies the first number.\(j\),And\(j\)The number of fluctuation series of the peaks.
Considering the transfer, I first write the transfer equation:
\(\qquad f[i][j]=f[i][j-1]+f[i-1][i-j+1]\)
Please understand with the following text description.
From lemma 1\(j-1\)and\(j\)Non adjacent exchange\(j-1\)and\(j\)Then you get some fluctuation sequences, which are as follows\(j-1\)All the fluctuation sequences at the beginning, which correspond to the sequence before the exchange, should be added.\(f[i][j-1]\)Represented by\(j\)Some of the first fluctuation sequences can be\(j-1\)The initial fluctuation sequence shifts over.
if\(j-1\)and\(j\)Neighbouring, since we have stipulated\(j\)It’s a mountain peak.\(j-1\)It must be a valley. By imitating the above deduction process, we can see from one-to-one correspondence in lemma 2 that the length is\(i-1\)、with\(j-1\)Beginning and\(j-1\)Number of Sequences for Valleys and uuuuuuuuuuu\((i-1+1)-(j-1)\)Namely\(i-j+1\)Beginning and\(i-j+1\)The number of peaks is the same, so you need to add one\(f[i-1][i-j+1]\)
The final answer is\(2*\sum_{i=2} ^n f[n][i]\)(Anyhow\(1\)No fluctuation sequence can be constructed at the beginning.\(f[n][1]=0\),So you don’t need to.\(1\)The reason for * 2 is that only the beginning of a mountain is considered above. Lemma 2 shows that there must be one and only one beginning of a valley corresponding to each case calculated above.

I don’t think my proof has lasted for a long time.

Code Implementation

Rolling arrays can be used to optimize space.

using namespace std;
const int S=4211;
int f[2][S];
int main(){
    register int n,p,i,j,o=0;
    for(i=2;i<=n;++i) o=(o+f[n&1][i])%p;
    return 0;

221 ms, 792 KB were measured.

second kinds”

third kinds”

Fourth kinds”

fifth kinds”


set up\(f[i][j]\)There is a sequence of fluctuations representing 1 to I.\(j\)The number of fluctuation sequences is due to the fact that the number should be smaller than the previous number, which leads to the number of fluctuation sequences that do not meet the requirements of the previous number (how do you think?!).
Consider transferring, as new entries\(i+1\)It’s bigger than any number in the sequence, if you put it in

Link of this Article: [SDOI2010] Goblin Tribe