4361: isn

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 938  Solved: 485
[Submit][Status][Discuss]

Description

Give a length of n Sequence A(A1,A2...AN). If the sequence A No, it's not non-toxic , You have to delete a number from it ,
This operation , until A Not until it falls . How many different operation schemes are there , Answer model 10^9+7.

Input

The first line is an integer n.
Next line n It's an integer , describe A.

Output

One line, one integer , Describe the answer .

Sample Input

4
1 7 5 3

Sample Output

18

HINT

1<=N<=2000

set up $g(i)$ The length of a sequence is $i$ The number of nondecreasing sequences of , So we can use the inclusion exclusion principle to get the answer
$ans=\sum_{i=1}^{n}g(i)*(n-i)!-g(i+1)*(n-i-1)!*(i+1)$
$g(i)$ The illegality in ( It's already a non decreasing sequence, but it's deleted again ) It must be from $g(i+1)$ Transferred , So we can use $g(i+1)$ Get rid of $g(i)*(n-i)!$ The illegality in
 
$g(i)$ How can I ask
set up $f(i,j)$ With $i$ ending , The length is $j$ The number of nondecreasing sequences of
$f(i,j)=\sum_{k=1}^{i-1}f(k,j-1)*[A_k<=A_i]$
But this is $n^3$ Fang
So we use a tree array to put $k$ Optimize to $(logn)$
The complexity is $O(n^2logn)$
$g(i)=\sum_{j=i}^{n}f(j,i)$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define N 2005
const ll P=1e9+;
int n,m,A[N],B[N],p[N];
ll fac[N],s[N][N],f[N][N],g[N],ans;
inline ll Md(ll a){return a<P?a:a-P;}
void Add(int id,int x,ll v){for(;x<=n;x+=x&-x)s[id][x]=Md(s[id][x]+v);}
ll Sum(int id,int x){ll re=; for(;x;x-=x&-x)re=Md(re+s[id][x]); return re;}
void prep(){
fac[]=;
for(ll i=;i<=n;++i) scanf("%d",&A[i]),B[i]=A[i],fac[i]=fac[i-]*i%P;
sort(B+,B+n+); m=unique(B+,B+n+)-B-;
for(int i=;i<=n;++i) p[i]=lower_bound(B+,B+m+,A[i])-B;// discretization
}
int main(){
scanf("%d",&n); prep(); Add(,,);
for(int i=;i<=n;++i)
for(int j=i;j;--j)
f[i][j]=Md(f[i][j]+Sum(j-,p[i])),Add(j,p[i],f[i][j]);
for(int i=;i<=n;++i)
for(int j=i;j<=n;++j)
g[i]=Md(g[i]+f[j][i]);
for(ll i=;i<=n;++i)
ans=Md(Md(ans+g[i]*fac[n-i]%P)-g[i+]*fac[n-i-]%P*(i+)%P+P);
printf("%lld",ans);
return ;
}

