Python3 解法, 执行用时: 95ms, 内存消耗: 5832K, 提交时间: 2022-04-29 22:30:21

import sys

def read_str():
    return sys.stdin.readline().strip()
def read_int():
    return int(read_str())
def read_strs():
    return read_str().split()
def read_ints():
    return list(map(int, read_strs()))
##############################

n, a, b, k = map(int, input().strip().split())
MOD = 10**9+9

q = pow(b, k, MOD) * pow(pow(a, k, MOD), -1, MOD) % MOD
s = [1 if x == '+' else -1 for x in read_str()]
ab = pow(a, n, MOD)

ia = pow(a, -1, MOD)
z = 0
for i in range(k):
    z = (z + s[i % k] * ab) % MOD
    ab = ab * ia * b % MOD

m = (n+1) // k
if q == 1:
    print(z * m % MOD)
else:
    print(z * (pow(q, m, MOD)-1) * pow(q-1, -1, MOD) % MOD)

C++ 解法, 执行用时: 24ms, 内存消耗: 664K, 提交时间: 2021-12-14 00:18:51

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+9;
int qs(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
char s[100010];
int n,a,b,k;
signed main()
{
	cin>>n>>a>>b>>k;
	int m=n;
	n=(n+1)/k;
	scanf("%s",s);
	int res=0;
	int ak=qs(a,k);
	int xi=qs(b,k)*qs(ak,p-2)%p;
	if(xi==1){
		xi=n;
	}else {
		xi=(qs(xi,n)-1)*qs((xi-1)%p,p-2)%p;
		xi=(xi+p)%p;
	}
	
	for(int i=0;i<k;i++){
		if(s[i]=='+') res=(res+qs(a,m-i)*qs(b,i)%p*xi%p)%p;
		else res=(res-qs(a,m-i)*qs(b,i)%p*xi%p)%p;
	}
	res=(res+p)%p;
	cout<<res;
}