Alternating Sum
题意翻译
##### 题目描述
给你两个整数 $a$ 和 $b$ 。再给你一个序列 $s_0, s_1, \cdots, s_n$ ,其中 $s_i$ 要么为 $1$ ,要么为 $-1$ 。已知这个序列以 $k$ 为周期并且 $k$ 整除 $n + 1$ ,换句话说,对于所有满足 $k \le i \le n$ 的 $i$ 都有 $s_i = s_{i - k}$ 。
求出下式在模 $10^9 + 9$ 意义下的值(注意是 $+9$ !):
$\sum_{i = 0}^{n} s_i a^{n - i}b^i$
##### 输入
第一行包含四个整数 $n$ , $a$ , $b$ 和 $k$ 。
第二行包含一个长度为 $k$ 的正负号序列,用 `+` 表示 $1$ ,用 `-` 表示 $-1$ ,表示 $s_{0 \sim k - 1}$ 。可以用这个长度为 $k$ 的序列构造出整个 $s$ 序列。
##### 输出
输出一个整数:给定表达式的值模 $10^9 + 9$ 的值,最后的结果必须是非负的。
##### 数据规模与约定
$1 \le n \le 10^9$ , $1 \le a, b \le 10^9$ , $1 \le k \le 10^5$ 。
感谢@OrangeLee 提供的翻译
题目描述
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!
输入输出格式
输入格式
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 a single integer — value of given expression modulo $ 10^{9} + 9 $ .
输入输出样例
输入样例 #1
2 2 3 3
+-+
输出样例 #1
7
输入样例 #2
4 1 5 1
-
输出样例 #2
999999228
说明
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} $ .