bzoj4361 isn( Tree array optimization dp+ A class ) More articles about

  1. HDU 6240 Server(2017 CCPC Harbin station K topic ,01 Fractional programming + Tree array optimization DP)

    Topic link   2017 CCPC Harbin Problem K The question   Given a number of items , Each item can cover an area . Now we're going to cover the interval $[1, t]$. For the selected items $\frac{∑a_{i}}{∑b_ ...

  2. Codeforces 946G Almost Increasing Array ( Tree array optimization DP)

    Topic link    Educational Codeforces Round 39 Problem G The question   Given a sequence , Please turn him into Almost Increasing Array The minimum number of elements that need to be changed . ...

  3. LUOGU P2344 Cows protest ( Tree array optimization dp)

    Portal Their thinking Tree array optimization dp,f[i] Before presentation i The number of cows in a group , So it's easy to conclude that $f[i]=\sum\limits_{1\leq j\leq i}f[j-1]*(sum[i]\ge sum[j- ...

  4. 【 Answer key 】Music Festival( Tree array optimization dp)

    [ Answer key ]Music Festival( Tree array optimization dp) Gym - 101908F The question : Yes \(n\) It's a show , Each program has a start time and an end time and weights . You can only watch one program at a time ( Borders don't count ), I've seen it in all kinds of places ...

  5. 【 Answer key 】ARC101F Robots and Exits(DP Zhuangelu + Tree array optimization DP)

    [ Answer key ]ARC101F Robots and Exits(DP Zhuangelu + Tree array optimization DP) Delete all robots that can only enter one hole , It doesn't contribute to the answer Consider that a robot can only enter two holes , And the real constraint is the prefix of the operation ...

  6. BZOJ4361 isn Tree array 、DP、 A class

    Portal We don't consider the restriction of stopping after becoming a non descending sequence , So the answer is obviously \(\sum\limits_{i=1}^N cnt_i \times (N-i)!\), among \(cnt_i\) The length is \(i\) The number of nondecreasing sequences of ...

  7. 4.9 Save the race Sequence Two points Conclusion Tree array optimization dp

    It's obvious that there's a dichotomy . about n<=100 violence dp f[i][j] Before presentation i Divide into numbers j Is the paragraph feasible for the current answer . You can find this dp It can be optimized sum[i]-sum[j]<=mid sum[i] ...

  8. Codeforces 909C Python Indentation: Tree array optimization dp

    Topic link :http://codeforces.com/contest/909/problem/C The question : Python There are no braces to indicate the statement block , It's a strict indentation . Now there's a simplified version of Pytho ...

  9. BZOJ3594: [Scoi2014] Uncle Fang's corn field 【 Two dimensional tree array optimization DP】

    Description Uncle Fang is walking by his farm , He suddenly found that a row of corn in the field was very ugly . This row of corn has N plant , They're very different in height . Uncle Fang thinks that monotonic non decreasing sequence is very beautiful , So he decided to pull up some corn first , And then destroy the beauty ...

Random recommendation

  1. opencv And icvCreateHidHaarClassifierCascade Classifier information initialization function part detailed code comments .

    Please see comments . This function , It's the main function of face recognition , One of the functions that we've seen in it , The function is to initialize the data of the classifier , It's just one. xml Data initialization of file . static CvHidHaarClassifierCascade* icvCr ...

  2. Map Tool series -03- Code generation BySQl Instructions for use of tools

    all cs The end tool integrates a tool panel - open (IE) Map Tool series -01-Map Code generation tool description Map Tool series -02- Data migration tool instructions Map Tool series -03- Code generation BySQl Instructions for use of tools Map ...

  3. LeetCode 【318. Maximum Product of Word Lengths】

    Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the tw ...

  4. android matters needing attention

    Do Android design today , Learning layout . In the process, I encountered a few small problems , I feel it's very necessary to share the records . 1.string Strings don't appear "that's" , To use “that is” Otherwise, it will report a mistake . 2. ...

  5. [ turn ] Python Code performance optimization techniques

    When you choose a scripting language, you have to endure its speed , To some extent, this sentence shows that python As a weakness of the script , That is, the execution efficiency and performance are not ideal , Especially in performance On a poor machine , So it is necessary to optimize the code ...

  6. 【Struts】 Upload and download server files

    Java Get the file suffix of the file in import java.io.*; public class FileTest{ public static void main(String args[]){ File ...

  7. VS2015 In the preview C#6.0 new function ( One )

    VS2015 In the preview C#6.0 new function ( Two ) VS2015 In the preview C#6.0 new function ( 3、 ... and ) VS2015 The preview version of 11 month 12 Date issued , Let's take a look C# What new features are provided . String addition (Str ...

  8. iOS objc_msgSend Wild pointer Crash from Log extract Crash when selector And print

    from crash stack log Inside , extract objc_msgSend keyword , Is the positioning caused by the wild pointer problem crash, If so, print crash At the time of the objc_msgSend The second parameter of the call , namely ...

  9. Centos7+ASP.Net Core function

    One :ASP.Net Core Running across platforms , Need to be in Linux Install the operating environment . This machine uses Centos, The download and installation address is :https://www.microsoft.com/net/core#centos su ...

  10. Python socket Glue package to solve

    socket Sticky package : socket Interaction send when , Continuous processing of multiple send There will be sticky package when it is used ,soket I'll take two send As a send Force send , It's going to stick together . send The transmission will be based on recv The defined value sends a fixed ...