## 4361: isn

Time Limit: 10 Sec Memory Limit: 256 MB

Submit: 938 Solved: 485

[Submit][Status][Discuss]

## Description

## Input

## Output

One line, one integer , Describe the answer .

## Sample Input

1 7 5 3

## Sample Output

## HINT

#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

- 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_ ...

- 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 . ...

- 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- ...

- 【 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 ...

- 【 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 ...

- 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 ...

- 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] ...

- 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 ...

- 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

- 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 ...

- 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 ...

- 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 ...

- 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. ...

- [ 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 ...

- 【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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...