C. Python Indentation

Codeforces

IDCF909C

Time2000ms

Memory256MB

Difficulty—

English · Original

Chinese · Translation

Formal · Original

In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation. We will consider an extremely simplified subset of Python with only two types of statements. **Simple statements** are written in a single line, one per line. An example of a simple statement is assignment. **For statements** are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for" prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty. You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program. ## Input The first line contains a single integer _N_ (1 ≤ _N_ ≤ 5000) — the number of commands in the program. _N_ lines of the program follow, each line describing a single command. Each command is either "f" (denoting "for statement") or "s" ("simple statement"). It is guaranteed that the last line is a simple statement. ## Output Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 109 + 7. [samples] ## Note In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one. simple statement for statement for statement simple statement In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one. for statement simple statement for statement simple statement or for statement simple statement for statement simple statement

在 Python 中，代码块没有显式的 begin/end 或花括号来标记块的开始和结束，而是通过缩进来定义代码块。我们将考虑一个仅包含两种语句的极简 Python 子集。 *简单语句* 单独占一行，每行一个。例如赋值语句就是一种简单语句。 *for 语句* 是复合语句：它们包含一个或多个其他语句。for 语句由一个单独行的头部组成，该行以 "for" 前缀开头，后跟循环体。循环体是一个缩进层级比头部高一级的语句块。循环体可以包含两种类型的语句，且不能为空。你被给定一个没有缩进的语句序列。请计算有多少种方式可以为这些语句添加缩进，使其构成一个合法的 Python 程序。第一行包含一个整数 $N$ ($1 ≤ N ≤ 5000$) —— 程序中的语句数量。接下来 $N$ 行，每行描述一个语句，每个语句要么是 "f"（表示 "for 语句"），要么是 "s"（"简单语句"）。保证最后一行是简单语句。请输出一个整数，表示给定语句序列能被缩进成合法 Python 程序的方式数，对 $10^9 + 7$ 取模。 ## Input 第一行包含一个整数 $N$ ($1 ≤ N ≤ 5000$) —— 程序中的语句数量。接下来 $N$ 行，每行描述一个语句，每个语句要么是 "f"（表示 "for 语句"），要么是 "s"（"简单语句"）。保证最后一行是简单语句。 ## Output 请输出一个整数，表示给定语句序列能被缩进成合法 Python 程序的方式数，对 $10^9 + 7$ 取模。 [samples] ## Note 在第一个测试用例中，只有一种缩进方式：第二个 for 语句必须是第一个 for 语句体的一部分。 simple statement for statement for statement simple statement 在第二个测试用例中，有两种缩进方式：第二个 for 语句可以是第一个 for 语句体的一部分，也可以是紧随其后的独立语句。 for statement simple statement for statement simple statement 或 for statement simple statement for statement simple statement

**Definitions** Let $ N \in \mathbb{Z} $ be the number of statements. Let $ S = (s_1, s_2, \dots, s_N) $ be a sequence where $ s_i \in \{ \texttt{f}, \texttt{s} \} $, with $ s_N = \texttt{s} $. Let $ d_i \in \mathbb{Z}_{\geq 0} $ denote the indentation depth (number of leading spaces) of statement $ i $, representing the level of nesting. **Constraints** 1. $ 1 \leq N \leq 5000 $ 2. $ d_1 = 0 $ 3. For each $ i \in \{1, \dots, N-1\} $: - If $ s_i = \texttt{s} $, then $ d_{i+1} \leq d_i $ - If $ s_i = \texttt{f} $, then $ d_{i+1} = d_i + 1 $ 4. For all $ i \in \{1, \dots, N\} $, $ d_i \geq 0 $ **Objective** Compute the number of valid sequences $ (d_1, d_2, \dots, d_N) $ satisfying the above constraints, modulo $ 10^9 + 7 $.

Samples

Input #1

4
s
f
f
s

Output #1

Input #2

4
f
s
f
s

Output #2

API Response (JSON)

{
  "problem": {
    "name": "C. Python Indentation",
    "description": {
      "content": "In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation. We will consider an extremely simplified ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF909C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.\n\nWe will consider an extremely simplified ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "在 Python 中，代码块没有显式的 begin/end 或花括号来标记块的开始和结束，而是通过缩进来定义代码块。\n\n我们将考虑一个仅包含两种语句的极简 Python 子集。\n\n*简单语句* 单独占一行，每行一个。例如赋值语句就是一种简单语句。\n\n*for 语句* 是复合语句：它们包含一个或多个其他语句。for 语句由一个单独行的头部组成，该行以 \"for\" 前缀开头，后跟循环体。循环体是一个缩...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of statements.  \nLet $ S = (s_1, s_2, \\dots, s_N) $ be a sequence where $ s_i \\in \\{ \\texttt{f}, \\texttt{s} \\} $, with $ s_N = \\texttt{s} $.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments