search
HomeWeb Front-endHTML TutorialCodeforces Round #266 (Div. 2) D. Increase Sequence_html/css_WEB-ITnose

Peter has a sequence of integers a1,?a2,?...,?an. Peter wants all numbers in the sequence to equalh. He can perform the operation of "adding one on the segment[l,?r]": add one to all elements of the sequence with indices froml to r (inclusive). At that, Peter never chooses any element as the beginning of the segment twice. Similarly, Peter never chooses any element as the end of the segment twice. In other words, for any two segments [l1,?r1] and[l2,?r2], where Peter added one, the following inequalities hold:l1?≠?l2 andr1?≠?r2.

How many distinct ways are there to make all numbers in the sequence equal h? Print this number of ways modulo 1000000007 (109? ?7). Two ways are considered distinct if one of them has a segment that isn't in the other way.

Input

The first line contains two integers n,?h(1?≤?n,?h?≤?2000). The next line containsn integers a1,?a2,?...,?an(0?≤?ai?≤?2000).

Output

Print a single integer ? the answer to the problem modulo 1000000007 (109? ?7).

Sample test(s)

Input

3 21 1 1

Output

Input

5 11 1 1 1 1

Output

Input

4 33 2 1 1

Output

0题意:选择若干个不重复的区间执行+1操作,求有多少种方法使得序列都是m思路:dp[i][open]表示到第i个后左边还有多少个未匹配右括号的个数,另外还有一篇不错的题解:参考;引用:<p></p><p>Lets use dynamic programming to solve this problem. dp[i][opened] ? the number of ways to cover prefix of array 1..i by segments and make it equal to h and remain after i-th element opened segments that are not closed.</p><p>Consider all possible variants opening/closing segments in each position:- ] closing one segment- [ opening one new segment- [] adding one segment with length 1- ][ closing one opened segment and opening a new one- - do nothing</p><p>Lets understand how to build dynamic. It is obviously to understand that a[i]?+?opened can be equal h or h?-?1. Otherwise, number of such ways equals 0.</p><p>Consider this two cases separately:</p><p>1) a[i]?+?opened?=?hIt means that number of opened segments after i-th as max as possible and we can’t open one more segment in this place. So there are two variants:- [ Opening a new segment. If only opened?>?0. dp[i][opened] += dp[i-1][opened + 1]- - Do nothing. dp[i][opened] += dp[i-1][opened]</p><p>Other variants are impossible because of summary value of a[i] will be greater than h(when segment is finishing in current position ? it increase value, but do not influence on opened, by the dynamic definition.</p><p>2) a[i]?+?opened?+?1?=?h Here we consider ways where i-th element has been increased by opened?+?1 segments, but after i-th remain only opened not closed segments. Therefore, there are next variants:- ] ? closing one of the opened segments(we can do it opened?+?1 ways).dp[i][opened] += dp[i-1][opened + 1] * (opened + 1) - [] ? creating 1-length segment. dp[i][opened] += dp[i-1][opened] - ][ ? If only opened?>?0. Amount of ways to choose segment which we will close equals opened.dp[i][opened] += dp[i-1][opened] * opened</p><p>Start values ? dp[1][0] = (a[1] == h || a[1] + 1 == h?1:0); dp[1][1] = (a[1] + 1 == h?1:0)</p><p>Answer ? dp[n][0].</p><p></p><strong></strong><pre name="code" class="n">#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>typedef long long ll;using namespace std;const int maxn = 2010;#define mod 1000000007ll dp[maxn][maxn];int a[maxn];inline void add(ll &a, ll b) {	a += b;	a %= mod;}int main() {	int n, h;	cin >> n >> h;		for (int i = 1; i > a[i];	dp[1][0] = (a[1] == h || a[1]+1 == h ? 1 : 0);	dp[1][1] = (a[1]+1 == h ? 1 : 0);	for (int i = 2; i  0)					add(dp[i][open], dp[i-1][open-1]);			}			if (open + a[i] + 1 == h) {				add(dp[i][open], dp[i-1][open+1]*(open+1));				add(dp[i][open], dp[i-1][open]);				add(dp[i][open], dp[i-1][open]*open);			}		}	cout <br><br></algorithm></cstring></cstdio></iostream>
Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Are the HTML tags and elements the same thing?Are the HTML tags and elements the same thing?Apr 28, 2025 pm 05:44 PM

The article explains that HTML tags are syntax markers used to define elements, while elements are complete units including tags and content. They work together to structure webpages.Character count: 159

What is the significance of <head> and <body> tag in HTML?What is the significance of <head> and <body> tag in HTML?Apr 28, 2025 pm 05:43 PM

The article discusses the roles of <head> and <body> tags in HTML, their impact on user experience, and SEO implications. Proper structuring enhances website functionality and search engine optimization.

What is the difference between <strong>, <b> tags and <em>, <i> tags?What is the difference between <strong>, <b> tags and <em>, <i> tags?Apr 28, 2025 pm 05:42 PM

The article discusses the differences between HTML tags , , , and , focusing on their semantic vs. presentational uses and their impact on SEO and accessibility.

Please explain how to indicate the character set being used by a document in HTML?Please explain how to indicate the character set being used by a document in HTML?Apr 28, 2025 pm 05:41 PM

Article discusses specifying character encoding in HTML, focusing on UTF-8. Main issue: ensuring correct display of text, preventing garbled characters, and enhancing SEO and accessibility.

What are the various formatting tags in HTML?What are the various formatting tags in HTML?Apr 28, 2025 pm 05:39 PM

The article discusses various HTML formatting tags used for structuring and styling web content, emphasizing their effects on text appearance and the importance of semantic tags for accessibility and SEO.

What is the difference between the 'id' attribute and the 'class' attribute of HTML elements?What is the difference between the 'id' attribute and the 'class' attribute of HTML elements?Apr 28, 2025 pm 05:39 PM

The article discusses the differences between HTML's 'id' and 'class' attributes, focusing on their uniqueness, purpose, CSS syntax, and specificity. It explains how their use impacts webpage styling and functionality, and provides best practices for

What is the 'class' attribute in HTML?What is the 'class' attribute in HTML?Apr 28, 2025 pm 05:37 PM

The article explains the HTML 'class' attribute's role in grouping elements for styling and JavaScript manipulation, contrasting it with the unique 'id' attribute.

What are different types of lists in HTML?What are different types of lists in HTML?Apr 28, 2025 pm 05:36 PM

Article discusses HTML list types: ordered (<ol>), unordered (<ul>), and description (<dl>). Focuses on creating and styling lists to enhance website design.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.