Codeforces 963 A. Alternating Sum （逆元）

Codeforces 963 A. Alternating Sum （逆元）

Description

You are given two integers a a and bb. Moreover, you are given a sequence s0,s1,…,sn s 0 , s 1 , … , s n . All values in s s are integers 11 or −1 − 1 . It’s known that sequence is k k -periodic and kk divides n+1 n + 1 . In other words, for each k≤i≤n k ≤ i ≤ n it’s satisfied that si=si−k s i = s i − k .Find out the non-negative remainder of division of ∑i=0nsian−ibi ∑ i = 0 n s i a n − i b i by 109+9 10 9 + 9 .Note that the modulo is unusual!

Input

The first line contains four integers n,a,b n , a , b and k k (1≤n≤109,1≤a,b≤109,1≤k≤105)(1≤n≤109,1≤a,b≤109,1≤k≤105).The second line contains a sequence of length k k If the ii-th character (0-indexed) is ‘+’, then si=1 s i = 1 , otherwise si=−1 s i = − 1 .Note that only the first k k

Output

Output a single integer — value of given expression modulo 109+9109+9.

Examples input

2 2 3 3+-+

Examples output

7

题意

给定数据 n,a,b,k n , a , b , k 以及 s s

思路

因为 ss 中每 k k 段是一样的，于是原公式便等价于一个公比为 a−kbka−kbk 的等比数列前 (n+1)/k ( n + 1 ) / k

配合逆元求解即可。

AC 代码

#include #define IO \ ios::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0);using namespace std;typedef long long LL;const int maxn = 1e5 + 10;const int mod = 1e9 + 9;LL a, b, n, k;char str[maxn];LL mult(LL a, LL n) { LL ans = 1; while (n) { if (n & 1) ans = (ans * a) % mod; a = (a * a) % mod; n >>= 1; } return ans;}void solve() { LL ans = 0, res = 0; LL inva = mult(a, mod - 2); LL pw = mult(a, n); LL lun = (n + 1) / k; for (int i = 0; i < k; i++) { res += (str[i] == '+' ? 1 : -1) * pw % mod; res %= mod; pw = pw * inva % mod * b % mod; } LL q = mult(inva, k) * mult(b, k) % mod; if (q == 1) { ans = res * lun % mod; } else { LL di = mult((q - 1 + mod) % mod, mod - 2); LL de = (mult(q, lun) - 1 + mod) % mod; ans = res * de % mod * di % mod; } ans = ((ans % mod) + mod) % mod; cout << ans << endl;}int main() {#ifndef ONLINE_JUDGE freopen("test.in", "r", stdin); freopen("test.out", "w", stdout);#else IO;#endif // ONLINE_JUDGE cin >> n >> a >> b >> k; cin >> str; solve(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。