C. Alternating Sum
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers aa and bb. Moreover, you are given a sequence s0,s1,…,sns0,s1,…,sn. All values in ss are integers 11 or −1−1. It's known that sequence is kk-periodic and kk divides n+1n+1. In other words, for each k≤i≤nk≤i≤n it's satisfied that si=si−ksi=si−k.

Find out the non-negative remainder of division of n∑i=0sian−ibi∑i=0nsian−ibi by 109+9109+9.

Note that the modulo is unusual!

Input

The first line contains four integers n,a,bn,a,b and kk (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 kk consisting of characters '+' and '-'.

If the ii-th character (0-indexed) is '+', then si=1si=1, otherwise si=−1si=−1.

Note that only the first kk 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 109+9109+9.

Examples
input
Copy 
2 2 3 3
+-+
output
Copy 
7
input
Copy 
4 1 5 1
-
output
Copy 
999999228
Note

In the first example:

(n∑i=0sian−ibi)(∑i=0nsian−ibi) = 2230−2131+20322230−2131+2032 = 7

In the second example:

(n∑i=0sian−ibi)=−1450−1351−1252−1153−1054=−781≡999999228(mod109+9)(∑i=0nsian−ibi)=−1450−1351−1252−1153−1054=−781≡999999228(mod109+9).



题意：告诉你前k个的符号+1,-1 。 对于 i>=k的符号=i-k;

思路：

1.对于前k个符号，每个符号对应后面的数列都是一个等比数列 q > 1。

2.for循环一遍前k个符号，等比公式。 

3.问题在于，解决这个等比数列如果不取模就涉及浮点数。因此正确做法使用逆元，逆元在数论中很重要，解决了在取模情况下的分数问题。

有逆元学习需要的，有学长的博客推荐 逆元学习 写得非常好。

用快速幂求逆元时 inva=qm(a,MOD-2)，要求a与MOD互质，其中题目给的mod=1e9+9是个质数


归结： 核心思想， 根据取模→用逆元乘法 取代 分数运算


以下是AC代码，复杂度O(log(max(a,b))*k)

还有一种计算方法，连续k个为一个集合，和后面是等比数列

#include<bits/stdc++.h>
#define PI acos(-1.0)
using namespace std;
typedef long long ll;

const int N=1e5+5;
const int MOD=1e9+9;
const int INF=0x3f3f3f3f;

ll qm(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a%MOD);
        a=(a*a)%MOD;
        b>>=1;
    }
    return ans%MOD;
}
char s[N];
int main(void){
    ll n,a,b,k;
    ll ans=0;
    cin >> n>>a>>b>>k;
    ll head=qm(a,n);
//    cout <<"head="<<head<<endl;
    ll inv_a=qm(a,MOD-2);
    ll gap=qm(b,k)*qm(inv_a,k)%MOD;
    string s;cin>>s;
//    cout <<"gap="<<gap<<endl;
    for(int i=0;i<(int)s.size();++i){
        int flag=1;
        if(s[i]=='-')  flag=-1;
        if(gap==1)  ans+=flag*(n+1)/k%MOD *head,ans= ((ans%MOD)+MOD)%MOD;
        else{
            ans+=flag*head*qm(1-gap,MOD-2)%MOD*(1-qm(gap,(n+1)/k))%MOD;
            ans= ((ans%MOD)+MOD)%MOD;
        }
        head=head*b%MOD*inv_a%MOD;
//        cout <<ans <<endl;
    }
    cout << ans << endl;
    return 0;
}