# Bzoj2431: [haoi2009] inverse pairwise sequence (DP, difference)

2021-07-30 04:42:50 ## Description

For a sequence {ai}, If there is i<j And ai>aj, Then we call ai And aj Is a pair of inverse logarithms . If for any one by 1~n It's made up of natural numbers
The sequence , It's easy to find out how many inverse logarithms there are . Then the inverse logarithm is k How many natural numbers are there ？

## Input

The first line is two integers n,k.

## Output

Write an integer , Indicates the number of qualified series , Because this number may be very large , You just output the number pair 10000 The result of finding the remainder .

4 1

## Sample Output

3

Sample explanation ：
The following 3 The reverse logarithms of all sequences are 1; Namely 1 2 4 3 ;1 3 2 4 ;2 1 3 4;
100% The data of n<=1000,k<=1000

## Solution

In the computer room see After listening to all morning's World Final……
It's easy to design a state f[i][j] Express i The number is j The number of reverse order pairs
Suppose you put i-1 Number , It's time to put it in the first place i Number. .
Because the first i The number is the largest , So putting it to the far right of the queue can generate additional 0 In reverse order , Put it on the far left to generate additional i-1 individual
So put the first i The number can be increased 0~i-1 In reverse order
that f[i][j]=sigma(f[i-1][k]), among max(0,j-i+1)<=k<=j
It's easy to write a n^3 The violence of

## Code

``` 1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #define N (1000+10)
5 using namespace std;
6 int f[N][N],n,m;
7 int main()
8 {
9     scanf("%d%d",&n,&m);
10     f=1;
11     for (int i=1; i<=n; ++i)
12         for (int j=0; j<=m; ++j)
13             for (int k=max(0,j-i+1); k<=j; ++k)
14                 (f[i][j]+=f[i-1][k])%=10000;
15     printf("%d",f[n][m]);
16 }```

However n^3 Violence will never pass 1000 Of . However, there are 90.
We found that the third cycle of violence is just query f[i-1][] A section of ,
We just need one side DP While calculating the prefix and , Then you can optimize the third loop with prefix and .

``` 1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #define N (1000+10)
5 using namespace std;
6 int f[N][N],sum[N][N],n,m;
7 int main()
8 {
9     scanf("%d%d",&n,&m);
10     for (int i=0; i<=m; ++i)
11         sum[i]=1;
12     for (int i=1; i<=n; ++i)
13         for (int j=0; j<=m; ++j)
14         {
15             f[i][j]=(j-i>=0) ? (sum[i-1][j]-sum[i-1][j-i]+10000)%10000 : sum[i-1][j];
16             sum[i][j]=(sum[i][j-1]+f[i][j])%10000;
17         }
18     printf("%d",f[n][m]);
19 }```

https://chowdera.com/2021/07/20210728100054495p.html