C. Alternating Sum

Codeforces

IDCF964C

Time1000ms

Memory256MB

Difficulty—

mathmatricesnumber theory

English · Original

Chinese · Translation

Formal · Original

You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$\-periodic and $k$ divides $n+1$. In other words, for each $k \leq i \leq n$ it's satisfied that $s_{i} = s_{i - k}$. Find out the **non-negative** remainder of division of $\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$ by $10^{9} + 9$. **Note that the modulo is unusual!** ## Input The first line contains four integers $n, a, b$ and $k$ $(1 \leq n \leq 10^{9}, 1 \leq a, b \leq 10^{9}, 1 \leq k \leq 10^{5})$. The second line contains a sequence of length $k$ consisting of characters '_+_' and '_\-_'. If the $i$\-th character (0-indexed) is '_+_', then $s_{i} = 1$, otherwise $s_{i} = -1$. Note that only the first $k$ members of the sequence are given, the rest can be obtained using the periodicity property. ## Output Output a single integer — value of given expression modulo $10^{9} + 9$. [samples] ## Note In the first example: $(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i})$ = $2^{2} 3^{0} - 2^{1} 3^{1} + 2^{0} 3^{2}$ = 7 In the second example: $(\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}) = -1^{4} 5^{0} - 1^{3} 5^{1} - 1^{2} 5^{2} - 1^{1} 5^{3} - 1^{0} 5^{4} = -781 \equiv 999999228 \pmod{10^{9} + 9}$.

给定两个整数 $a$ 和 $b$，以及一个序列 $s_0, s_1, dots.h, s_n$。序列 $s$ 中的所有值均为整数 $1$ 或 $-1$。已知该序列是 $k$-周期的，且 $k$ 整除 $n + 1$。换句话说，对于每个 $k lt.eq i lt.eq n$，均有 $s_i = s_(i -k)$。求表达式 $sum limits_(i = 0)^n s_i a^(n -i) b^i$ 除以 $10^9 + 9$ 的**非负余数**。 *注意：模数不寻常！* 第一行包含四个整数 $n, a, b$ 和 $k$ $(1 lt.eq n lt.eq 10^9, 1 lt.eq a, b lt.eq 10^9, 1 lt.eq k lt.eq 10^5)$。第二行包含一个长度为 $k$ 的字符串，由字符 '_+_' 和 '_-_' 组成。如果第 $i$ 个字符（从 0 开始计数）是 '_+_'，则 $s_i = 1$；否则 $s_i = -1$。请注意，仅给出了序列的前 $k$ 个元素，其余元素可通过周期性性质推导得出。输出一个整数——给定表达式对 $10^9 + 9$ 取模的值。 ## Input 第一行包含四个整数 $n, a, b$ 和 $k$ $(1 lt.eq n lt.eq 10^9, 1 lt.eq a, b lt.eq 10^9, 1 lt.eq k lt.eq 10^5)$。第二行包含一个长度为 $k$ 的字符串，由字符 '_+_' 和 '_-_' 组成。如果第 $i$ 个字符（从 0 开始计数）是 '_+_'，则 $s_i = 1$；否则 $s_i = -1$。请注意，仅给出了序列的前 $k$ 个元素，其余元素可通过周期性性质推导得出。 ## Output 输出一个整数——给定表达式对 $10^9 + 9$ 取模的值。 [samples] ## Note 在第一个例子中：$(sum limits_(i = 0)^n s_i a^(n -i) b^i)$ = $2^23^0 -2^13^1 + 2^03^2$ = 7 在第二个例子中：$(sum limits_(i = 0)^n s_i a^(n -i) b^i) = -1^45^0 -1^35^1 -1^25^2 -1^15^3 -1^05^4 = -781 equiv 999999228 pmod 10^(9) + 9$。

**Definitions** Let $ M = 10^9 + 9 $. Let $ n, a, b, k \in \mathbb{Z} $ with $ 1 \leq n \leq 10^9 $, $ 1 \leq a, b \leq 10^9 $, $ 1 \leq k \leq 10^5 $, and $ k \mid (n+1) $. Let $ s = (s_0, s_1, \dots, s_{k-1}) \in \{1, -1\}^k $ be the base period of the sequence, extended periodically: $ s_i = s_{i \bmod k} $ for all $ i \geq 0 $. **Constraints** 1. $ k \mid (n+1) $ 2. $ s_i \in \{1, -1\} $ for all $ i \in \{0, 1, \dots, k-1\} $, determined by input characters: - $ s_i = 1 $ if the $ i $-th character is '+' - $ s_i = -1 $ if the $ i $-th character is '-' **Objective** Compute the non-negative remainder modulo $ M $ of: $$ \sum_{i=0}^{n} s_i \cdot a^{n-i} \cdot b^i $$ That is, compute: $$ \left( \sum_{i=0}^{n} s_i \cdot a^{n-i} \cdot b^i \right) \bmod M $$

Samples

Input #1

2 2 3 3
+-+

Output #1

Input #2

4 1 5 1
-

Output #2

999999228

API Response (JSON)

{
  "problem": {
    "name": "C. Alternating Sum",
    "description": {
      "content": "You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \\dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$\\-periodic and $k$ divid",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF964C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given two integers $a$ and $b$. Moreover, you are given a sequence $s_0, s_1, \\dots, s_{n}$. All values in $s$ are integers $1$ or $-1$. It's known that sequence is $k$\\-periodic and $k$ divid...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定两个整数 $a$ 和 $b$，以及一个序列 $s_0, s_1, dots.h, s_n$。序列 $s$ 中的所有值均为整数 $1$ 或 $-1$。已知该序列是 $k$-周期的，且 $k$ 整除 $n + 1$。换句话说，对于每个 $k lt.eq i lt.eq n$，均有 $s_i = s_(i -k)$。\n\n求表达式 $sum limits_(i = 0)^n s_i a^(n -i) ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ M = 10^9 + 9 $.  \nLet $ n, a, b, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^9 $, $ 1 \\leq a, b \\leq 10^9 $, $ 1 \\leq k \\leq 10^5 $, and $ k \\mid (n+1) $.  \nLet $ s = (s_0, s_1,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments