Alternating Sum

​​传送门​​

思路：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const ll mod = 1e9+9;
ll qpow(ll a,ll b)
{
  ll ans = 1;
  while(b)
  {
    if(b&1)ans = ans*a%mod;
    b>>=1;
    a = a*a%mod;
  }
  return ans;
}

void Solve()
{
  ll n,a,b,k;
  cin>>n>>a>>b>>k;
  string s;
  cin>>s;
  ll ans = 0;
  ll sum1 = 0;
  if(a==1 && b==1)
  {
    for(int i = 0; i < k; i++)
    {
      if(s[i] == '+')ans++;
      else ans--;
    }
    ans*=(n+1)/k;
    while(ans<0)ans+=mod;
    cout<<ans%mod<<endl;
    return;
  }
  for(int i = 0; i < k; i++)
  {
    if(s[i] == '+')
    sum1+=qpow(a,n-i)*qpow(b,i)%mod;
    else
    sum1=(sum1-qpow(a,n-i)*qpow(b,i)+mod)%mod;
    sum1%=mod;
  }
  ll q = qpow(b,k)*qpow(qpow(a,k),mod-2)%mod;
  if(q == 1)
  {
    cout<<sum1*(n+1)/k%mod<<endl;
    return ;
  }
  ans = sum1*(qpow(q,(n+1)/k)-1)%mod*qpow(q-1,mod-2)%mod;
  while(ans<0)ans+=mod;
  cout<<ans%mod<<endl;
}

int main()
{
  Solve();
}